第八章树和二叉树_1讲述.ppt

合肥工业大学 计算机与信息学院 * 算法与数据结构 （第八章 树和二叉树） * 8.1 树的相关概念和术语 家族关系示意图/单位机构组成示意图 定义：树T是由n个结点组成的有限集合（n 0）。 其中有一个根结点， 其余结点可划分成m个（m=0）互不相交的子集 T1, T2, ... ,Tm， 且这些子集也分别构成树—T的子树。 （注意：有无空树的概念） * 8.1 树的相关概念和术语 术语 关系术语 孩子结点 —— 子树的根 父结点 兄弟结点 —— 同一个结点的孩子结点互为兄弟 祖先结点 后代结点 层次类术语 根的层次为1 其余结点的层次为其父结点层次加1 高度/深度 —— 整个树中结点的最大层次 度 —— 结点的孩子数目称为结点的度 叶子（终结点）—— 度为0 分支结点----度不为0的结点（非叶子结点） 树的度 —— 最大的结点度 森林 —— 多棵树 有序树/无序树 ——按照兄弟结点之间的排列是否有序 * 8.1 树的相关概念和术语 树的表示形式 图形表示，即前面所示的自然界中的“树”的形式 目录形式：书的目录，资源管理器中的表示 嵌套集合表示 广义表形式 A(B(E(K,L),F),C(G),D(H(M),I,J)) 8.1 树的相关概念和术语 运算 （1）初始化 （2）查找 —— 结点的父、兄弟、祖先、后代、根 （3）插入 —— 叶子， 子树 （4）删除 —— 叶子，子树 树的存储？ * * 8.2 二叉树的定义、性质和存储结构 8.2.1定义 二叉树T：是n个结点组成的有限集合（n = 0）， n=0时为空二叉树， 否则：其中有一个根结点， 其余结点可以划分成两个互不相交的子集TL, TR， 且TL, TR也分别构成二叉树 —— 左、右子树。 A G F E D C B * 8.2 二叉树的定义、性质和存储结构 二叉树与树的区别： 是两种不同性质的结构； 比较三个结点的树与二叉树，各有几种不同的形态。 三个结点的树 三个结点的二叉树 A A B B C C A A A A A B B B B B C C C C C * 8.2 二叉树的定义、性质和存储结构 由定义可知，依据结点数的多少可将二叉树划分为五种不同的形态： （1）空树，即结点数为0 （2）单结点二叉树，即仅有一个结点 （3）左子树为空右子树不空 （4）右子树为空左子树不空 （5）左右子树均不空 * 8.2 二叉树的定义、性质和存储结构 8.2.2二叉树的性质 性质1：第i层的结点数≤2i-1； 性质2：高度为k（k≥1）的二叉树的结点总数≤2k-1； 性质3：设二叉树的叶子结点数为n0，度为2的结点数为n2，则 n0=n2+1。 证明：设总结点数为n，度为1的结点数为n1，则 n=n0+n1+n2 ——结点数 （1） n-1=n1+2n2 ——分支数 （2） 式（1）－（2）得 n0=n2+1 课堂练习：已知一棵二叉树中，有20个叶子结点，10个结点只有左孩子，15个结点只有右孩子，求该二叉树的总结点数。 * 8.2 二叉树的定义、性质和存储结构 定义1：称高度为k且有2k-1个结点的二叉树为满二叉树。 例如，高度为1~4的满二叉树如下。 A B C G F E D A N O A B C G F E H I D K J M L C B A (a) 高度为1的满二叉树 (b) 高度为2的满二叉树 (c) 高度为3的满二叉树 (d) 高度为4的满二叉树 * 8.2 二叉树的定义、性质和存储结构 定义2：称在满二叉树最下一层从右到左依次连续去掉若干个结点所得到的二叉树为完全二叉树。 下面分别给出完全二叉树和非完全二叉树的示例。 A B C G F E H I D K J M L (a) 完全二叉树示例 M N A B C G F E H I D K J L (b) 非完全二叉树示例 O N 8.2 二叉树的定义、性质和存储结构 定义3：平衡二叉树(AV