数据结构_char6(第六章树).ppt

第6章 树和二叉树（Tree Binary Tree） 6.1 树6.1.1 树的定义 6.1.2 若干术语 6.1.3 树的抽象数据类型 6.1.4　树的存储结构 树的结点之间的逻辑关系主要有双亲-孩子关系，兄弟关系。因此，从结点之间的逻辑关系分，树的存储结构主要有：双亲表示法、孩子表示法、双亲孩子表示法和孩子兄弟表示法四种组合。 2. 孩子表示法 孩子表示法主要描述的是结点的孩子关系。由于每个结点的孩子个数不定，所以利用链式存储结构更加适宜。 图 在C语言中，这种存储形式定义如下： #define MAXNODE 树中结点的最大个数 typedef struct ChildNode{ int childcode; struct ChildNode *nextchild; } typedef struct { elemtype data; struct ChildNode *firstchild; }NodeType; NodeType t[MAXNODE]; 补充：树的5种表示法： 图形表示法 6.2 二叉树 为何要重点研究每结点最多只有两个 “叉” 的树？ 二叉树的结构最简单，规律性最强； 可以证明，所有树都能转为唯一对应的二叉树，不失一般性。 6.2.1　二叉树的定义 二、满二叉树 　　在一棵二叉树中，如果所有分支结点都 存在左子树和右子树，并且所有叶子结点都 在同一层上，这样的二叉树称为满二叉树。 (一棵深度为k((k≥0)且有2k-1个结点的 二叉树称为满二叉树。) 三、完全二叉树 图6.4 　　如果一棵深度为k，有n个结点的二叉树 中各结点能够与深度为k的顺序编号的满二叉 树从1到n标号的结点相对应的二叉树称为完 全二叉树。 特点: (1)所有的叶结点都出现在第k层或k－1层。 图6.5 (2)若任一结点，如果其右子树的最大层次为i，则其左子树的 最大层次为i或i＋1。 设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为（ ） A．5 B．6 C．7 D．8 三、满二叉树与完全二叉树的区别 　　　满二叉树是叶子一个也不少的树，而完全二叉树虽然前k-1层是满的，但最底层却允许在右边缺少连续若干个结点。满二叉树是完全二叉树的一个特例。 四、为何要研究这两种特殊形式？ 　　　因为它们在顺序存储方式下可以复原。 6.2.2 二叉树的抽象数据类型 6.2.3　二叉树的性质 小结 6.1 树的基本概念 6.2 二叉树 二叉树的概念 两种特殊的二叉树 二叉树的性质 性质3: 对于任何一棵非空的二叉树，若度为2的结点数有n2个，则叶子数（n0）必定为n2＋1 （即n0=n2+1） 证明： ∵ 二叉树中全部结点数n＝n0+n1+n2(叶子数＋1度结点数＋2度结点数) 又∵二叉树中全部结点数n＝B+1 ( 总分支数＋根结点 ) （除根结点外，每个结点必有一个直接前趋，即一个分支） 而 总分支数B= n1+2n2 (1度结点必有1个直接后继，2度结点必有2个) 三式联立可得： n0+n1+n2= n1+2n2 +1, 即n0=n2+1 叶子数＝2度结点数＋1 讨论3：二叉树的叶子数和度为2的结点数之间有关系吗？ 性质4: 具有n个结点的完全二叉树的深度k必为?log2n? ＋1 (假定k为0时表示此二叉树仅有根结点） 证明：根据性质2，深度为k的二叉树最多只有2k-1个结点，且完全二叉树的定义是与同深度的满二叉树前面编号相同，即它的总结点数n位于k层和k-1层满二叉树容量之间， 即 2(k-1)-1n≤2k-1，移项，有 2k－1 ≤ n 2k 对不等式求对数，有 k－1≤log2 nk+1 因为k是整数，所以k=?log2n? ＋1 对于两种特殊形式的二叉树（满二叉树和完全二叉树），还特别具备以下2个性质： 性质5:对于一棵有n个结点的完全二叉树的结点按照从上至下和从左至右的顺序对所有结点从1开始顺序编号,则对于序号为i的结点(1≤i≤n),有： (1)如果i=1，则结点i无双亲，是二叉树的根；如果i1，则其双亲是结点 i/2(“/”表示整除）。 (2)如果2i n，则结点i为叶子结点，无左孩子；否则，其左孩子是结点2