数据结构第六章-二叉树.pptx

1第6章二叉树和树

线索二叉树的建立、使用；树的各种存储结构及其特点；树、森林与二叉树之间的转换；树、森林的遍历。【掌握】：【重点掌握】：二叉树的结构特性;二叉树的各种存储结构的特点及适用范围;二叉树各种遍历策略的递归算法，且能灵活运用遍历算法实现二叉树的其它操作；最优二叉树的特性，建立最优树和哈夫曼编码的方法。

线性结构的特点是逻辑结构简单，易于进行查找、删除、插入等操作。其主要用于对客观世界中具有单一的前驱和后继的数据关系进行描述。非线性结构是指在该结构中至少存在一个数据元素有两个或两个以上的直接前驱或直接后继。树形结构是一类重要的非线性结构。树形结构是结点之间有分支、并且具有层次关系的结构，它非常类似于自然界中的树。树结构在客观世界是大量存在的，例如家谱、行政组织机构都可用树形象地表示。树在计算机领域中也有着广泛的应用，例如在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织信息；在分析算法的行为时，可用树来描述其执行过程等等。图形结构是十分重要的非线性结构，可以用来描述客观世界中广泛存在的网状结构的关系。

6.1二叉树6.1.2二叉树的基本概念1.二叉树(BinaryTree)(1)定义：二叉树是n（n=0）个数据元素的集合，该集合或为空，或含有唯一的称为根的元素，且其余元素分成两个互不相交的子集，每个子集自身也是一棵二叉树，分别称为左子树和右子树。说明:1）二叉树是递归结构，在二叉树的定义中又用到了二叉树的概念2）二叉树中每个结点最多有两棵子树,二叉树每个结点度小于等于2ABCDEFG

53）左、右子树不能颠例二叉树结点的子树要区分左子树和右子树：即使只有一棵子树也要进行区分，说明它是左子树，还是右子树。这是二叉树与树的最主要的差别。ABAB两棵不同的二叉树(2)二叉树的5种基本形态φ空二叉树根和空的左右子树根和左子树根和右子树根和左右子树

2.二叉树的基本术语1)孩子(child)：结点的子树的根称为该结点的孩子；左孩子，右孩子。2)双亲(parents)：孩子结点的上层结点。3)兄弟(sibling)：同一双亲的孩子结点；堂兄弟、祖先结点、子孙结点4)叶子(leaf)：终端结点，左右子树均为空的结点；反之，分支结点。5)结点的度(degree)：结点拥有的子树数。6)二叉树的度：树中最大的结点度。7)结点层(level)：从根结点开始算起，根为第一层；根的孩子为第2层结点；……8）二叉树的深度(depth)：二叉树中叶子结点的最大层次数。

※二叉树的基本性质性质1：一棵非空二叉树的第i层上最多有2i-1个结点（i≥1）。

此树的深度k=4，共有24-1=15个结点性质2：一棵深度为k的二叉树中，最多有2k-1个结点（k≥1)。深度为k的二叉树取最多结点时，二叉树中的每层上均应取最多结点。根据性质1得到每层上的最大结点数为2i-1，则二叉树中的总结点数为：20+21+……+2k-1=2k-1。

9性质3：对于非空二叉树，如果叶子结点数为n0，度为2的结点数为n2，则有n0=n2+1。证明：设二叉树中度为1的结点数为n1，二叉树中总结点数为N，因为二叉树中所有结点均小于或等于2，所以有：N＝n0＋n1＋n2(6-1)再看二叉树中的分支数，除根结点外，其余结点都由一个分支与其双亲相连接，设B为二叉树中的分支总数，则有：N＝B＋1（6-2)由于这些分支都是由度为1和2的结点射出的，所以有：B＝n1+2*n2（6-3)即：N＝B＋1＝n1＋2×n2＋1由式（6-1）得到：n0+n1+n2=n1+2*n2+1即：n0＝n2＋1n0=3n2=2ABCDEFG

k=4的满二叉树※两种特殊的二叉树(1)满二叉树：如果深度为k的二叉树有2k-1个结点，则称为满二叉树。特点：每一层上都含有最大结点数。

logo（2）完全二叉树：如果二叉树除最后一层外每一层都是满的，且最后一层或者是满的，或者结点都连续地集中在该层的最左端，则称其为完全二叉树。特点：1)所有的叶子结点都出现在第k层或k-1层;2)对任一结点，如果其右子树的最大层次为L，则其左子树的最大层次为L或L+1。非完全二叉树123114589121367101415满二叉树（完全二叉树)123114589126710完全二叉树1234567非完全二叉树

性质4：具有n个结点的完全二叉树的深度为：?log2n+1?。（符号?x?表示不大