《树与二叉树整》PPT课件.ppt

第第6 6章章 树与二叉树树与二叉树 树树树树 (tree)(tree)结结结结构构构构是是是是一一一一种种种种多多多多分分分分支支支支多多多多层层层层次次次次的的的的数数数数据据据据结结结结构构构构，由由由由一一一一组组组组结结结结点点点点组组组组成成成成。由由由由于于于于它它它它呈呈呈呈现现现现与与与与自自自自然然然然界界界界树树树树类类类类似似似似的的的的结结结结构构构构形形形形式式式式，所所所所以以以以称称称称之之之之为为为为树树树树。在在在在许许许许多多多多算算算算法法法法中中中中，常常常常用用用用树树树树型型型型结结结结构构构构描描描描述述述述问题的求解过程或表示求解的对策等。问题的求解过程或表示求解的对策等。问题的求解过程或表示求解的对策等。问题的求解过程或表示求解的对策等。树的逻辑结构树的逻辑结构6.1 树树2树的存储结构树的存储结构 树树树树是是是是由由由由 n n (n n0)0)个个个个结结结结点点点点组组组组成成成成的的的的有有有有限限限限集集集集。在在在在任任任任意意意意一一一一棵棵棵棵非空树非空树非空树非空树 T T 中：中：中：中：有且仅有一个特定的称为有且仅有一个特定的称为有且仅有一个特定的称为有且仅有一个特定的称为根根根根(root)(root)结点；结点；结点；结点；当当当当 n n1 1 时时时时，其其其其余余余余结结结结点点点点分分分分成成成成 mm (mm0)0)个个个个互互互互不不不不相相相相交交交交的的的的有有有有限限限限集集集集T T1 1，T T2 2，T Tmm，其其其其中中中中每每每每一一一一个个个个集集集集合合合合本本本本身身身身又又又又都都都都是是是是一一一一棵树，并且称为根的棵树，并且称为根的棵树，并且称为根的棵树，并且称为根的子树子树子树子树。36.1.1 树的逻辑结构树的逻辑结构 1.1.树的定义树的定义树的定义树的定义42.2.树的基本操作树的基本操作树的基本操作树的基本操作 InitTree(tree);InitTree(tree);操作结果：构造空树操作结果：构造空树操作结果：构造空树操作结果：构造空树 TreeTree。InsertChild(Tree,p,child);InsertChild(Tree,p,child);初始条件：树初始条件：树初始条件：树初始条件：树 TreeTree 存在，存在，存在，存在，p p 指向指向指向指向 TreeTree 中某个结点，中某个结点，中某个结点，中某个结点，11i i p p 所所所所指指指指结结结结点点点点的的的的度度度度+1+1，非非非非空空空空树树树树 childchild 与与与与TreeTree 不相交。不相交。不相交。不相交。操作结果：插入操作结果：插入操作结果：插入操作结果：插入childchild为为为为 T T 中中中中 p p 所指结点的子所指结点的子所指结点的子所指结点的子树。树。树。树。树结构中经常会用到一些基本术语。例如：树结构中经常会用到一些基本术语。例如：树结构中经常会用到一些基本术语。例如：树结构中经常会用到一些基本术语。例如：结点结点结点结点结点的度结点的度结点的度结点的度叶结点叶结点叶结点叶结点分支结点分支结点分支结点分支结点树的度树的度树的度树的度双亲及孩子双亲及孩子双亲及孩子双亲及孩子兄弟兄弟兄弟兄弟堂兄弟堂兄弟堂兄弟堂兄弟祖先祖先祖先祖先子孙子孙子孙子孙层次层次层次层次树的深度树的深度树的深度树的深度有序树有序树有序树有序树无序树无序树无序树无序树森林森林森林森林5 3.3.树的基本概念树的基本概念树的基本概念树的基本概念66.1.2 树的存储结构树的存储结构 假假假假设设设设以以以以一一一一组组组组连连连连续续续续空空空空间间间间存存存存储储储储树树树树的的的的结结结结点点点点，同同同同时时时时在在在在每每每每个个个个结结结结点点点点中中中中附附附附设设设设一一一一个个个个指指指指示示示示器器器器指指指指示示示示其其其其双双双双亲亲亲亲结结结结点点点点在在在在连连连连续续续续空空空空间间间间中中中中的的的的位位位位置。置。置。置。typedef struct typedef struct /双亲表示结构定义双亲表示结构定义双亲表示结构定义双亲表示结构定义 TNode TNode treeMAX;treeMAX;/结点数组结点数组结点数组结点数组 int int nodenum;nodenum;/结点数结点数结点数结点数 ParentTree;ParentTree;/双亲表示结构类型名双亲表示结构类型名双亲表示结构类型名双亲表示结构类型名#define Max 100#define Max 100 typedef struct TNode typedef struct TNode /结点结构定义结点结构定义结点结构定义结点结构定义 DataType DataTypedata;data;/数据域数据域数据域数据域 int intparent;parent;/双亲位置域双亲位置域双亲位置域双亲位置域 TNode;TNode;1.1.双亲表示法双亲表示法双亲表示法双亲表示法7R RA AB BC CD DE EF FG GHHK K树树树树R R-1-1A A0 0B B0 0C C0 0D D1 1E E1 1F F3 3G G6 6HH6 6K K6 6数组下标数组下标数组下标数组下标0 01 12 23 34 45 56 67 78 89 9双亲存储结构双亲存储结构双亲存储结构双亲存储结构 树树树树的的的的双双双双亲亲亲亲表表表表示示示示存存存存储储储储结结结结构构构构利利利利用用用用了了了了每每每每个个个个结结结结点点点点（根根根根结结结结点点点点除除除除外外外外）只只只只有惟一双亲的性质。有惟一双亲的性质。有惟一双亲的性质。有惟一双亲的性质。在在在在树树树树的的的的双双双双亲亲亲亲存存存存储储储储结结结结构构构构中中中中，求求求求双双双双亲亲亲亲 Parent(T,Parent(T,x)x)操操操操作作作作非非非非常常常常方方方方便便便便。求求求求树树树树根根根根结结结结点点点点 Root(x)Root(x)操操操操作作作作也也也也很很很很简简简简单单单单：反反反反复复复复调调调调用用用用 Parent Parent 操操操操作作作作，直直直直到到到到遇遇遇遇见见见见无无无无双双双双亲亲亲亲的的的的结结结结点点点点时时时时，即即即即 T T.parent.parent=-1-1 时时时时，便便便便找找找找到到到到了了了了惟惟惟惟一一一一的的的的无双亲的根结点。无双亲的根结点。无双亲的根结点。无双亲的根结点。在在在在树树树树的的的的双双双双亲亲亲亲存存存存储储储储结结结结构构构构中中中中，求求求求某某某某结结结结点点点点的的的的孩孩孩孩子子子子结结结结点点点点时时时时需需需需遍遍遍遍历历历历整整整整个个个个结结结结构构构构。例例例例如如如如求求求求树树树树中中中中结结结结点点点点 F F 的的的的孩孩孩孩子子子子，就就就就需需需需要要要要在在在在整整整整个个个个结结结结构构构构中中中中 从从从从 头头头头 到到到到 尾尾尾尾 扫扫扫扫 描描描描 一一一一 遍遍遍遍 T T.parent.parent 域域域域，T T.parent.parent=6 6 的的的的结结结结点点点点 G G、HH、K K 就就就就是是是是结结结结点点点点 F F 的孩子。的孩子。的孩子。的孩子。由由由由于于于于树树树树中中中中每每每每个个个个结结结结点点点点可可可可能能能能有有有有多多多多棵棵棵棵子子子子树树树树，则则则则可可可可以以以以用用用用多多多多重重重重链链链链表表表表，即即即即每每每每个个个个结结结结点点点点有有有有多多多多个个个个指指指指针针针针域域域域，其其其其中中中中每每每每个个个个指指指指针针针针指指指指向向向向一一一一棵棵棵棵子子子子树树树树的的的的根根根根结结结结点点点点，此此此此时时时时，链链链链表表表表中中中中的的的的结结结结点点点点可可可可以以以以有有有有如如如如下下下下 3 3 种种种种结构格式：结构格式：结构格式：结构格式：8同构结点格式同构结点格式同构结点格式同构结点格式不同构结点格式不同构结点格式不同构结点格式不同构结点格式单链表存储结构单链表存储结构单链表存储结构单链表存储结构 2.2.孩子表示法孩子表示法孩子表示法孩子表示法 (1)(1)同构结点格式。同构结点格式。同构结点格式。同构结点格式。即多重链表中的结点是同构的。即多重链表中的结点是同构的。即多重链表中的结点是同构的。即多重链表中的结点是同构的。datadatachildchild1 1childchild2 2childchildd d 其其其其中中中中 d d 为为为为树树树树的的的的度度度度。由由由由于于于于树树树树中中中中很很很很多多多多结结结结点点点点的的的的度度度度都都都都小小小小于于于于 d d，所以链表中有很多空链域，空间比较浪费。，所以链表中有很多空链域，空间比较浪费。，所以链表中有很多空链域，空间比较浪费。，所以链表中有很多空链域，空间比较浪费。9 设设设设树树树树的的的的度度度度为为为为 k k，结结结结点点点点数数数数为为为为 n n。若若若若采采采采用用用用同同同同构构构构结结结结点点点点格格格格式式式式，每每每每个个个个结结结结点点点点具具具具有有有有 k k 个个个个固固固固定定定定链链链链域域域域，那那那那么么么么共共共共有有有有 nknk 个个个个链链链链域域域域。由由由由于于于于 n n 个个个个结结结结点点点点要要要要有有有有 (n n -1)1)个个个个枝枝枝枝相相相相连连连连，而而而而每每每每枝枝枝枝需需需需要要要要 1 1 个个个个链链链链域域域域。因此，这棵树的空链域的个树为：因此，这棵树的空链域的个树为：因此，这棵树的空链域的个树为：因此，这棵树的空链域的个树为：n n(k k 1)+1 1)+1。由由由由此此此此可可可可知知知知，树树树树的的的的度度度度越越越越大大大大，空空空空链链链链域域域域越越越越多多多多。如如如如果果果果采采采采用用用用同同同同构结点格式将造成空间的极大浪费。构结点格式将造成空间的极大浪费。构结点格式将造成空间的极大浪费。构结点格式将造成空间的极大浪费。(2)(2)不不不不同同同同构构构构结结结结点点点点格格格格式式式式。即即即即多多多多重重重重链链链链表表表表中中中中的的的的结结结结点点点点是是是是不不不不同同同同构的。构的。构的。构的。degreedegree childchild1 1childchild2 2childchildd ddatadata 其中其中其中其中种种种种存存存存储储储储结结结结构构构构避避免免了了孩孩子子表表示示法法存存储储结结构构中中出出现现的的空空链链域域，节节约约存存储储空空间间。但但是是由由于于每每个个结结点点的的孩孩子子链链域域数数不同，所以在这种结构上进行的各种操作不易实现。不同，所以在这种结构上进行的各种操作不易实现。为结点的度，为结点的度，为结点的度，为结点的度，degree degree 域的值和域的值和域的值和域的值和 d d相同。这相同。这相同。这相同。这10d d (3)(3)单单单单链链链链表表表表存存存存储储储储结结结结构构构构。即即即即把把把把每每每每个个个个结结结结点点点点的的的的孩孩孩孩子子子子结结结结点点点点排排排排列列列列起起起起来来来来，看看看看成成成成是是是是一一一一个个个个线线线线性性性性表表表表，且且且且以以以以单单单单链链链链表表表表作作作作为为为为存存存存储储储储结结结结构构构构，则则则则 n n 个个个个结结结结点点点点有有有有 n n 个个个个孩孩孩孩子子子子链链链链表表表表（叶叶叶叶子子子子结结结结点点点点的的的的孩孩孩孩子子子子链链链链表表表表为为为为空空空空表表表表）。而而而而 n n 个个个个头头头头指指指指针针针针又又又又组组组组成成成成一一一一个个个个线线线线性性性性表表表表，为为为为了了了了便于查找，可以采用顺序存储结构。便于查找，可以采用顺序存储结构。便于查找，可以采用顺序存储结构。便于查找，可以采用顺序存储结构。11R RA AB BC CD DE EF FG GHHk k树树树树A AB BC CD DR RE EF FG GHHK K3 35 5 6 6 0 01 12 2 7 78 89 9 0 01 12 23 34 45 56 67 78 89 9根位置根位置根位置根位置12 与与与与树树树树的的的的双双双双亲亲亲亲表表表表示示示示法法法法相相相相反反反反，树树树树的的的的孩孩孩孩子子子子单单单单链链链链表表表表表表表表示示示示法法法法便便便便于于于于查查查查找找找找树树树树中中中中任任任任一一一一结结结结点点点点的的的的孩孩孩孩子子子子：由由由由链链链链表表表表中中中中某某某某结结结结点点点点的的的的指指指指针针针针域域域域 next next 即即即即可可可可以以以以得得得得到到到到该结点的孩子结点。该结点的孩子结点。该结点的孩子结点。该结点的孩子结点。在在在在树树树树的的的的孩孩孩孩子子子子单单单单链链链链表表表表结结结结构构构构中中中中，查查查查找找找找某某某某结结结结点点点点的的的的双双双双亲亲亲亲需需需需要要要要按按按按照照照照该该该该结结结结点点点点在在在在头头头头结结结结点点点点顺顺顺顺序序序序表表表表中中中中的的的的位位位位置置置置序序序序号号号号在在在在每每每每个个个个孩孩孩孩子子子子链链链链表表表表中中中中扫扫扫扫描描描描，当当当当在在在在孩孩孩孩子子子子域域域域 child child 中中中中找找找找到到到到相相相相同同同同的的的的序序序序号号号号时时时时，则则则则单单单单链链链链表表表表表表表表头头头头的的的的结结结结点点点点就就就就是是是是要找的双亲。要找的双亲。要找的双亲。要找的双亲。例例例例如如如如，要要要要寻寻寻寻找找找找树树树树中中中中 G G 结结结结点点点点的的的的双双双双亲亲亲亲结结结结点点点点。G G 结结结结点点点点在在在在头头头头结结结结点点点点顺顺顺顺序序序序表表表表中中中中的的的的位位位位置置置置序序序序号号号号为为为为 7 7，则则则则在在在在孩孩孩孩子子子子链链链链表表表表中中中中查查查查询询询询 child child=7 7 的的的的孩孩孩孩子子子子结结结结点点点点，当当当当找找找找到到到到的的的的时时时时候候候候，该该该该单单单单链链链链表表表表的的的的表表表表头头头头结结结结点点点点 F F 就是就是就是就是 G G 的双亲结点。的双亲结点。的双亲结点。的双亲结点。树树树树的的的的孩孩孩孩子子子子兄兄兄兄弟弟弟弟表表表表示示示示法法法法又又又又称称称称二二二二叉叉叉叉树树树树表表表表示示示示法法法法，或或或或二二二二叉叉叉叉链链链链表表表表表表表表示示示示法法法法，即即即即以以以以二二二二叉叉叉叉链链链链表表表表作作作作为为为为树树树树的的的的存存存存储储储储结结结结构构构构。链链链链表表表表中中中中每每每每个个个个结结结结点点点点的的的的结结结结构构构构相相相相同同同同，都都都都有有有有 3 3 个个个个域域域域：数数数数据据据据域域域域 data data 存存存存放放放放树树树树中中中中结结结结点点点点的的的的信信信信息息息息；孩孩孩孩子子子子域域域域 firstchild firstchild 存存存存放放放放该该该该结结结结点点点点的的的的第第第第一一一一个个个个孩孩孩孩子子子子结结结结点点点点（从从从从左左左左算算算算起起起起）的的的的地地地地址址址址；兄兄兄兄弟弟弟弟域域域域 nextsibling nextsibling 存存存存放放放放该该该该结结结结点的下一个兄弟结点（从左向右）的地址。点的下一个兄弟结点（从左向右）的地址。点的下一个兄弟结点（从左向右）的地址。点的下一个兄弟结点（从左向右）的地址。133.3.孩子兄弟表示法孩子兄弟表示法孩子兄弟表示法孩子兄弟表示法R RA AB BC CD DE EF FG GHHK K树树树树R R A AD DE E B BC C F F G GHHK K 14 树树树树的的的的二二二二叉叉叉叉链链链链表表表表存存存存储储储储结结结结构构构构的的的的最最最最大大大大优优优优点点点点就就就就是是是是结结结结点点点点的的的的结结结结构构构构统统统统一一一一，和和和和前前前前面面面面讲讲讲讲的的的的二二二二叉叉叉叉树树树树表表表表示示示示法法法法完完完完全全全全一一一一样样样样，因因因因此此此此可可可可以以以以利利利利用用用用二二二二叉叉叉叉树树树树的的的的算算算算法法法法来来来来实实实实现现现现对对对对树树树树的操作。的操作。的操作。的操作。在在在在树树树树的的的的二二二二叉叉叉叉链链链链表表表表存存存存储储储储结结结结构构构构中中中中，易易易易于于于于实实实实现现现现找找找找结结结结点点点点等等等等的的的的操操操操作作作作。如如如如果果果果要要要要访访访访问问问问树树树树中中中中结结结结点点点点 x x 的的的的第第第第 i i 个个个个孩孩孩孩子子子子，那那那那么么么么 只只只只 需需需需 要要要要 先先先先 从从从从 该该该该 结结结结 点点点点 的的的的 firstchild firstchild 域域域域找找找找到到到到第第第第 1 1 个个个个孩孩孩孩子子子子结结结结点点点点，然然然然后后后后再再再再沿沿沿沿孩孩孩孩子子子子结结结结点点点点的的的的 nextsibling nextsibling 域域域域连连连连续续续续走走走走 i i-1-1 步步步步，便便便便可可可可以以以以找找找找到到到到结结结结点点点点 x x 的第的第的第的第 i i 个孩子。个孩子。个孩子。个孩子。例例例例如如如如，要要要要访访访访问问问问 F F 结结结结点点点点的的的的第第第第 3 3 个个个个孩孩孩孩子子子子，只只只只要要要要先先先先从从从从 F F 结结结结点点点点的的的的 Firstchild Firstchild 域域域域找找找找到到到到第第第第一一一一个个个个孩孩孩孩子子子子 G G 结结结结点点点点后后后后，再再再再沿沿沿沿着着着着 G G 结结结结点点点点的的的的 Nextsibling Nextsibling 域域域域连连连连续续续续走走走走 2 2 步步步步，找找找找到到到到 K K 结结结结点点点点，这这这这就就就就是是是是 F F 结结结结点点点点的的的的第第第第 3 3 个个个个孩孩孩孩子子子子结结结结点点点点。但但但但是是是是，在在在在这这这这个个个个结结结结构构构构上上上上查查查查找找找找某某某某结结结结点点点点的的的的双双双双亲亲亲亲结结结结点点点点不不不不是是是是很很很很方方方方便便便便，若若若若为为为为每每每每个个个个结结结结点点点点再再再再增增增增设设设设一一一一个个个个双双双双亲亲亲亲 parent parent 域域域域，则则则则查查查查找找找找某某某某结结结结点的双亲的操作也很方便。点的双亲的操作也很方便。点的双亲的操作也很方便。点的双亲的操作也很方便。二二二二叉叉叉叉树树树树 (binary(binary tree)tree)是是是是另另另另一一一一种种种种树树树树型型型型结结结结构构构构，它它它它的的的的特特特特点点点点是是是是每每每每个个个个结结结结点点点点至至至至多多多多只只只只有有有有两两两两棵棵棵棵子子子子树树树树（即即即即二二二二叉叉叉叉树树树树中中中中不不不不存存存存在在在在度度度度大大大大于于于于 2 2 的的的的结结结结点点点点），并并并并且且且且，二二二二叉叉叉叉树树树树的的的的子子子子树树树树有有有有左左左左右右右右之之之之分分分分，其其其其次次次次序不能任意颠倒。序不能任意颠倒。序不能任意颠倒。序不能任意颠倒。二叉树的逻辑结构二叉树的逻辑结构6.2 二叉树二叉树15二叉树的基本性质二叉树的基本性质二叉树的存储结构二叉树的存储结构 二二二二叉叉叉叉树树树树是是是是一一一一个个个个有有有有限限限限的的的的结结结结点点点点的的的的集集集集合合合合，该该该该集集集集合合合合或或或或者者者者为为为为空空空空，或或或或者者者者由由由由一一一一个个个个根根根根结结结结点点点点加加加加上上上上两两两两棵棵棵棵分分分分别别别别称称称称为为为为左左左左子子子子树树树树和和和和右右右右子子子子树树树树的的的的、互不相交的二叉树组成。互不相交的二叉树组成。互不相交的二叉树组成。互不相交的二叉树组成。16 二二二二叉叉叉叉树树树树定定定定义义义义是是是是一一一一个个个个递递递递归归归归定定定定义义义义，即即即即在在在在二二二二叉叉叉叉树树树树的的的的定定定定义义义义中中中中又用到二叉树的概念。又用到二叉树的概念。又用到二叉树的概念。又用到二叉树的概念。6.2.1 二叉树的逻辑结构二叉树的逻辑结构 1.1.二叉树的定义二叉树的定义二叉树的定义二叉树的定义 性性性性质质质质1 1：在在在在二二二二叉叉叉叉树树树树的的的的第第第第 i i 层层层层上上上上至至至至多多多多有有有有 2 2i i-1-1 个个个个结结结结点点点点（i i11）。）。）。）。证明：利用归纳法容易证得此性质。证明：利用归纳法容易证得此性质。证明：利用归纳法容易证得此性质。证明：利用归纳法容易证得此性质。i i=1 =1 时，只有一个根结点。时，只有一个根结点。时，只有一个根结点。时，只有一个根结点。2 2i i-1-1=2=20 0=1=1，命题成立。，命题成立。，命题成立。，命题成立。假假假假定定定定对对对对所所所所有有有有的的的的 j j (1(1j ji i)，命命命命题题题题成成成成立立立立，即即即即第第第第 j j 层层层层上上上上至至至至多有多有多有多有 2 2 j j-1-1 个结点。那么，可以证明个结点。那么，可以证明个结点。那么，可以证明个结点。那么，可以证明 j j=i i 时命题也成立。时命题也成立。时命题也成立。时命题也成立。根根根根据据据据归归归归纳纳纳纳假假假假设设设设，第第第第 i i-1-1 层层层层上上上上至至至至多多多多有有有有 2 2i i-2-2 个个个个结结结结点点点点。由由由由于于于于二二二二叉叉叉叉树树树树的的的的每每每每个个个个结结结结点点点点的的的的度度度度最最最最多多多多为为为为 2 2，所所所所以以以以在在在在第第第第 i i 层层层层上上上上最最最最多多多多的的的的结点数为第结点数为第结点数为第结点数为第 i i-1-1 层上的层上的层上的层上的 2 2 倍，即倍，即倍，即倍，即 22 22i i-2-2=2=2i i-1-1。176.2.2 二叉树的基本性质二叉树的基本性质 性性性性质质质质2 2：深深深深度度度度为为为为 k k 的的的的二二二二叉叉叉叉树树树树至至至至多多多多有有有有 2 2k k1 1 个个个个结结结结点点点点（k k11）。）。）。）。=2=2k k1 118 证明：证明：证明：证明：由性质由性质由性质由性质1 1 可见，深度为可见，深度为可见，深度为可见，深度为 k k 的二叉树的最大结点数为的二叉树的最大结点数为的二叉树的最大结点数为的二叉树的最大结点数为 性性性性质质质质3 3：对对对对任任任任何何何何一一一一棵棵棵棵二二二二叉叉叉叉树树树树 T T，如如如如果果果果其其其其终终终终端端端端结结结结点点点点数数数数为为为为 n n0 0，度为，度为，度为，度为 2 2 的结点数为的结点数为的结点数为的结点数为 n n2 2，则，则，则，则 n n0 0 n n2 2+1+1。19 证明：证明：证明：证明：(1)(1)设设设设 n n1 1 为为为为二二二二叉叉叉叉树树树树 T T 中中中中度度度度为为为为 1 1 的的的的结结结结点点点点数数数数。n n 为为为为二二二二叉叉叉叉树树树树中中中中总总总总结结结结点点点点数数数数。因因因因为为为为二二二二叉叉叉叉树树树树中中中中所所所所有有有有结结结结点点点点的的的的度度度度均均均均小小小小于于于于或或或或等等等等于于于于 2 2，则：，则：，则：，则：n n=n n0 0+n n1 1+n n2 2 。(2)(2)设设设设 B B 为二叉树为二叉树为二叉树为二叉树 T T 中的分支总数。中的分支总数。中的分支总数。中的分支总数。从从从从入入入入支支支支的的的的角角角角度度度度看看看看，二二二二叉叉叉叉树树树树中中中中除除除除了了了了根根根根结结结结点点点点外外外外，其其其其余余余余结结结结点都有一个且仅有一个入支，则：点都有一个且仅有一个入支，则：点都有一个且仅有一个入支，则：点都有一个且仅有一个入支，则：n n=B B+1+1。从从从从出出出出支支支支的的的的角角角角度度度度看看看看，度度度度为为为为 1 1 的的的的结结结结点点点点只只只只有有有有一一一一个个个个出出出出支支支支，度度度度为为为为 2 2 的结点有两个出支，则：的结点有两个出支，则：的结点有两个出支，则：的结点有两个出支，则：B B=n n1 1+2+2n n2 2 故：故：故：故：n n=n n1 1+2+2n n2 2+1+1；最后得到：；最后得到：；最后得到：；最后得到：n n0 0=n n2 2+1+1。为为为为便便便便于于于于介介介介绍绍绍绍下下下下面面面面两两两两个个个个二二二二叉叉叉叉树树树树性性性性质质质质，先先先先了了了了解解解解满满满满二二二二叉叉叉叉树树树树 (full(full binary binary tree)tree)和和和和完完完完全全全全二二二二叉叉叉叉树树树树 (complete(complete binary binary tree)tree)的概念。的概念。的概念。的概念。20 满满满满二二二二叉叉叉叉树树树树的的的的特特特特点点点点是是是是：每每每每一一一一层层层层上上上上的的的的结结结结点点点点数数数数都都都都达达达达到到到到最最最最大大大大值值值值；满满满满二二二二叉叉叉叉树树树树中中中中只只只只有有有有度度度度为为为为 0 0 和和和和度度度度为为为为 2 2 的的的的结结结结点点点点，不不不不存存存存在在在在度度度度为为为为 1 1 的的的的结结结结点点点点；每每每每一一一一个个个个结结结结点点点点均均均均有有有有两两两两棵棵棵棵高高高高度度度度相相相相同同同同的的的的子子子子树树树树，叶叶叶叶子结点都在树的最下面的同一层上。子结点都在树的最下面的同一层上。子结点都在树的最下面的同一层上。子结点都在树的最下面的同一层上。满满满满二二二二叉叉叉叉树树树树：一一一一棵棵棵棵深深深深度度度度为为为为 k k 并并并并且且且且有有有有 2 2k k-1 1 个个个个结结结结点点点点的的的的二二二二叉叉叉叉树，称之为满二叉树。树，称之为满二叉树。树，称之为满二叉树。树，称之为满二叉树。如如如如果果果果对对对对满满满满二二二二叉叉叉叉树树树树的的的的结结结结点点点点进进进进行行行行编编编编号号号号，约约约约定定定定编编编编号号号号从从从从根根根根结结结结点点点点起起起起，自自自自上上上上而而而而下下下下，自自自自左左左左至至至至右右右右。由由由由此此此此可可可可以以以以引引引引出出出出完完完完全全全全二二二二叉叉叉叉树树树树的定义。的定义。的定义。的定义。完完完完全全全全二二二二叉叉叉叉树树树树的的的的特特特特点点点点是是是是：二二二二叉叉叉叉树树树树中中中中的的的的叶叶叶叶子子子子结结结结点点点点只只只只可可可可能能能能出出出出现现现现在在在在二二二二叉叉叉叉树树树树中中中中层层层层次次次次最最最最大大大大的的的的两两两两层层层层上上上上；最最最最下下下下一一一一层层层层的的的的结结结结点点点点一一一一定定定定是是是是从从从从最最最最左左左左边边边边开开开开始始始始向向向向右右右右放放放放的的的的；并并并并且且且且若若若若某某某某个个个个结结结结点点点点没没没没有有有有左左左左孩孩孩孩子，则它一定没有右孩子。子，则它一定没有右孩子。子，则它一定没有右孩子。子，则它一定没有右孩子。21 完完完完全全全全二二二二叉叉叉叉树树树树：一一一一棵棵棵棵深深深深度度度度为为为为 k k 并并并并且且且且有有有有 n n 个个个个结结结结点点点点的的的的二二二二叉叉叉叉树树树树，当当当当且且且且仅仅仅仅当当当当其其其其每每每每一一一一个个个个结结结结点点点点都都都都与与与与深深深深度度度度为为为为 k k 的的的的满满满满二二二二叉叉叉叉树树树树中中中中编号从编号从编号从编号从 1 1 至至至至 n n 的结点一一对应时，称之为完全二叉树。的结点一一对应时，称之为完全二叉树。的结点一一对应时，称之为完全二叉树。的结点一一对应时，称之为完全二叉树。性质性质性质性质4 4：具有：具有：具有：具有 n n 个结点的完全二叉树的深度为个结点的完全二叉树的深度为个结点的完全二叉树的深度为个结点的完全二叉树的深度为 loglog2 2n n +1 +1 （x x 表示不大于表示不大于表示不大于表示不大于 x x 的最大整数）的最大整数）的最大整数）的最大整数）22 证明：证明：证明：证明：设设设设所所所所求求求求完完完完全全全全二二二二叉叉叉叉树树树树深深深深度度度度为为为为 k k，则则则则它它它它的的的的前前前前 k k-1-1 层层层层可可可可视视视视为为为为深深深深度度度度为为为为 k k-1-1 的的的的满满满满二二二二叉叉叉叉树树树树，共共共共有有有有 2 2k k-1-1-1 1 个个个个结结结结点点点点，故故故故该该该该完完完完全二叉树的总结点数全二叉树的总结点数全二叉树的总结点数全二叉树的总结点数 n n 一定满足式子：一定满足式子：一定满足式子：一定满足式子：n n2 2k k-1-1-1 1。根据性质根据性质根据性质根据性质 2 2，可以确定：，可以确定：，可以确定：，可以确定：n n 2 2k k-1 1 由此得到：由此得到：由此得到：由此得到：2 2k k-1-1-1 1n n2 2k k-1 1 或或或或 2 2k k-1-1 n n2 2k k 等价关系：等价关系：等价关系：等价关系：k k-1 1loglog2 2n nk k因为因为因为因为 k k 是整数，所以是整数，所以是整数，所以是整数，所以 k k-1=-1=loglog2 2n n ，即，即，即，即 k k=loglog2 2n n +1+1 性性性性质质质质5 5：如如如如果果果果对对对对一一一一棵棵棵棵有有有有 n n 个个个个结结结结点点点点的的的的完完完完全全全全二二二二叉叉叉叉树树树树（此此此此二二二二叉叉叉叉树树树树的的的的深深深深度度度度为为为为 loglog2 2n n +1+1）的的的的结结结结点点点点按按按按照照照照层层层层次次次次编编编编号号号号（从从从从第第第第 1 1 层层层层到到到到第第第第 loglog2 2n n +1+1 层层层层，每每每每层层层层从从从从左左左左到到到到右右右右），那那那那么么么么对对对对任任任任一一一一结结结结点点点点 i i（1 1 i i n n），有），有），有），有23 (1)(1)若若若若 i i =1 1，则则则则结结结结点点点点 i i 是是是是二二二二叉叉叉叉树树树树的的的的根根根根，没没没没有有有有双双双双亲亲亲亲结结结结点点点点；若若若若 i i 1 1，则其双亲结点是结点，则其双亲结点是结点，则其双亲结点是结点，则其双亲结点是结点 i i/2/2 。(2)(2)若若若若 2 2i i n n，则则则则结结结结点点点点 i i 没没没没有有有有左左左左孩孩孩孩子子子子（结结结结点点点点 i i 为为为为叶叶叶叶子子子子结点）；否则其左孩子是结点结点）；否则其左孩子是结点结点）；否则其左孩子是结点结点）；否则其左孩子是结点 2 2i i。(3)(3)若若若若 2 2i i +1 1n n，则则则则结结结结点点点点 i i 没没没没有有有有右右右右孩孩孩孩子子子子；否否否否则则则则其其其其右右右右孩孩孩孩子是结点子是结点子是结点子是结点 2 2i i+1+1。二二二二叉叉叉叉树树树树和和和和其其其其他他他他数数数数据据据据结结结结构构构构一一一一样样样样也也也也分分分分顺顺顺顺序序序序存存存存储储储储结结结结构构构构和和和和链链链链式式式式存存存存储储储储结结结结构构构构；而而而而链链链链式式式式存存存存储储储储结结结结构构构构又又又又分分分分二二二二叉叉叉叉链链链链表表表表存存存存储储储储结结结结构构构构和和和和三叉链表存储结构。三叉链表存储结构。三叉链表存储结构。三叉链表存储结构。246.2.3 二叉树的存储结构二叉树的存储结构 二二二二叉叉叉叉树树树树的的的的顺顺顺顺序序序序存存存存储储储储结结结结构构构构就就就就是是是是用用用用一一一一组组组组地地地地址址址址连连连连续续续续的的的的存存存存储单元来存放一棵二叉树的所有结点元素。储单元来存放一棵二叉树的所有结点元素。储单元来存放一棵二叉树的所有结点元素。储单元来存放一棵二叉树的所有结点元素。#define#define MAX_TREE_SIZE 100 MAX_TREE_SIZE 100 /二叉树的最大结点数二叉树的最大结点数二叉树的最大结点数二叉树的最大结点数 typedef typedef DataType DataType SqBiTreeMAX_TREE_SIZE;SqBiTreeMAX_TREE_SIZE;/定义顺序树类型定义顺序树类型定义顺序树类型定义顺序树类型SqBiTreeSqBiTree，约定，约定，约定，约定0 0 号单元存储根结点号单元存储根结点号单元存储根结点号单元存储根结点 SqBiTree SqBiTree bt;bt;/定义了一棵二叉树定义了一棵二叉树btbt25 1.1.顺序存储结构顺序存储结构顺序存储结构顺序存储结构 顺顺顺顺序序序序存存存存储储储储结结结结构构构构仅仅仅仅适适适适用用用用于于于于完完完完全全全全二二二二叉叉叉叉树树树树。如如如如果果果果存存存存储储储储一一一一般般般般二二二二叉叉叉叉树树树树，则则则则会会会会造造造造成成成成存存存存储储储储空空空空间间间间的的的的浪浪浪浪费费费费，这这这这时时时时就就就就需需需需要要要要使使使使用用用用二二二二叉树的链式存储结构。叉树的链式存储结构。叉树的链式存储结构。叉树的链式存储结构。二二二二叉叉叉叉树树树树的的的的链链链链式式式式存存存存储储储储结结结结构构构构主主主主要要要要是是是是设设设设计计计计结结结结点点点点结结结结构构构构。根根根根据据据据结结结结点点点点结结结结构构构构的的的的不不不不同同同同，又又又又可可可可以以以以分分分分为为为为二二二二叉叉叉叉链链链链表表表表存存存存储储储储结结结结构构构构和和和和三三三三叉叉叉叉链表存储结构。链表存储结构。链表存储结构。链表存储结构。26 2.2.链式存储结构链式存储结构链式存储结构链式存储结构 (1)(1)二叉链表存储结构二叉链表存储结构二叉链表存储结构二叉链表存储结构tyepdef struct Node tyepdef struct Node DataType DataTypedata;data;structNode structNode *lchild,lchild,*rchild;rchild;/左右孩子指针左右孩子指针左右孩子指针左右孩子指针 BiTNode BiTNode *BiTree;BiTree;/二叉链表存储结构类型名二叉链表存储结构类型名二叉链表存储结构类型名二叉链表存储结构类型名lchildlchilddatadatarchildrchild左孩子指针左孩子指针左孩子指针左孩子指针右孩子指针右孩子指针右孩子指针右孩子指针数据域数据域数据域数据域27 二二二二叉叉叉叉