教学课件第6章树与二叉树

《教学课件第6章树与二叉树》由会员分享，可在线阅读，更多相关《教学课件第6章树与二叉树（138页珍藏版）》请在金锄头文库上搜索。

1、第第6 6章章 树与二叉树树与二叉树 树树树树 (tree) (tree) 结结结结构构构构是是是是一一一一种种种种多多多多分分分分支支支支多多多多层层层层次次次次的的的的数数数数据据据据结结结结构构构构，由由由由一一一一组组组组结结结结点点点点组组组组成成成成。由由由由于于于于它它它它呈呈呈呈现现现现与与与与自自自自然然然然界界界界树树树树类类类类似似似似的的的的结结结结构构构构形形形形式式式式，所所所所以以以以称称称称之之之之为为为为树树树树。在在在在许许许许多多多多算算算算法法法法中中中中，常常常常用用用用树树树树型型型型结结结结构构构构描描描描述述述述问题的求解过程或表示求解的对策等。

2、问题的求解过程或表示求解的对策等。问题的求解过程或表示求解的对策等。问题的求解过程或表示求解的对策等。树的逻辑结构树的逻辑结构6.1 树树2树的存储结构树的存储结构 树树树树是是是是由由由由 n n ( (n n0)0) 个个个个结结结结点点点点组组组组成成成成的的的的有有有有限限限限集集集集。在在在在任任任任意意意意一一一一棵棵棵棵非空树非空树非空树非空树 T T 中：中：中：中： 有且仅有一个特定的称为有且仅有一个特定的称为有且仅有一个特定的称为有且仅有一个特定的称为根根根根 (root) (root) 结点；结点；结点；结点； 当当当当 n n1 1 时时时时，其其其其余余余余结结结结点

3、点点点分分分分成成成成 mm ( (mm0) 0) 个个个个互互互互不不不不相相相相交交交交的的的的有有有有限限限限集集集集T T1 1，T T2 2，T Tmm，其其其其中中中中每每每每一一一一个个个个集集集集合合合合本本本本身身身身又又又又都都都都是是是是一一一一棵树，并且称为根的棵树，并且称为根的棵树，并且称为根的棵树，并且称为根的子树子树子树子树。36.1.1 树的逻辑结构树的逻辑结构 1. 1. 树的定义树的定义树的定义树的定义42. 2. 树的基本操作树的基本操作树的基本操作树的基本操作 InitTree (tree); InitTree (tree);操作结果：构造空树操作结果：

4、构造空树操作结果：构造空树操作结果：构造空树 TreeTree。 InsertChild (Tree, p, child); InsertChild (Tree, p, child); 初始条件：树初始条件：树初始条件：树初始条件：树 TreeTree 存在，存在，存在，存在，p p 指向指向指向指向 TreeTree 中某个结点，中某个结点，中某个结点，中某个结点， 11i i p p 所所所所指指指指结结结结点点点点的的的的度度度度+1+1，非非非非空空空空树树树树 childchild 与与与与TreeTree 不相交。不相交。不相交。不相交。操作结果：插入操作结果：插入操作结果：插入操

5、作结果：插入childchild为为为为 T T 中中中中 p p 所指结点的子所指结点的子所指结点的子所指结点的子树。树。树。树。 树结构中经常会用到一些基本术语。例如：树结构中经常会用到一些基本术语。例如：树结构中经常会用到一些基本术语。例如：树结构中经常会用到一些基本术语。例如：结点结点结点结点结点的度结点的度结点的度结点的度叶结点叶结点叶结点叶结点分支结点分支结点分支结点分支结点树的度树的度树的度树的度双亲及孩子双亲及孩子双亲及孩子双亲及孩子兄弟兄弟兄弟兄弟堂兄弟堂兄弟堂兄弟堂兄弟祖先祖先祖先祖先子孙子孙子孙子孙层次层次层次层次树的深度树的深度树的深度树的深度有序树有序树有序树有序树无

6、序树无序树无序树无序树森林森林森林森林5 3. 3. 树的基本概念树的基本概念树的基本概念树的基本概念66.1.2 树的存储结构树的存储结构 假假假假设设设设以以以以一一一一组组组组连连连连续续续续空空空空间间间间存存存存储储储储树树树树的的的的结结结结点点点点，同同同同时时时时在在在在每每每每个个个个结结结结点点点点中中中中附附附附设设设设一一一一个个个个指指指指示示示示器器器器指指指指示示示示其其其其双双双双亲亲亲亲结结结结点点点点在在在在连连连连续续续续空空空空间间间间中中中中的的的的位位位位置。置。置。置。 typedef struct typedef struct / / 双亲表示结

7、构定义双亲表示结构定义双亲表示结构定义双亲表示结构定义 TNode TNode treeMAX; treeMAX; / / 结点数组结点数组结点数组结点数组 int int nodenum; nodenum; / / 结点数结点数结点数结点数 ParentTree; ParentTree; / / 双亲表示结构类型名双亲表示结构类型名双亲表示结构类型名双亲表示结构类型名 #define Max 100 #define Max 100 typedef struct TNode typedef struct TNode / / 结点结构定义结点结构定义结点结构定义结点结构定义 DataType D

8、ataTypedata;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双亲存储结构双亲存储结构双亲存储结构双亲存储结构 树树树树的的的的双双双双亲

9、亲亲亲表表表表示示示示存存存存储储储储结结结结构构构构利利利利用用用用了了了了每每每每个个个个结结结结点点点点（根根根根结结结结点点点点除除除除外外外外）只只只只有惟一双亲的性质。有惟一双亲的性质。有惟一双亲的性质。有惟一双亲的性质。 在在在在树树树树的的的的双双双双亲亲亲亲存存存存储储储储结结结结构构构构中中中中，求求求求双双双双亲亲亲亲 Parent(T, Parent(T, x) x) 操操操操作作作作非非非非常常常常方方方方便便便便。求求求求树树树树根根根根结结结结点点点点 Root(x) Root(x) 操操操操作作作作也也也也很很很很简简简简单单单单：反反反反复复复复调调调调用用用

10、用 Parent Parent 操操操操作作作作，直直直直到到到到遇遇遇遇见见见见无无无无双双双双亲亲亲亲的的的的结结结结点点点点时时时时，即即即即 T T.parent .parent = = -1 -1 时时时时，便便便便找找找找到到到到了了了了惟惟惟惟一一一一的的的的无双亲的根结点。无双亲的根结点。无双亲的根结点。无双亲的根结点。 在在在在树树树树的的的的双双双双亲亲亲亲存存存存储储储储结结结结构构构构中中中中，求求求求某某某某结结结结点点点点的的的的孩孩孩孩子子子子结结结结点点点点时时时时需需需需遍遍遍遍历历历历整整整整个个个个结结结结构构构构。例例例例如如如如求求求求树树树树中中中中

11、结结结结点点点点 F F 的的的的孩孩孩孩子子子子，就就就就需需需需要要要要在在在在整整整整个个个个结结结结构构构构中中中中 从从从从 头头头头 到到到到 尾尾尾尾 扫扫扫扫 描描描描 一一一一 遍遍遍遍 T T.parent .parent 域域域域，T T.parent .parent = = 6 6 的的的的结结结结点点点点 G G、HH、K K 就就就就是是是是结结结结点点点点 F F 的孩子。的孩子。的孩子。的孩子。 由由由由于于于于树树树树中中中中每每每每个个个个结结结结点点点点可可可可能能能能有有有有多多多多棵棵棵棵子子子子树树树树，则则则则可可可可以以以以用用用用多多多多重重重

12、重链链链链表表表表，即即即即每每每每个个个个结结结结点点点点有有有有多多多多个个个个指指指指针针针针域域域域，其其其其中中中中每每每每个个个个指指指指针针针针指指指指向向向向一一一一棵棵棵棵子子子子树树树树的的的的根根根根结结结结点点点点，此此此此时时时时，链链链链表表表表中中中中的的的的结结结结点点点点可可可可以以以以有有有有如如如如下下下下 3 3 种种种种结构格式：结构格式：结构格式：结构格式：8同构结点格式同构结点格式同构结点格式同构结点格式不同构结点格式不同构结点格式不同构结点格式不同构结点格式单链表存储结构单链表存储结构单链表存储结构单链表存储结构 2. 2. 孩子表示法孩子表示法

13、孩子表示法孩子表示法 (1) (1) 同构结点格式。同构结点格式。同构结点格式。同构结点格式。即多重链表中的结点是同构的。即多重链表中的结点是同构的。即多重链表中的结点是同构的。即多重链表中的结点是同构的。datadatachildchild1 1childchild2 2childchildd d 其其其其中中中中 d d 为为为为树树树树的的的的度度度度。由由由由于于于于树树树树中中中中很很很很多多多多结结结结点点点点的的的的度度度度都都都都小小小小于于于于 d d，所以链表中有很多空链域，空间比较浪费。，所以链表中有很多空链域，空间比较浪费。，所以链表中有很多空链域，空间比较浪费。，所以

14、链表中有很多空链域，空间比较浪费。9 设设设设树树树树的的的的度度度度为为为为 k k，结结结结点点点点数数数数为为为为 n n。若若若若采采采采用用用用同同同同构构构构结结结结点点点点格格格格式式式式，每每每每个个个个结结结结点点点点具具具具有有有有 k k 个个个个固固固固定定定定链链链链域域域域，那那那那么么么么共共共共有有有有 nknk 个个个个链链链链域域域域。由由由由于于于于 n n 个个个个结结结结点点点点要要要要有有有有 ( ( n n - - - - 1) 1) 个个个个枝枝枝枝相相相相连连连连，而而而而每每每每枝枝枝枝需需需需要要要要 1 1 个个个个链链链链域域域域。因此

15、，这棵树的空链域的个树为：因此，这棵树的空链域的个树为：因此，这棵树的空链域的个树为：因此，这棵树的空链域的个树为： n n ( ( k k 1 ) +1 1 ) +1。 由由由由此此此此可可可可知知知知，树树树树的的的的度度度度越越越越大大大大，空空空空链链链链域域域域越越越越多多多多。如如如如果果果果采采采采用用用用同同同同构结点格式将造成空间的极大浪费。构结点格式将造成空间的极大浪费。构结点格式将造成空间的极大浪费。构结点格式将造成空间的极大浪费。 (2) (2) 不不不不同同同同构构构构结结结结点点点点格格格格式式式式。即即即即多多多多重重重重链链链链表表表表中中中中的的的的结结结结点

16、点点点是是是是不不不不同同同同构的。构的。构的。构的。degreedegree childchild1 1childchild2 2childchildd ddatadata 其中其中其中其中种种种种存存存存储储储储结结结结构构构构避避免免了了孩孩子子表表示示法法存存储储结结构构中中出出现现的的空空链链域域，节节约约存存储储空空间间。但但是是由由于于每每个个结结点点的的孩孩子子链链域域数数不同，所以在这种结构上进行的各种操作不易实现。不同，所以在这种结构上进行的各种操作不易实现。 为结点的度，为结点的度，为结点的度，为结点的度，degree degree 域的值和域的值和域的值和域的值和 d

17、d相同。这相同。这相同。这相同。这10d d (3) (3) 单单单单链链链链表表表表存存存存储储储储结结结结构构构构。即即即即把把把把每每每每个个个个结结结结点点点点的的的的孩孩孩孩子子子子结结结结点点点点排排排排列列列列起起起起来来来来，看看看看成成成成是是是是一一一一个个个个线线线线性性性性表表表表，且且且且以以以以单单单单链链链链表表表表作作作作为为为为存存存存储储储储结结结结构构构构，则则则则 n n 个个个个结结结结点点点点有有有有 n n 个个个个孩孩孩孩子子子子链链链链表表表表（叶叶叶叶子子子子结结结结点点点点的的的的孩孩孩孩子子子子链链链链表表表表为为为为空空空空表表表表）。

18、而而而而 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 与与与与树树树树的的的的双双双双亲亲亲亲表表表表示示示示法法

19、法法相相相相反反反反，树树树树的的的的孩孩孩孩子子子子单单单单链链链链表表表表表表表表示示示示法法法法便便便便于于于于查查查查找找找找树树树树中中中中任任任任一一一一结结结结点点点点的的的的孩孩孩孩子子子子：由由由由链链链链表表表表中中中中某某某某结结结结点点点点的的的的指指指指针针针针域域域域 next next 即即即即可可可可以以以以得得得得到到到到该结点的孩子结点。该结点的孩子结点。该结点的孩子结点。该结点的孩子结点。 在在在在树树树树的的的的孩孩孩孩子子子子单单单单链链链链表表表表结结结结构构构构中中中中，查查查查找找找找某某某某结结结结点点点点的的的的双双双双亲亲亲亲需需需需要要要

20、要按按按按照照照照该该该该结结结结点点点点在在在在头头头头结结结结点点点点顺顺顺顺序序序序表表表表中中中中的的的的位位位位置置置置序序序序号号号号在在在在每每每每个个个个孩孩孩孩子子子子链链链链表表表表中中中中扫扫扫扫描描描描，当当当当在在在在孩孩孩孩子子子子域域域域 child child 中中中中找找找找到到到到相相相相同同同同的的的的序序序序号号号号时时时时，则则则则单单单单链链链链表表表表表表表表头头头头的的的的结结结结点点点点就就就就是是是是要找的双亲。要找的双亲。要找的双亲。要找的双亲。 例例例例如如如如，要要要要寻寻寻寻找找找找树树树树中中中中 G G 结结结结点点点点的的的的双

21、双双双亲亲亲亲结结结结点点点点。G G 结结结结点点点点在在在在头头头头结结结结点点点点顺顺顺顺序序序序表表表表中中中中的的的的位位位位置置置置序序序序号号号号为为为为 7 7，则则则则在在在在孩孩孩孩子子子子链链链链表表表表中中中中查查查查询询询询 child child = = 7 7 的的的的孩孩孩孩子子子子结结结结点点点点，当当当当找找找找到到到到的的的的时时时时候候候候，该该该该单单单单链链链链表表表表的的的的表表表表头头头头结结结结点点点点 F F 就是就是就是就是 G G 的双亲结点。的双亲结点。的双亲结点。的双亲结点。 树树树树的的的的孩孩孩孩子子子子兄兄兄兄弟弟弟弟表表表表示

22、示示示法法法法又又又又称称称称二二二二叉叉叉叉树树树树表表表表示示示示法法法法，或或或或二二二二叉叉叉叉链链链链表表表表表表表表示示示示法法法法，即即即即以以以以二二二二叉叉叉叉链链链链表表表表作作作作为为为为树树树树的的的的存存存存储储储储结结结结构构构构。链链链链表表表表中中中中每每每每个个个个结结结结点点点点的的的的结结结结构构构构相相相相同同同同，都都都都有有有有 3 3 个个个个域域域域：数数数数据据据据域域域域 data data 存存存存放放放放树树树树中中中中结结结结点点点点的的的的信信信信息息息息；孩孩孩孩子子子子域域域域 firstchild firstchild 存存存存

23、放放放放该该该该结结结结点点点点的的的的第第第第一一一一个个个个孩孩孩孩子子子子结结结结点点点点（从从从从左左左左算算算算起起起起）的的的的地地地地址址址址；兄兄兄兄弟弟弟弟域域域域 nextsibling nextsibling 存存存存放放放放该该该该结结结结点的下一个兄弟结点（从左向右）的地址。点的下一个兄弟结点（从左向右）的地址。点的下一个兄弟结点（从左向右）的地址。点的下一个兄弟结点（从左向右）的地址。133. 3. 孩子兄弟表示法孩子兄弟表示法孩子兄弟表示法孩子兄弟表示法R RA AB BC CD DE EF FG GHHK K树树树树R R A AD DE E B BC C F

24、F G GHHK K 14 树树树树的的的的二二二二叉叉叉叉链链链链表表表表存存存存储储储储结结结结构构构构的的的的最最最最大大大大优优优优点点点点就就就就是是是是结结结结点点点点的的的的结结结结构构构构统统统统一一一一，和和和和前前前前面面面面讲讲讲讲的的的的二二二二叉叉叉叉树树树树表表表表示示示示法法法法完完完完全全全全一一一一样样样样，因因因因此此此此可可可可以以以以利利利利用用用用二二二二叉叉叉叉树树树树的的的的算算算算法法法法来来来来实实实实现现现现对对对对树树树树的操作。的操作。的操作。的操作。 在在在在树树树树的的的的二二二二叉叉叉叉链链链链表表表表存存存存储储储储结结结结构构构

25、构中中中中，易易易易于于于于实实实实现现现现找找找找结结结结点点点点等等等等的的的的操操操操作作作作。如如如如果果果果要要要要访访访访问问问问树树树树中中中中结结结结点点点点 x x 的的的的第第第第 i i 个个个个孩孩孩孩子子子子，那那那那么么么么 只只只只 需需需需 要要要要 先先先先 从从从从 该该该该 结结结结 点点点点 的的的的 firstchild firstchild 域域域域找找找找到到到到第第第第 1 1 个个个个孩孩孩孩子子子子结结结结点点点点，然然然然后后后后再再再再沿沿沿沿孩孩孩孩子子子子结结结结点点点点的的的的 nextsibling nextsibling 域域域

26、域连连连连续续续续走走走走 i i-1 -1 步步步步，便便便便可可可可以以以以找找找找到到到到结结结结点点点点 x x 的第的第的第的第 i i 个孩子。个孩子。个孩子。个孩子。 例例例例如如如如，要要要要访访访访问问问问 F F 结结结结点点点点的的的的第第第第 3 3 个个个个孩孩孩孩子子子子，只只只只要要要要先先先先从从从从 F F 结结结结点点点点的的的的 Firstchild Firstchild 域域域域找找找找到到到到第第第第一一一一个个个个孩孩孩孩子子子子 G G 结结结结点点点点后后后后，再再再再沿沿沿沿着着着着 G G 结结结结点点点点的的的的 Nextsibling N

27、extsibling 域域域域连连连连续续续续走走走走 2 2 步步步步，找找找找到到到到 K K 结结结结点点点点，这这这这就就就就是是是是 F F 结结结结点点点点的的的的第第第第 3 3 个个个个孩孩孩孩子子子子结结结结点点点点。但但但但是是是是，在在在在这这这这个个个个结结结结构构构构上上上上查查查查找找找找某某某某结结结结点点点点的的的的双双双双亲亲亲亲结结结结点点点点不不不不是是是是很很很很方方方方便便便便，若若若若为为为为每每每每个个个个结结结结点点点点再再再再增增增增设设设设一一一一个个个个双双双双亲亲亲亲 parent parent 域域域域，则则则则查查查查找找找找某某某某

28、结结结结点点点点的的的的双双双双亲亲亲亲的的的的操操操操作作作作也很方便。也很方便。也很方便。也很方便。 二二二二叉叉叉叉树树树树 (binary (binary tree) tree) 是是是是另另另另一一一一种种种种树树树树型型型型结结结结构构构构，它它它它的的的的特特特特点点点点是是是是每每每每个个个个结结结结点点点点至至至至多多多多只只只只有有有有两两两两棵棵棵棵子子子子树树树树（即即即即二二二二叉叉叉叉树树树树中中中中不不不不存存存存在在在在度度度度大大大大于于于于 2 2 的的的的结结结结点点点点），并并并并且且且且，二二二二叉叉叉叉树树树树的的的的子子子子树树树树有有有有左左左左

29、右右右右之之之之分分分分，其其其其次次次次序不能任意颠倒。序不能任意颠倒。序不能任意颠倒。序不能任意颠倒。二叉树的逻辑结构二叉树的逻辑结构6.2 二叉树二叉树15二叉树的基本性质二叉树的基本性质二叉树的存储结构二叉树的存储结构 二二二二叉叉叉叉树树树树是是是是一一一一个个个个有有有有限限限限的的的的结结结结点点点点的的的的集集集集合合合合，该该该该集集集集合合合合或或或或者者者者为为为为空空空空，或或或或者者者者由由由由一一一一个个个个根根根根结结结结点点点点加加加加上上上上两两两两棵棵棵棵分分分分别别别别称称称称为为为为左左左左子子子子树树树树和和和和右右右右子子子子树树树树的的的的、互不相

30、交的二叉树组成。互不相交的二叉树组成。互不相交的二叉树组成。互不相交的二叉树组成。16 二二二二叉叉叉叉树树树树定定定定义义义义是是是是一一一一个个个个递递递递归归归归定定定定义义义义，即即即即在在在在二二二二叉叉叉叉树树树树的的的的定定定定义义义义中中中中又用到二叉树的概念。又用到二叉树的概念。又用到二叉树的概念。又用到二叉树的概念。6.2.1 二叉树的逻辑结构二叉树的逻辑结构 1. 1. 二叉树的定义二叉树的定义二叉树的定义二叉树的定义 性性性性质质质质1 1：在在在在二二二二叉叉叉叉树树树树的的的的第第第第 i i 层层层层上上上上至至至至多多多多有有有有 2 2i i-1-1 个个个个

31、结结结结点点点点（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

32、个结点。那么，可以证明个结点。那么，可以证明个结点。那么，可以证明个结点。那么，可以证明 j j = = i i 时命题也成立。时命题也成立。时命题也成立。时命题也成立。 根根根根据据据据归归归归纳纳纳纳假假假假设设设设，第第第第 i i-1 -1 层层层层上上上上至至至至多多多多有有有有 2 2i i-2-2 个个个个结结结结点点点点。由由由由于于于于二二二二叉叉叉叉树树树树的的的的每每每每个个个个结结结结点点点点的的的的度度度度最最最最多多多多为为为为 2 2，所所所所以以以以在在在在第第第第 i i 层层层层上上上上最最最最多多多多的的的的结点数为第结点数为第结点数为第结点数为第 i i

33、-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 的二叉树的最大结点数为的二叉树的最大结点数为的二叉树的最大结点数为的二叉树的最大结点数为

34、 性性性性质质质质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 为为为为二二二二叉叉叉叉树树树树中中中中总总总总结结结结点点点点数数数数。

35、因因因因为为为为二二二二叉叉叉叉树树树树中中中中所所所所有有有有结结结结点点点点的的的的度度度度均均均均小小小小于于于于或或或或等等等等于于于于 2 2，则：，则：，则：，则：n n = = n n0 0 + + n n1 1 + + n n2 2 。 (2) (2) 设设设设 B B 为二叉树为二叉树为二叉树为二叉树 T T 中的分支总数。中的分支总数。中的分支总数。中的分支总数。 从从从从入入入入支支支支的的的的角角角角度度度度看看看看，二二二二叉叉叉叉树树树树中中中中除除除除了了了了根根根根结结结结点点点点外外外外，其其其其余余余余结结结结点都有一个且仅有一个入支，则：点都有一个且仅有一

36、个入支，则：点都有一个且仅有一个入支，则：点都有一个且仅有一个入支，则：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 =

37、= n n2 2 + 1 + 1。 为为为为便便便便于于于于介介介介绍绍绍绍下下下下面面面面两两两两个个个个二二二二叉叉叉叉树树树树性性性性质质质质，先先先先了了了了解解解解满满满满二二二二叉叉叉叉树树树树 (full (full binary binary tree) tree) 和和和和完完完完全全全全二二二二叉叉叉叉树树树树 (complete (complete binary binary tree) tree) 的概念。的概念。的概念。的概念。20 满满满满二二二二叉叉叉叉树树树树的的的的特特特特点点点点是是是是：每每每每一一一一层层层层上上上上的的的的结结结结点点点点数数数数都都都

38、都达达达达到到到到最最最最大大大大值值值值；满满满满二二二二叉叉叉叉树树树树中中中中只只只只有有有有度度度度为为为为 0 0 和和和和度度度度为为为为 2 2 的的的的结结结结点点点点，不不不不存存存存在在在在度度度度为为为为 1 1 的的的的结结结结点点点点；每每每每一一一一个个个个结结结结点点点点均均均均有有有有两两两两棵棵棵棵高高高高度度度度相相相相同同同同的的的的子子子子树树树树，叶叶叶叶子结点都在树的最下面的同一层上。子结点都在树的最下面的同一层上。子结点都在树的最下面的同一层上。子结点都在树的最下面的同一层上。 满满满满二二二二叉叉叉叉树树树树：一一一一棵棵棵棵深深深深度度度度为为

39、为为 k k 并并并并且且且且有有有有 2 2k k- - - -1 1 个个个个结结结结点点点点的的的的二二二二叉叉叉叉树，称之为满二叉树。树，称之为满二叉树。树，称之为满二叉树。树，称之为满二叉树。 如如如如果果果果对对对对满满满满二二二二叉叉叉叉树树树树的的的的结结结结点点点点进进进进行行行行编编编编号号号号，约约约约定定定定编编编编号号号号从从从从根根根根结结结结点点点点起起起起，自自自自上上上上而而而而下下下下，自自自自左左左左至至至至右右右右。由由由由此此此此可可可可以以以以引引引引出出出出完完完完全全全全二二二二叉叉叉叉树树树树的定义。的定义。的定义。的定义。 完完完完全全全全二

40、二二二叉叉叉叉树树树树的的的的特特特特点点点点是是是是：二二二二叉叉叉叉树树树树中中中中的的的的叶叶叶叶子子子子结结结结点点点点只只只只可可可可能能能能出出出出现现现现在在在在二二二二叉叉叉叉树树树树中中中中层层层层次次次次最最最最大大大大的的的的两两两两层层层层上上上上；最最最最下下下下一一一一层层层层的的的的结结结结点点点点一一一一定定定定是是是是从从从从最最最最左左左左边边边边开开开开始始始始向向向向右右右右放放放放的的的的；并并并并且且且且若若若若某某某某个个个个结结结结点点点点没没没没有有有有左左左左孩孩孩孩子，则它一定没有右孩子。子，则它一定没有右孩子。子，则它一定没有右孩子。子，

41、则它一定没有右孩子。21 完完完完全全全全二二二二叉叉叉叉树树树树：一一一一棵棵棵棵深深深深度度度度为为为为 k k 并并并并且且且且有有有有 n n 个个个个结结结结点点点点的的的的二二二二叉叉叉叉树树树树，当当当当且且且且仅仅仅仅当当当当其其其其每每每每一一一一个个个个结结结结点点点点都都都都与与与与深深深深度度度度为为为为 k k 的的的的满满满满二二二二叉叉叉叉树树树树中中中中编号从编号从编号从编号从 1 1 至至至至 n n 的结点一一对应时，称之为完全二叉树。的结点一一对应时，称之为完全二叉树。的结点一一对应时，称之为完全二叉树。的结点一一对应时，称之为完全二叉树。 性质性质性质性

42、质4 4：具有：具有：具有：具有 n n 个结点的完全二叉树的深度为个结点的完全二叉树的深度为个结点的完全二叉树的深度为个结点的完全二叉树的深度为 loglog2 2n n + 1 + 1 （ x x 表示不大于表示不大于表示不大于表示不大于 x x 的最大整数）的最大整数）的最大整数）的最大整数）22 证明：证明：证明：证明： 设设设设所所所所求求求求完完完完全全全全二二二二叉叉叉叉树树树树深深深深度度度度为为为为 k k，则则则则它它它它的的的的前前前前 k k-1 -1 层层层层可可可可视视视视为为为为深深深深度度度度为为为为 k k-1 -1 的的的的满满满满二二二二叉叉叉叉树树树树，

43、共共共共有有有有 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

44、等价关系：等价关系：等价关系：等价关系：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）的的的的结结结结点点点点按按按按照照照照层

45、层层层次次次次编编编编号号号号（从从从从第第第第 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

46、/ 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。 二二二二叉叉叉叉树树树树和和和和其其其其

47、他他他他数数数数据据据据结结结结构构构构一一一一样样样样也也也也分分分分顺顺顺顺序序序序存存存存储储储储结结结结构构构构和和和和链链链链式式式式存存存存储储储储结结结结构构构构；而而而而链链链链式式式式存存存存储储储储结结结结构构构构又又又又分分分分二二二二叉叉叉叉链链链链表表表表存存存存储储储储结结结结构构构构和和和和三叉链表存储结构。三叉链表存储结构。三叉链表存储结构。三叉链表存储结构。246.2.3 二叉树的存储结构二叉树的存储结构 二二二二叉叉叉叉树树树树的的的的顺顺顺顺序序序序存存存存储储储储结结结结构构构构就就就就是是是是用用用用一一一一组组组组地地地地址址址址连连连连续续续续的的

48、的的存存存存储单元来存放一棵二叉树的所有结点元素。储单元来存放一棵二叉树的所有结点元素。储单元来存放一棵二叉树的所有结点元素。储单元来存放一棵二叉树的所有结点元素。 # define # define MAX_TREE_SIZE 100 MAX_TREE_SIZE 100 / / 二叉树的最大结点数二叉树的最大结点数二叉树的最大结点数二叉树的最大结点数 typedef typedef DataType DataType SqBiTreeMAX_TREE_SIZE;SqBiTreeMAX_TREE_SIZE; / / 定义顺序树类型定义顺序树类型定义顺序树类型定义顺序树类型SqBiTreeSqB

49、iTree，约定，约定，约定，约定0 0 号单元存储根结点号单元存储根结点号单元存储根结点号单元存储根结点 SqBiTree SqBiTree bt; bt; / /定义了一棵二叉树定义了一棵二叉树btbt25 1. 1. 顺序存储结构顺序存储结构顺序存储结构顺序存储结构 顺顺顺顺序序序序存存存存储储储储结结结结构构构构仅仅仅仅适适适适用用用用于于于于完完完完全全全全二二二二叉叉叉叉树树树树。如如如如果果果果存存存存储储储储一一一一般般般般二二二二叉叉叉叉树树树树，则则则则会会会会造造造造成成成成存存存存储储储储空空空空间间间间的的的的浪浪浪浪费费费费，这这这这时时时时就就就就需需需需要要要要

50、使使使使用用用用二二二二叉树的链式存储结构。叉树的链式存储结构。叉树的链式存储结构。叉树的链式存储结构。 二二二二叉叉叉叉树树树树的的的的链链链链式式式式存存存存储储储储结结结结构构构构主主主主要要要要是是是是设设设设计计计计结结结结点点点点结结结结构构构构。根根根根据据据据结结结结点点点点结结结结构构构构的的的的不不不不同同同同，又又又又可可可可以以以以分分分分为为为为二二二二叉叉叉叉链链链链表表表表存存存存储储储储结结结结构构构构和和和和三三三三叉叉叉叉链表存储结构。链表存储结构。链表存储结构。链表存储结构。26 2. 2. 链式存储结构链式存储结构链式存储结构链式存储结构 (1) (1)

51、 二叉链表存储结构二叉链表存储结构二叉链表存储结构二叉链表存储结构tyepdef struct Node tyepdef struct Node DataType DataTypedata;data; structNode structNode * * * *lchild, lchild, * * * *rchild; rchild; / / 左右孩子指针左右孩子指针左右孩子指针左右孩子指针 BiTNode BiTNode * * * *BiTree;BiTree; / / 二叉链表存储结构类型名二叉链表存储结构类型名二叉链表存储结构类型名二叉链表存储结构类型名lchildlchilddata

52、datarchildrchild左孩子指针左孩子指针左孩子指针左孩子指针右孩子指针右孩子指针右孩子指针右孩子指针数据域数据域数据域数据域27 二二二二叉叉叉叉树树树树的的的的结结结结点点点点由由由由一一一一个个个个数数数数据据据据元元元元素素素素和和和和分分分分别别别别指指指指向向向向其其其其左左左左、右右右右子子子子树树树树的的的的两两两两个个个个分分分分支支支支构构构构成成成成，则则则则表表表表示示示示二二二二叉叉叉叉树树树树的的的的链链链链表表表表中中中中的的的的结结结结点点点点包包包包括括括括三三三三个个个个域域域域：数数数数据据据据域域域域、左左左左指指指指针针针针域域域域和和和和右

53、右右右指指指指针针针针域域域域，称称称称为为为为二二二二叉叉叉叉链链链链表存储结构。表存储结构。表存储结构。表存储结构。 (2) (2) 三叉链表存储结构三叉链表存储结构三叉链表存储结构三叉链表存储结构tyepdef struct TriTNode tyepdef struct TriTNode TElemType TElemTypedata;data; struct TriTNode struct TriTNode * * * *lchild, lchild, * * * *rchild, rchild, * * * *parent;parent; TriTNode TriTNode * *

54、 * *TriTree;TriTree; / / 三叉链表存储结构类型名三叉链表存储结构类型名三叉链表存储结构类型名三叉链表存储结构类型名左孩子指针左孩子指针左孩子指针左孩子指针右孩子指针右孩子指针右孩子指针右孩子指针数据域数据域数据域数据域lchildlchilddatadataparentparentrchildrchild双亲指针双亲指针双亲指针双亲指针28 为为为为方方方方便便便便找找找找到到到到结结结结点点点点双双双双亲亲亲亲，在在在在二二二二叉叉叉叉链链链链表表表表结结结结构构构构中中中中增增增增加加加加一一一一个个个个指指指指向向向向其其其其双双双双亲亲亲亲结结结结点点点点的的的

55、的指指指指针针针针域域域域，则则则则表表表表示示示示二二二二叉叉叉叉树树树树的的的的链链链链表表表表中中中中的的的的结结结结点点点点包包包包括括括括四四四四个个个个域域域域：数数数数据据据据域域域域、左左左左指指指指针针针针域域域域、右右右右指指指指针针针针域域域域和和和和双双双双亲亲亲亲指指指指针域，称为三叉链表存储结构。针域，称为三叉链表存储结构。针域，称为三叉链表存储结构。针域，称为三叉链表存储结构。 在在在在二二二二叉叉叉叉树树树树的的的的很很很很多多多多应应应应用用用用中中中中，常常常常要要要要求求求求在在在在二二二二叉叉叉叉树树树树中中中中查查查查找找找找某某某某些些些些指指指指定

56、定定定的的的的结结结结点点点点或或或或对对对对二二二二叉叉叉叉树树树树中中中中全全全全部部部部结结结结点点点点逐逐逐逐一一一一进进进进行行行行某某某某种种种种操操操操作作作作，这就需要依次访问二叉树中的结点，即遍历二叉树。这就需要依次访问二叉树中的结点，即遍历二叉树。这就需要依次访问二叉树中的结点，即遍历二叉树。这就需要依次访问二叉树中的结点，即遍历二叉树。6.4 遍历二叉树遍历二叉树29 遍遍历历二二叉叉树树 (traversing binary tree) 是是指指按按某某种种规规律律巡巡查查二二叉叉树树，对对树树中中的的每每个个结结点点访访问问一一次次且且仅仅访访问问一一次次。在在访访问

57、问每每个个结结点点时时可可对对结结点点进进行行各各种种操操作作，如如：输输出结点的信息、对结点进行计数、修改结点的信息等。出结点的信息、对结点进行计数、修改结点的信息等。遍历二叉树的操作定义遍历二叉树的操作定义30遍历二叉树的递归算法遍历二叉树的递归算法遍历二叉树的非递归算法遍历二叉树的非递归算法建立二叉树的算法建立二叉树的算法 二二二二叉叉叉叉树树树树的的的的定定定定义义义义是是是是递递递递归归归归的的的的，一一一一棵棵棵棵非非非非空空空空的的的的二二二二叉叉叉叉树树树树由由由由三三三三个个个个基基基基本本本本单单单单元元元元组组组组成成成成：根根根根结结结结点点点点、左左左左子子子子树树树

58、树和和和和右右右右子子子子树树树树。因因因因此此此此，若若若若能能能能依次遍历这三部分，便是遍历了整个二叉树。依次遍历这三部分，便是遍历了整个二叉树。依次遍历这三部分，便是遍历了整个二叉树。依次遍历这三部分，便是遍历了整个二叉树。 设设设设以以以以 L L、D D、R R 分分分分别别别别表表表表示示示示遍遍遍遍历历历历左左左左子子子子树树树树、访访访访问问问问根根根根结结结结点点点点和和和和遍遍遍遍历历历历右右右右子子子子树树树树，则则则则可可可可能能能能有有有有 DLRDLR、LDRLDR、LRDLRD、DRLDRL、RDLRDL、RLDRLD 六六六六种种种种遍遍遍遍历历历历二二二二叉叉

59、叉叉树树树树的的的的方方方方案案案案。如如如如果果果果限限限限定定定定先先先先左左左左子子子子树树树树后后后后右右右右子子子子树树树树，则则则则只只只只有有有有前前前前三三三三种种种种方方方方案案案案，分分分分别别别别称称称称之之之之为为为为先先先先根根根根（序序序序）遍遍遍遍历历历历 DLRDLR、中中中中根根根根（序序序序）遍遍遍遍历历历历 LDRLDR 和和和和后后后后根根根根（序序序序）遍遍遍遍历历历历 LRDLRD。遍遍遍遍历历历历左左左左子子子子树树树树和和和和右右右右子子子子树树树树的的的的规规规规律律律律和和和和遍遍遍遍历历历历整整整整个个个个二二二二叉叉叉叉树树树树的的的的规

60、规规规律律律律相相相相同同同同，因而这三种遍历都具有递归性。因而这三种遍历都具有递归性。因而这三种遍历都具有递归性。因而这三种遍历都具有递归性。316.3.1 遍历二叉树的操作定义遍历二叉树的操作定义 (1) (1) 先根（序）先根（序）先根（序）先根（序）DLRDLR 遍历二叉树的操作定义遍历二叉树的操作定义遍历二叉树的操作定义遍历二叉树的操作定义 若二叉树为空，则空操作；否则：若二叉树为空，则空操作；否则：若二叉树为空，则空操作；否则：若二叉树为空，则空操作；否则： 访问根结点；访问根结点；访问根结点；访问根结点； 先序遍历左子树；先序遍历左子树；先序遍历左子树；先序遍历左子树； 先序遍历

61、右子树。先序遍历右子树。先序遍历右子树。先序遍历右子树。32 (2) (2) 中根（序）中根（序）中根（序）中根（序）LDRLDR 遍历二叉树的操作定义遍历二叉树的操作定义遍历二叉树的操作定义遍历二叉树的操作定义 若二叉树为空，则空操作；否则：若二叉树为空，则空操作；否则：若二叉树为空，则空操作；否则：若二叉树为空，则空操作；否则： 中序遍历左子树；中序遍历左子树；中序遍历左子树；中序遍历左子树； 访问根结点；访问根结点；访问根结点；访问根结点； 中序遍历右子树。中序遍历右子树。中序遍历右子树。中序遍历右子树。33 (3) (3) 后根（序）后根（序）后根（序）后根（序）LRDLRD 遍历二叉

62、树的操作定义遍历二叉树的操作定义遍历二叉树的操作定义遍历二叉树的操作定义 若二叉树为空，则空操作；否则：若二叉树为空，则空操作；否则：若二叉树为空，则空操作；否则：若二叉树为空，则空操作；否则： 后序遍历左子树；后序遍历左子树；后序遍历左子树；后序遍历左子树； 后序遍历右子树；后序遍历右子树；后序遍历右子树；后序遍历右子树； 访问根结点。访问根结点。访问根结点。访问根结点。34 遍遍遍遍历历历历二二二二叉叉叉叉树树树树可可可可以以以以根根根根据据据据二二二二叉叉叉叉树树树树的的的的递递递递归归归归定定定定义义义义写写写写出出出出递递递递归算法。分为：归算法。分为：归算法。分为：归算法。分为：先

63、序遍历二叉树的递归算法先序遍历二叉树的递归算法先序遍历二叉树的递归算法先序遍历二叉树的递归算法35中序遍历二叉树的递归算法中序遍历二叉树的递归算法中序遍历二叉树的递归算法中序遍历二叉树的递归算法后序遍历二叉树的递归算法后序遍历二叉树的递归算法后序遍历二叉树的递归算法后序遍历二叉树的递归算法6.3.2 遍历二叉树的递归算法遍历二叉树的递归算法1. 1. 先序遍历二叉树的递归算法先序遍历二叉树的递归算法先序遍历二叉树的递归算法先序遍历二叉树的递归算法 void PreOrder (BiTree root) void PreOrder (BiTree root) /* /* 采采采采用用用用二二二二

64、叉叉叉叉链链链链表表表表存存存存储储储储结结结结构构构构，rootroot为为为为指指指指向向向向二二二二叉叉叉叉树树树树根根根根结结结结点点点点指指指指针针针针，Visit Visit 是是是是对对对对数数数数据据据据元元元元素素素素操操操操作作作作的的的的应应应应用函数，先序遍历二叉树用函数，先序遍历二叉树用函数，先序遍历二叉树用函数，先序遍历二叉树rootroot的递归算法，对每个数据元素调用函数的递归算法，对每个数据元素调用函数的递归算法，对每个数据元素调用函数的递归算法，对每个数据元素调用函数 Visit Visit 。*/*/ if (root!=NULL) if (root!=N

65、ULL) / / 若若若若rootroot不为空不为空不为空不为空36 Visit(root-data)Visit(root-data) / / 访问根结点访问根结点访问根结点访问根结点 PreOrder (root-LChild) PreOrder (root-LChild) / / 先序遍历左子树先序遍历左子树先序遍历左子树先序遍历左子树PreOrder (rootPreOrder (root- - - -RChild) RChild) / /先序遍历先序遍历先序遍历先序遍历右子树右子树右子树右子树 / PreOrder/ PreOrder2. 2. 中序遍历二叉树的递归算法中序遍历二叉树

66、的递归算法中序遍历二叉树的递归算法中序遍历二叉树的递归算法 void InOrder (BiTree root) void InOrder (BiTree root) /* /* 采采采采用用用用二二二二叉叉叉叉链链链链表表表表存存存存储储储储结结结结构构构构，rootroot为为为为指指指指向向向向二二二二叉叉叉叉树树树树( (或或或或某某某某一一一一子子子子树树树树) )根根根根结结结结点点点点指指指指针针针针，Visit Visit 是是是是对对对对数数数数据据据据元元元元素素素素操操操操作作作作的的的的应应应应用用用用函函函函数数数数， 中中中中序序序序遍遍遍遍历历历历二二二二叉叉叉叉

67、树树树树rootroot的的的的递递递递归归归归算算算算法法法法，对对对对每每每每个个个个数数数数据据据据元元元元素素素素调调调调用用用用函函函函数数数数 Visit Visit 。*/*/ if (root!=NULL) if (root!=NULL) / / 若若若若rootroot不为空不为空不为空不为空37 InOrder (root-LChild) InOrder (root-LChild) / / 中序遍历左子树中序遍历左子树中序遍历左子树中序遍历左子树 Visit(rootVisit(root- - - -data)data) / / 访问根结点访问根结点访问根结点访问根结点In

68、Order (rootInOrder (root- - - -RChild) RChild) / /中序遍历中序遍历中序遍历中序遍历右子树右子树右子树右子树 / InOrder/ InOrder3. 3. 后序遍历二叉树的递归算法后序遍历二叉树的递归算法后序遍历二叉树的递归算法后序遍历二叉树的递归算法38 void PostOrder (BiTree root) void PostOrder (BiTree root) /* /* 采采采采用用用用二二二二叉叉叉叉链链链链表表表表存存存存储储储储结结结结构构构构，rootroot为为为为指指指指向向向向二二二二叉叉叉叉树树树树根根根根结结结结点

69、点点点指指指指针针针针，Visit Visit 是是是是对对对对数数数数据据据据元元元元素素素素操操操操作作作作的的的的应应应应用函数，后序遍历二叉树用函数，后序遍历二叉树用函数，后序遍历二叉树用函数，后序遍历二叉树rootroot的递归算法，对每个数据元素调用函数的递归算法，对每个数据元素调用函数的递归算法，对每个数据元素调用函数的递归算法，对每个数据元素调用函数 Visit Visit 。*/*/ if (root!=NULL) if (root!=NULL) / / 若若若若rootroot不为空不为空不为空不为空 PostOrder (root-LChild) PostOrder (r

70、oot-LChild) / / 后序遍历左子树后序遍历左子树后序遍历左子树后序遍历左子树 PostOrder (root PostOrder (root- - - -RChild) RChild) / /后序遍历后序遍历后序遍历后序遍历右子树右子树右子树右子树 Visit(root-data)Visit(root-data) / / 访问根结点访问根结点访问根结点访问根结点 / PostOrder/ PostOrder int Visit ( DataType e ) int Visit ( DataType e ) printf (e); printf (e);/ / 输出数据元素输出数据元

71、素输出数据元素输出数据元素 e e 的值的值的值的值 return OK; return OK; / PrintElement/ PrintElement 对对对对每每每每个个个个数数数数据据据据元元元元素素素素进进进进行行行行访访访访问问问问的的的的时时时时候候候候，可可可可以以以以使使使使用用用用调调调调用用用用函数函数函数函数 Visit Visit，最简单的，最简单的，最简单的，最简单的 Visit Visit 函数是：函数是：函数是：函数是：39 在在在在有有有有些些些些算算算算法法法法语语语语言言言言中中中中是是是是不不不不允允允允许许许许递递递递归归归归调调调调用用用用的的的的，

72、所所所所以以以以也也也也有有有有必必必必要要要要讨讨讨讨论论论论遍遍遍遍历历历历二二二二叉叉叉叉树树树树的的的的非非非非递递递递归归归归算算算算法法法法。非非非非递递递递归归归归的的的的程程程程序序序序中中中中要要要要用用用用栈栈栈栈来来来来保保保保存存存存遍遍遍遍历历历历经经经经过过过过的的的的路路路路径径径径，才才才才能能能能访访访访问问问问到到到到二二二二叉叉叉叉树树树树中中中中的的的的每每每每一个结点。分为：一个结点。分为：一个结点。分为：一个结点。分为：先序遍历二叉树的非递归算法先序遍历二叉树的非递归算法先序遍历二叉树的非递归算法先序遍历二叉树的非递归算法40中序遍历二叉树的非递归算

73、法中序遍历二叉树的非递归算法中序遍历二叉树的非递归算法中序遍历二叉树的非递归算法后序遍历二叉树的非递归算法后序遍历二叉树的非递归算法后序遍历二叉树的非递归算法后序遍历二叉树的非递归算法6.3.3 遍历二叉树的非递归算法遍历二叉树的非递归算法 1. 1. 先序遍历二叉树的非递归算法先序遍历二叉树的非递归算法先序遍历二叉树的非递归算法先序遍历二叉树的非递归算法(1)(1) 算法思算法思算法思算法思想想想想 使使使使用用用用一一一一个个个个栈栈栈栈 S S，用用用用以以以以存存存存放放放放已已已已经经经经访访访访问问问问过过过过的的的的根根根根结结结结点点点点指指指指针针针针，以以以以备备备备在在在

74、在访访访访问问问问该该该该结结结结点点点点的的的的左左左左子子子子树树树树之之之之后后后后再再再再访访访访问问问问其其其其右右右右子子子子树树树树。显显显显然，开始时栈应该为空。然，开始时栈应该为空。然，开始时栈应该为空。然，开始时栈应该为空。 算算算算法法法法开开开开始始始始时时时时，先先先先将将将将栈栈栈栈 S S 初初初初始始始始化化化化，然然然然后后后后令令令令 p p 指指指指向向向向二二二二叉树的根结点，即叉树的根结点，即叉树的根结点，即叉树的根结点，即 p = root p = root。 如如如如果果果果指指指指向向向向根根根根结结结结点点点点的的的的指指指指针针针针非非非非空

75、空空空或或或或者者者者栈栈栈栈非非非非空空空空，则则则则做做做做如如如如下操作：下操作：下操作：下操作：41 如如如如果果果果指指指指向向向向根根根根结结结结点点点点的的的的指指指指针针针针非非非非空空空空，则则则则访访访访问问问问根根根根结结结结点点点点；然然然然后后后后将将将将根根根根结结结结点点点点指指指指针针针针进进进进栈栈栈栈；最最最最后后后后将将将将指指指指针针针针指指指指向向向向该该该该结结结结点点点点的的的的左左左左子子子子树树树树根结点，继续遍历；根结点，继续遍历；根结点，继续遍历；根结点，继续遍历；42 如如如如果果果果指指指指向向向向根根根根结结结结点点点点的的的的指指指

76、指针针针针为为为为空空空空，则则则则应应应应该该该该退退退退至至至至上上上上一一一一层层层层（即将栈顶存放的指针出栈）。有两种情况：（即将栈顶存放的指针出栈）。有两种情况：（即将栈顶存放的指针出栈）。有两种情况：（即将栈顶存放的指针出栈）。有两种情况： 当指针为空并且栈为空时，遍历结束。当指针为空并且栈为空时，遍历结束。当指针为空并且栈为空时，遍历结束。当指针为空并且栈为空时，遍历结束。 若若若若从从从从左左左左子子子子树树树树返返返返回回回回，则则则则应应应应将将将将指指指指针针针针指指指指向向向向当当当当前前前前层层层层（即即即即栈栈栈栈顶指针所指）根结点的右子树根结点，顶指针所指）根结点

77、的右子树根结点，顶指针所指）根结点的右子树根结点，顶指针所指）根结点的右子树根结点， 继续遍历。继续遍历。继续遍历。继续遍历。 若若若若从从从从右右右右子子子子树树树树返返返返回回回回，则则则则表表表表明明明明当当当当前前前前层层层层遍遍遍遍历历历历结结结结束束束束，应应应应该该该该继继继继续续续续退退退退栈栈栈栈。从从从从另另另另一一一一个个个个角角角角度度度度看看看看，这这这这意意意意味味味味着着着着遍遍遍遍历历历历右右右右子子子子树树树树时时时时不不不不再需要保存当前层的根指针，可以直接修改指针。再需要保存当前层的根指针，可以直接修改指针。再需要保存当前层的根指针，可以直接修改指针。再需

78、要保存当前层的根指针，可以直接修改指针。PreOrder PreOrder 非递归算法的时间复杂度非递归算法的时间复杂度非递归算法的时间复杂度非递归算法的时间复杂度 树树树树中中中中非非非非空空空空链链链链域域域域的的的的个个个个数数数数为为为为 2 2n n2 2+ +n n1 1，再再再再由由由由二二二二叉叉叉叉树树树树的的的的性性性性质质质质 3 ( 3 (n n0 0 = = n n2 2+1)+1)，可知：，可知：，可知：，可知：2 2n n2 2 + + n n1 1 = = n n2 2 + + n n2 2 + + n n1 1 = = n n0 0 + + n n1 1 +

79、+ n n2 2 - 1 = - 1 = n n - 1 - 1所以，遍历每个结点的时间复杂度为所以，遍历每个结点的时间复杂度为所以，遍历每个结点的时间复杂度为所以，遍历每个结点的时间复杂度为 O O( (n n) )。(2)(2) 算法分算法分算法分算法分析析析析43 假假假假定定定定二二二二叉叉叉叉树树树树 T T 有有有有 n n 个个个个结结结结点点点点，算算算算法法法法中中中中对对对对每每每每个个个个结结结结点点点点都都都都要要要要入入入入栈栈栈栈和和和和出出出出栈栈栈栈一一一一次次次次。因因因因此此此此，入入入入栈栈栈栈和和和和出出出出栈栈栈栈都都都都要要要要执执执执行行行行 n

80、n 次次次次。此此此此外外外外，只只只只有有有有当当当当 p p 为为为为非非非非空空空空时时时时，才才才才对对对对当当当当前前前前在在在在栈栈栈栈顶顶顶顶的的的的结结结结点点点点信信信信息进行访问。息进行访问。息进行访问。息进行访问。PreOrderPreOrder非递归算法所需附加空间非递归算法所需附加空间非递归算法所需附加空间非递归算法所需附加空间44 算算算算法法法法所所所所需需需需要要要要的的的的附附附附加加加加空空空空间间间间为为为为栈栈栈栈（用用用用以以以以存存存存放放放放已已已已经经经经访访访访问问问问的的的的根根根根结结结结点点点点）的的的的容容容容量量量量。栈栈栈栈的的的的

81、容容容容量量量量与与与与树树树树的的的的深深深深度度度度有有有有关关关关，如如如如果果果果每每每每个个个个结结结结点点点点需需需需要要要要 1 1 个个个个存存存存储储储储单单单单位位位位，则则则则遍遍遍遍历历历历深深深深度度度度为为为为 k k 的的的的二二二二叉叉叉叉树，栈需要树，栈需要树，栈需要树，栈需要 k k 个存储单位，即所需要的空间为个存储单位，即所需要的空间为个存储单位，即所需要的空间为个存储单位，即所需要的空间为 O O( (k k) )。 2. 2. 中序遍历二叉树的非递归算法中序遍历二叉树的非递归算法中序遍历二叉树的非递归算法中序遍历二叉树的非递归算法 算法思想算法思想算

82、法思想算法思想45 使使使使用用用用一一一一个个个个栈栈栈栈 S S，用用用用以以以以存存存存放放放放待待待待访访访访问问问问的的的的根根根根结结结结点点点点指指指指针针针针，以以以以备备备备在在在在访访访访问问问问该该该该结结结结点点点点的的的的左左左左子子子子树树树树之之之之后后后后再再再再访访访访问问问问该该该该结结结结点点点点及及及及其其其其右右右右子子子子树。显然，开始时栈应该为空。树。显然，开始时栈应该为空。树。显然，开始时栈应该为空。树。显然，开始时栈应该为空。 算算算算法法法法开开开开始始始始时时时时，先先先先将将将将栈栈栈栈 S S 初初初初始始始始化化化化，然然然然后后后后

83、令令令令 p p 指指指指向向向向二二二二叉树的根结点，即叉树的根结点，即叉树的根结点，即叉树的根结点，即 p p = = rootroot。 如如如如果果果果指指指指向向向向根根根根结结结结点点点点的的的的指指指指针针针针非非非非空空空空或或或或者者者者栈栈栈栈 S S 非非非非空空空空，则则则则做做做做如下操作：如下操作：如下操作：如下操作： 如如如如果果果果指指指指向向向向根根根根结结结结点点点点指指指指针针针针非非非非空空空空，则则则则将将将将该该该该指指指指针针针针进进进进栈栈栈栈，然然然然后将指针指向该结点左子树根结点，继续遍历。后将指针指向该结点左子树根结点，继续遍历。后将指针指

84、向该结点左子树根结点，继续遍历。后将指针指向该结点左子树根结点，继续遍历。46 如如如如果果果果指指指指向向向向根根根根结结结结点点点点指指指指针针针针为为为为空空空空，则则则则应应应应退退退退至至至至上上上上一一一一层层层层（即即即即将栈顶存放的指针出栈）：将栈顶存放的指针出栈）：将栈顶存放的指针出栈）：将栈顶存放的指针出栈）： 当指针为空并且栈为空时，遍历结束。当指针为空并且栈为空时，遍历结束。当指针为空并且栈为空时，遍历结束。当指针为空并且栈为空时，遍历结束。 若若若若从从从从左左左左子子子子树树树树返返返返回回回回，则则则则应应应应访访访访问问问问当当当当前前前前层层层层（即即即即栈栈

85、栈栈顶顶顶顶指指指指针针针针所所所所指指指指的的的的）根根根根结结结结点点点点，然然然然后后后后将将将将指指指指针针针针指指指指向向向向该该该该结结结结点点点点的的的的右右右右子子子子树树树树根根根根结点，继续遍历；结点，继续遍历；结点，继续遍历；结点，继续遍历； 若若若若从从从从右右右右子子子子树树树树返返返返回回回回，则则则则表表表表明明明明当当当当前前前前层层层层遍遍遍遍历历历历结结结结束束束束，应应应应继继继继续续续续退退退退栈栈栈栈。从从从从另另另另一一一一个个个个角角角角度度度度看看看看，这这这这意意意意味味味味着着着着遍遍遍遍历历历历右右右右子子子子树树树树时时时时不不不不再需要

86、保存当前层的根指针，可直接修改指针。再需要保存当前层的根指针，可直接修改指针。再需要保存当前层的根指针，可直接修改指针。再需要保存当前层的根指针，可直接修改指针。(2)(2)算法描述算法描述void InOrder(BiTree root) void InOrder(BiTree root) /*/*采用二叉链表存储结构，采用二叉链表存储结构，采用二叉链表存储结构，采用二叉链表存储结构，Visit Visit 是对元素操作的应用函数。是对元素操作的应用函数。是对元素操作的应用函数。是对元素操作的应用函数。 中序遍历二叉树中序遍历二叉树中序遍历二叉树中序遍历二叉树T T 的非递归算法，的非递归算

87、法，的非递归算法，的非递归算法，对每个元素调用函数对每个元素调用函数对每个元素调用函数对每个元素调用函数 Visit*/ Visit*/ InitStack (&S);InitStack (&S); / / 使用栈使用栈使用栈使用栈 S S 存放待访问的根结点存放待访问的根结点存放待访问的根结点存放待访问的根结点 p = root;p = root; /令令令令 p p 指向二叉树根结点指向二叉树根结点指向二叉树根结点指向二叉树根结点 while ( p!=NULL | ! IsEmpty (S) )while ( p!=NULL | ! IsEmpty (S) ) / / 当当当当 p p

88、不为空，或者栈不为空，或者栈不为空，或者栈不为空，或者栈 S S 不为空时不为空时不为空时不为空时 if ( p!=NULL ) if ( p!=NULL ) / / 如果如果如果如果 p p 非空非空非空非空 Push ( &S, p )Push ( &S, p ) ; ; / / 将将将将 p p 指针入栈指针入栈指针入栈指针入栈 p = p-Lchild;p = p-Lchild; / / 指针指向左子树根结点，遍历左子树指针指向左子树根结点，遍历左子树指针指向左子树根结点，遍历左子树指针指向左子树根结点，遍历左子树 /if/if else else / / 如果如果如果如果 p p 为

89、空为空为空为空 Pop ( &S, &p )Pop ( &S, &p ) / / 退栈，将上一层的根结点指针弹出退栈，将上一层的根结点指针弹出退栈，将上一层的根结点指针弹出退栈，将上一层的根结点指针弹出 Visit (p-data);Visit (p-data); / / 访问访问访问访问 p p 指针指向的结点指针指向的结点指针指向的结点指针指向的结点 p = p-Rchild;p = p-Rchild; / / 指针指向右子树根结点，遍历右子树指针指向右子树根结点，遍历右子树指针指向右子树根结点，遍历右子树指针指向右子树根结点，遍历右子树 / else / else / while / w

90、hile / InOrder/ InOrder 树树树树中中中中空空空空链链链链域域域域的的的的个个个个数数数数为为为为 2 2n n0 0+ +n n1 1，再再再再由由由由二二二二叉叉叉叉树树树树的的的的性性性性质质质质3 3 ( (n n0 0 = = n n2 2+1)+1)，可知：，可知：，可知：，可知：2 2n n0 0 + + n n1 1 = = n n0 0 + + n n0 0 + + n n1 1 = = n n0 0 + + n n1 1 + + n n2 2 + 1 = + 1 = n n + 1 + 1所以，遍历每个结点的时间复杂度为所以，遍历每个结点的时间复杂度为

91、所以，遍历每个结点的时间复杂度为所以，遍历每个结点的时间复杂度为 O O( (n n) )。(3)(3) 算算算算法法法法分分分分析析析析48InOrder InOrder 非递归算法的时间复杂度非递归算法的时间复杂度非递归算法的时间复杂度非递归算法的时间复杂度 假假假假定定定定二二二二叉叉叉叉树树树树 rootroot 有有有有 n n 个个个个结结结结点点点点，算算算算法法法法中中中中对对对对每每每每个个个个结结结结点点点点都都都都要要要要入入入入栈栈栈栈和和和和出出出出栈栈栈栈一一一一次次次次。因因因因此此此此，入入入入栈栈栈栈和和和和出出出出栈栈栈栈都都都都要要要要执执执执行行行行 n

92、 n 次次次次。此此此此外外外外，只只只只有有有有当当当当 p p 为为为为空空空空时时时时，才才才才对对对对当当当当前前前前在在在在栈栈栈栈顶顶顶顶的的的的结结结结点点点点信息进行访问。信息进行访问。信息进行访问。信息进行访问。InOrder InOrder 非递归算法所需附加空间非递归算法所需附加空间非递归算法所需附加空间非递归算法所需附加空间49 算算算算法法法法所所所所需需需需附附附附加加加加空空空空间间间间为为为为栈栈栈栈（用用用用以以以以存存存存放放放放待待待待访访访访问问问问的的的的根根根根结结结结点点点点）的的的的容容容容量量量量。栈栈栈栈的的的的容容容容量量量量与与与与树树树

93、树的的的的深深深深度度度度有有有有关关关关，如如如如果果果果每每每每个个个个结结结结点点点点需需需需要要要要 1 1 个个个个存存存存储储储储单单单单位位位位，则则则则遍遍遍遍历历历历深深深深度度度度为为为为 k k 的的的的二二二二叉叉叉叉树树树树，栈栈栈栈需要需要需要需要 k k 个存储单位，即所需要的空间为个存储单位，即所需要的空间为个存储单位，即所需要的空间为个存储单位，即所需要的空间为 O O( (k k) )。 3. 3. 后序遍历二叉树的非递归算法后序遍历二叉树的非递归算法后序遍历二叉树的非递归算法后序遍历二叉树的非递归算法50(1)(1) 算算算算法法法法思思思思想想想想 在在

94、在在后后后后序序序序遍遍遍遍历历历历中中中中，当当当当搜搜搜搜索索索索指指指指针针针针指指指指向向向向某某某某一一一一结结结结点点点点时时时时，不不不不能能能能马马马马上上上上进进进进行行行行访访访访问问问问，而而而而先先先先要要要要遍遍遍遍历历历历其其其其左左左左子子子子树树树树，所所所所以以以以要要要要将将将将此此此此结结结结点点点点入入入入栈栈栈栈保保保保存存存存。当当当当遍遍遍遍历历历历完完完完它它它它的的的的左左左左子子子子树树树树后后后后，退退退退栈栈栈栈再再再再次次次次得得得得到到到到该该该该结结结结点点点点时时时时，还还还还不不不不能能能能进进进进行行行行访访访访问问问问，还还

95、还还需需需需要要要要遍遍遍遍历历历历其其其其右右右右子子子子树树树树。所以，需要再次将此结点入栈保存。所以，需要再次将此结点入栈保存。所以，需要再次将此结点入栈保存。所以，需要再次将此结点入栈保存。 为为为为了了了了区区区区别别别别同同同同一一一一结结结结点点点点的的的的两两两两次次次次入入入入栈栈栈栈，在在在在此此此此算算算算法法法法中中中中，设设设设计一个栈计一个栈计一个栈计一个栈 S S 存放存放存放存放 SElemType SElemType 类型的数据，其结构为：类型的数据，其结构为：类型的数据，其结构为：类型的数据，其结构为： typedef struct SElemType ty

96、pedef struct SElemType / / 顺序栈中数据的结构定义顺序栈中数据的结构定义顺序栈中数据的结构定义顺序栈中数据的结构定义 BiTNode BiTNode * * * *p;p;/ / 二叉树的结点指针二叉树的结点指针二叉树的结点指针二叉树的结点指针 int int tag; tag; / / 标志变量标志变量标志变量标志变量 / / 当当当当 tag = 0 tag = 0 时，表示该结点第一次入栈，暂不访问；时，表示该结点第一次入栈，暂不访问；时，表示该结点第一次入栈，暂不访问；时，表示该结点第一次入栈，暂不访问； / / 当当当当 tag = 1 tag = 1 时，

97、表示该结点第二次入栈，可以访问。时，表示该结点第二次入栈，可以访问。时，表示该结点第二次入栈，可以访问。时，表示该结点第二次入栈，可以访问。 SElemType; SElemType; 算算算算法法法法开开开开始始始始时时时时，先先先先将将将将栈栈栈栈 S S 初初初初始始始始化化化化，然然然然后后后后令令令令 p p 指指指指向向向向二二二二叉树的根结点，即叉树的根结点，即叉树的根结点，即叉树的根结点，即 p p = = rootroot。51 如如如如果果果果指指指指向向向向根根根根结结结结点点点点指指指指针针针针不不不不为为为为空空空空，先先先先将将将将 tag tag 置置置置零零零零

98、；再再再再将将将将 tag tag 和和和和根根根根结结结结点点点点一一一一道道道道送送送送入入入入栈栈栈栈中中中中；然然然然后后后后将将将将指指指指针针针针指指指指向向向向该该该该结结结结点点点点的左子树根结点；继续遍历。的左子树根结点；继续遍历。的左子树根结点；继续遍历。的左子树根结点；继续遍历。52 如如如如果果果果指指指指向向向向根根根根结结结结点点点点指指指指针针针针为为为为空空空空，则则则则应应应应退退退退至至至至上上上上一一一一层层层层，即即即即将将将将栈栈栈栈顶顶顶顶存存存存放放放放的的的的数数数数据据据据项项项项（SElemTypeSElemType类类类类型型型型，包包包包

99、括括括括二二二二叉叉叉叉树树树树结结结结点指针和标志变量）出栈：点指针和标志变量）出栈：点指针和标志变量）出栈：点指针和标志变量）出栈： 直到栈为空并且指针为空时，遍历结束。直到栈为空并且指针为空时，遍历结束。直到栈为空并且指针为空时，遍历结束。直到栈为空并且指针为空时，遍历结束。 若若若若 tag tag 为为为为 0 0，则则则则改改改改变变变变 tag tag 值值值值，将将将将 tag tag 置置置置 1 1；再再再再把把把把 tag tag 和和和和弹弹弹弹出出出出的的的的结结结结点点点点重重重重新新新新装装装装入入入入栈栈栈栈中中中中；然然然然后后后后将将将将指指指指针针针针指指

100、指指向向向向该该该该结结结结点的右子树根结点；继续遍历。点的右子树根结点；继续遍历。点的右子树根结点；继续遍历。点的右子树根结点；继续遍历。 若若若若 tag tag = = 1 1，则则则则访访访访问问问问弹弹弹弹出出出出的的的的结结结结点点点点，并并并并且且且且将将将将弹弹弹弹出出出出指指指指针置为空。针置为空。针置为空。针置为空。 void PostOrder (BiTree root) void PostOrder (BiTree root) /*采采用用二二叉叉链链表表存存储储结结构构，Visit 是是对对元元素素操操作作的的应应用用函函数数。 后后序序遍遍历历二二叉叉树树 T 的的

101、非非递递归算法，对每个元素调用函数归算法，对每个元素调用函数Visit*/ SElemtype Data; SElemtype Data; InitStack (S); Data.p = root; InitStack (S); Data.p = root; / 使用栈使用栈 S 存放待访问的根结点。令存放待访问的根结点。令 Data.p 指向二叉树根结点指向二叉树根结点 do do if ( Data.p ) if ( Data.p ) / 若若 Data.p 非空非空Data.tag = 0;Data.tag = 0;/ 将将 Data.tag 置零置零Push ( S, Data );P

102、ush ( S, Data );/ 将将 Data.tag 和和 Data.p 一道送入栈一道送入栈 S Data.p = Data.pData.p = Data.p- - - -lchild;lchild;/ 将指针指向左子树根结点，遍历左子树将指针指向左子树根结点，遍历左子树 (2) (2) 算法描算法描算法描算法描述述述述53 else else / 如果如果 Data.p 为空为空 Pop ( S, Data ); Pop ( S, Data );/ 将将 Data.tag 和和 Data.p 一道弹出一道弹出 if ( Data.tag = 0 ) if ( Data.tag = 0

103、 ) / 如果标志变量如果标志变量 Data.tag 为零为零 Data.tag = 1; Data.tag = 1; / 将将 Data.tag 置为置为 1 Push ( S, Data ) Push ( S, Data )/ 将将 Data.tag 和和 Data.p 一道送入栈一道送入栈 S 中中 Data.p = Data.p Data.p = Data.p- - - -rchild; rchild; / 将指针指向右子树根结点，遍历右子树将指针指向右子树根结点，遍历右子树 54 else else / 如果标志变量如果标志变量 Data.tag 为为 1 Visit ( Data.

104、p );Visit ( Data.p ); / 访问访问 Data.p 指向的结点指向的结点 Data.p = NULL;Data.p = NULL; / 将将 Data.p 指针置空指针置空 while ( ! Data.p & StackEmpty (S) ); while ( ! Data.p & StackEmpty (S) );return OK;return OK; / PostOrderTraverse(3)(3) 算算算算法法法法分分分分析析析析55PostOrder 非递归算法的时间复杂度非递归算法的时间复杂度 假假定定二二叉叉树树 root 有有 n 个个结结点点，算算法法

105、中中对对每每个个结结点点都都要要进进行行两两次次入入栈栈和和出出栈栈。因因此此，入入栈栈和和出出栈栈都都要要执执行行 2n 次，则入栈、出栈的时间复杂度为次，则入栈、出栈的时间复杂度为 O(n)。 此此外外，每每当当 Data.p 为为空空时时，就就弹弹出出栈栈顶顶的的数数据据项项 Data，然然后后根根据据 Data.tag 的的值值是是否否为为零零，或或访访问问刚刚弹弹出出的的结结点点，或或使使数数据据项项重重新新进进栈栈。重重新新入入栈栈的的时时间间已已经经算算在在入入栈栈、出出栈栈所所需需时时间间之之内内，访访问问结结点点的的时时间间显显然然为为 O(n)。所所以以，算算法法总总的的时

106、时间间复复杂杂度度为为 O(n)+O(n)，或者为，或者为 O(n)。PostOrder PostOrder 非递归算法所需附加空间非递归算法所需附加空间非递归算法所需附加空间非递归算法所需附加空间56 算算算算法法法法所所所所需需需需要要要要的的的的附附附附加加加加空空空空间间间间比比比比前前前前面面面面两两两两个个个个算算算算法法法法多多多多。由由由由于于于于 DataData.tag .tag 变变变变量量量量用用用用 1 1 位位位位二二二二进进进进制制制制就就就就可可可可以以以以表表表表示示示示，因因因因此此此此，所所所所需需需需要要要要的空间仍然为的空间仍然为的空间仍然为的空间仍然

107、为 O O( (k k) )，其中，其中，其中，其中 k k 为二叉树的深度。为二叉树的深度。为二叉树的深度。为二叉树的深度。后序遍历方法二算法思想后序遍历方法二算法思想后序遍历方法二算法思想后序遍历方法二算法思想57 从从从从当当当当前前前前结结结结点点点点开开开开始始始始, ,进进进进栈栈栈栈并并并并走走走走左左左左子子子子树树树树, ,直直直直到到到到左左左左子子子子树树树树为为为为空空空空 否则，走右子树。否则，走右子树。否则，走右子树。否则，走右子树。直到栈为空并且指针为空时，遍历结束。直到栈为空并且指针为空时，遍历结束。直到栈为空并且指针为空时，遍历结束。直到栈为空并且指针为空时，

108、遍历结束。 如如如如果果果果栈栈栈栈顶顶顶顶结结结结点点点点的的的的右右右右子子子子树树树树为为为为空空空空, , , ,或或或或栈栈栈栈顶顶顶顶结结结结点点点点的的的的右右右右子子子子树树树树为为为为刚刚刚刚访访访访问问问问过过过过的的的的结结结结点点点点, , , ,则则则则退退退退栈栈栈栈并并并并访访访访问问问问，然然然然后后后后将将将将当当当当前前前前结结结结点点点点指指指指针针针针置为空。置为空。置为空。置为空。 遍遍遍遍历历历历二二二二叉叉叉叉树树树树是是是是二二二二叉叉叉叉树树树树各各各各种种种种操操操操作作作作的的的的基基基基础础础础，可可可可以以以以在在在在遍遍遍遍历历历历的

109、的的的过过过过程程程程中中中中对对对对结结结结点点点点进进进进行行行行各各各各种种种种操操操操作作作作，比比比比如如如如：对对对对于于于于一一一一棵棵棵棵已已已已知知知知树树树树可可可可以以以以求求求求结结结结点点点点的的的的双双双双亲亲亲亲，求求求求结结结结点点点点的的的的孩孩孩孩子子子子结结结结点点点点，判判判判定定定定结结结结点点点点所所所所在在在在的的的的层层层层次次次次等等等等；反反反反之之之之，给给给给定定定定一一一一棵棵棵棵二二二二叉叉叉叉树树树树的的的的遍遍遍遍历历历历序序序序列列列列结点，可建立二叉树的存储结构。结点，可建立二叉树的存储结构。结点，可建立二叉树的存储结构。结点

110、，可建立二叉树的存储结构。586.3.4 建立二叉树的算法建立二叉树的算法 例例例例如如如如，如如如如果果果果按按按按照照照照先先先先序序序序序序序序列列列列建建建建立立立立二二二二叉叉叉叉树树树树的的的的二二二二叉叉叉叉链链链链表表表表结结结结构构构构，对对对对下下下下图图图图所所所所示示示示二二二二叉叉叉叉树树树树，可可可可以以以以按按按按照照照照“ “扩扩扩扩展展展展先先先先序序序序遍遍遍遍历历历历顺顺顺顺序序序序” ”读入字符，即可以建立相应的二叉链表。读入字符，即可以建立相应的二叉链表。读入字符，即可以建立相应的二叉链表。读入字符，即可以建立相应的二叉链表。A AB BC CD DF

111、 FE EG GA A B C B C D ED E G G F F59 void CreateBiTree ( BiTree *bt) void CreateBiTree ( BiTree *bt) /*按按先先序序次次序序输输入入二二叉叉树树中中结结点点的的值值（一一个个字字符符）， 圆圆点点字字符符表表示示空空树树。构构造造二二叉叉链链表表表示的二叉树表示的二叉树 T。*/ / CreateBiTree scanf (&ch); scanf (&ch);/ / 输入字符输入字符 if ( ch = = if ( ch = = ) *bt = NULL;) *bt = NULL;/ / 若

112、是字符则令指针为空若是字符则令指针为空若是字符则令指针为空若是字符则令指针为空 else else if ( ! ( *bt = ( BiTNode if ( ! ( *bt = ( BiTNode * * * * ) malloc ( sizeof ( BiTNode ) ) ) ) ) malloc ( sizeof ( BiTNode ) ) ) ) return; return; (*bt) (*bt)- - - -data = ch;data = ch;/ 生成根结点生成根结点 CreateBiTree ( &(*bt) CreateBiTree ( &(*bt)- - - -LCh

113、ild );LChild );/ 构造左子树构造左子树 CreateBiTree ( &(*bt) CreateBiTree ( &(*bt)- - - -RChild );RChild );/ 构造右子树构造右子树 60 先先先先序序序序、中中中中序序序序和和和和后后后后序序序序遍遍遍遍历历历历二二二二叉叉叉叉树树树树的的的的结结结结点点点点比比比比处处处处理理理理单单单单链链链链表表表表中中中中的的的的一一一一个个个个结结结结点点点点要要要要复复复复杂杂杂杂。对对对对单单单单链链链链表表表表，我我我我们们们们曾曾曾曾经经经经定定定定义义义义了了了了求求求求前前前前驱和求后继的运算。那么在树

114、中可以吗？驱和求后继的运算。那么在树中可以吗？驱和求后继的运算。那么在树中可以吗？驱和求后继的运算。那么在树中可以吗？6.4 二叉线索树二叉线索树61二叉线索树的引出二叉线索树的引出二叉线索树的定义二叉线索树的定义二叉线索树的存储结构二叉线索树的存储结构二叉线索树的操作二叉线索树的操作 (1) (1) 先序排序如何实现求前驱和求后继运算？先序排序如何实现求前驱和求后继运算？先序排序如何实现求前驱和求后继运算？先序排序如何实现求前驱和求后继运算？A AB BD DF FE EG G后继后继后继后继后继后继后继后继626.4.1 线索二叉树的引出线索二叉树的引出 对对对对于于于于求求求求后后后后继

115、继继继运运运运算算算算，如如如如果果果果所所所所考考考考虑虑虑虑的的的的结结结结点点点点是是是是非非非非叶叶叶叶子子子子结结结结点点点点，那么该结点的左孩子就是它的后继结点。那么该结点的左孩子就是它的后继结点。那么该结点的左孩子就是它的后继结点。那么该结点的左孩子就是它的后继结点。 如如如如果果果果结结结结点点点点的的的的左左左左孩孩孩孩子子子子不不不不存存存存在在在在，那那那那么么么么该该该该结结结结点点点点的的的的右右右右孩孩孩孩子子子子就就就就是它的后继结点。是它的后继结点。是它的后继结点。是它的后继结点。 如如如如果果果果所所所所考考考考虑虑虑虑的的的的结结结结点点点点是是是是叶叶叶叶

116、子子子子结结结结点点点点，那那那那么么么么要要要要找找找找到到到到该该该该结结结结点点点点的后继结点，就必须遍历二叉树。的后继结点，就必须遍历二叉树。的后继结点，就必须遍历二叉树。的后继结点，就必须遍历二叉树。 对对对对于于于于求求求求前前前前驱驱驱驱运运运运算算算算，在在在在先先先先序序序序排排排排序序序序下下下下，不不不不论论论论何何何何种种种种情情情情况况况况都都都都需要遍历二叉树。需要遍历二叉树。需要遍历二叉树。需要遍历二叉树。 (2) (2) 后序排序如何实现求前驱和求后继运算？后序排序如何实现求前驱和求后继运算？后序排序如何实现求前驱和求后继运算？后序排序如何实现求前驱和求后继运算

117、？A AB BD DF FE EG G前驱前驱前驱前驱前驱前驱前驱前驱63 对对对对于于于于求求求求前前前前驱驱驱驱运运运运算算算算，如如如如果果果果所所所所考考考考虑虑虑虑的的的的结结结结点点点点是是是是非非非非叶叶叶叶子子子子结结结结点点点点，那么该结点的右孩子就是它的前驱结点。那么该结点的右孩子就是它的前驱结点。那么该结点的右孩子就是它的前驱结点。那么该结点的右孩子就是它的前驱结点。 如果该结点的右孩子不存在，那么该结点的左孩子如果该结点的右孩子不存在，那么该结点的左孩子如果该结点的右孩子不存在，那么该结点的左孩子如果该结点的右孩子不存在，那么该结点的左孩子就是它的前驱结点。就是它的前驱

118、结点。就是它的前驱结点。就是它的前驱结点。 如果所考虑的结点是叶子结点，那么要找到该结点如果所考虑的结点是叶子结点，那么要找到该结点如果所考虑的结点是叶子结点，那么要找到该结点如果所考虑的结点是叶子结点，那么要找到该结点的前驱结点，就必须遍历二叉树。的前驱结点，就必须遍历二叉树。的前驱结点，就必须遍历二叉树。的前驱结点，就必须遍历二叉树。 对于求后继运算，在后序排序下，不论何种情况都对于求后继运算，在后序排序下，不论何种情况都对于求后继运算，在后序排序下，不论何种情况都对于求后继运算，在后序排序下，不论何种情况都需要遍历二叉树。需要遍历二叉树。需要遍历二叉树。需要遍历二叉树。 (3) (3)

119、中序排序如何实现求前驱和求后继运算？中序排序如何实现求前驱和求后继运算？中序排序如何实现求前驱和求后继运算？中序排序如何实现求前驱和求后继运算？ 对对对对于于于于求求求求后后后后继继继继运运运运算算算算，若若若若所所所所考考考考虑虑虑虑的的的的结结结结点点点点有有有有右右右右孩孩孩孩子子子子，那那那那么么么么就就就就要要要要从从从从该该该该右右右右孩孩孩孩子子子子开开开开始始始始，顺顺顺顺着着着着该该该该右右右右孩孩孩孩子子子子的的的的左左左左孩孩孩孩子子子子链链链链域域域域找找找找下下下下去去去去，一一一一直直直直找找找找到到到到左左左左孩孩孩孩子子子子的的的的链链链链域域域域是是是是空空空

120、空为为为为止止止止，最最最最后后后后这这这这个个个个结结结结点点点点就就就就是是是是所所所所考考考考虑虑虑虑结结结结点点点点的的的的后后后后继继继继结结结结点点点点；若若若若所所所所考考考考虑虑虑虑的的的的结结结结点点点点无无无无右右右右孩孩孩孩子子子子，那那那那么就要遍历二叉树。么就要遍历二叉树。么就要遍历二叉树。么就要遍历二叉树。N NR R1 1R R2 2R Rk k后继后继后继后继64 对对于于求求前前驱驱运运算算，若若所所考考虑虑的的结结点点有有左左孩孩子子，那那么么就就要要从从该该左左孩孩子子开开始始，顺顺着着该该左左孩孩子子的的右右孩孩子子链链域域找找下下去去，一一直直找找到到

121、右右孩孩子子的的链链域域是是空空为为止止，最最后后这这个个结结点点就就是是所所考考虑虑结结点点的的前前驱驱结结点点；若若所所考考虑虑的的结结点点无无左左孩孩子子，那那么就要遍历二叉树。么就要遍历二叉树。N NR R1 1R R2 2R Rk k前驱前驱前驱前驱 方方方方法法法法一一一一：为为为为了了了了方方方方便便便便地地地地实实实实现现现现求求求求结结结结点点点点的的的的前前前前驱驱驱驱和和和和求求求求后后后后继继继继运运运运算算算算，可可可可以以以以在在在在原原原原有有有有二二二二叉叉叉叉链链链链表表表表的的的的结结结结点点点点结结结结构构构构中中中中，再再再再增增增增加加加加两两两两个个

122、个个链链链链域域域域：plink plink 和和和和 nlinknlink，分分分分别别别别指指指指示示示示结结结结点点点点在在在在依依依依任任任任一一一一次次次次序序序序遍历时得到的前驱和后继信息。遍历时得到的前驱和后继信息。遍历时得到的前驱和后继信息。遍历时得到的前驱和后继信息。 (4) (4) 如如如如何何何何保保保保存存存存在在在在遍遍遍遍历历历历二二二二叉叉叉叉树树树树的的的的动动动动态态态态过过过过程程程程中中中中得得得得到到到到的的的的某某某某一结点的前驱和后继信息？一结点的前驱和后继信息？一结点的前驱和后继信息？一结点的前驱和后继信息？ 方法有两个。方法有两个。方法有两个。方

123、法有两个。65 方方方方法法法法二二二二： 在在在在有有有有 n n 个个个个结结结结点点点点的的的的二二二二叉叉叉叉树树树树中中中中，有有有有 n n+1 +1 个个个个空空空空链链链链域域域域。由由由由此此此此，可可可可以以以以利利利利用用用用这这这这些些些些空空空空链链链链域域域域来来来来存存存存放放放放结结结结点点点点的的的的前前前前驱驱驱驱和后继的信息。和后继的信息。和后继的信息。和后继的信息。66 试试试试做做做做如如如如下下下下规规规规定定定定：若若若若结结结结点点点点有有有有左左左左子子子子树树树树，则则则则其其其其 lchild lchild 域域域域指指指指示示示示其其其其

124、左左左左孩孩孩孩子子子子，否否否否则则则则令令令令 lchild lchild 域域域域指指指指示示示示其其其其前前前前驱驱驱驱；若若若若结结结结点点点点有有有有右右右右子子子子树树树树，则则则则其其其其 rchild rchild 域域域域指指指指示示示示其其其其右右右右孩孩孩孩子子子子，否否否否则则则则令令令令 rchild rchild 域域域域指示其后继。指示其后继。指示其后继。指示其后继。 为为为为了了了了避避避避免免免免混混混混淆淆淆淆，需需需需改改改改变变变变二二二二叉叉叉叉链链链链表表表表的的的的结结结结点点点点结结结结构构构构，增增增增加两个标志域：加两个标志域：加两个标志域

125、：加两个标志域：ltag ltag 和和和和 rtag rtag。lchildlchildltagltagdatadatartagrtagrchildrchild其中：其中：其中：其中：ltag =ltag =0 01 1lchild lchild 域指示结点的左孩子域指示结点的左孩子域指示结点的左孩子域指示结点的左孩子lchildlchild 域指示结点的前驱域指示结点的前驱域指示结点的前驱域指示结点的前驱rtag =rtag =0 01 1rchild rchild 域指示结点的右孩子域指示结点的右孩子域指示结点的右孩子域指示结点的右孩子rchildrchild 域指示结点的后继域指示结点

126、的后继域指示结点的后继域指示结点的后继左孩子或前驱域左孩子或前驱域左孩子或前驱域左孩子或前驱域右孩子或后继域右孩子或后继域右孩子或后继域右孩子或后继域数据域数据域数据域数据域左标志域左标志域左标志域左标志域右标志域右标志域右标志域右标志域676.4.2 二叉线索树的定义二叉线索树的定义 这这这这种种种种存存存存储储储储方方方方式式式式利利利利用用用用了了了了二二二二叉叉叉叉链链链链表表表表中中中中原原原原有有有有的的的的空空空空链链链链域域域域，提高了结构的存储密度，是一种实用的做法。提高了结构的存储密度，是一种实用的做法。提高了结构的存储密度，是一种实用的做法。提高了结构的存储密度，是一种实

127、用的做法。 相关概念如下：相关概念如下：相关概念如下：相关概念如下：68 线线线线索索索索链链链链表表表表：以以以以这这这这种种种种结结结结点点点点结结结结构构构构构构构构成成成成的的的的二二二二叉叉叉叉链链链链表表表表作作作作为二叉树的存储结构称之。为二叉树的存储结构称之。为二叉树的存储结构称之。为二叉树的存储结构称之。 线线线线索索索索：在在在在线线线线索索索索链链链链表表表表中中中中指指指指向向向向结结结结点点点点前前前前驱驱驱驱和和和和后后后后继继继继的的的的指指指指针称之。针称之。针称之。针称之。 线索二叉树：加上线索的二叉树称之。线索二叉树：加上线索的二叉树称之。线索二叉树：加上线

128、索的二叉树称之。线索二叉树：加上线索的二叉树称之。 线线线线索索索索化化化化：对对对对二二二二叉叉叉叉树树树树以以以以某某某某种种种种次次次次序序序序遍遍遍遍历历历历使使使使其其其其变变变变为为为为线线线线索二叉树的过程称之。索二叉树的过程称之。索二叉树的过程称之。索二叉树的过程称之。typedef struct BiThrNode typedef struct BiThrNode DataType DataType data; data; / 数据域数据域 struct BiThrNode struct BiThrNode * * * *lchild, lchild, * * * *rchi

129、ld;rchild;/ 左右孩子指针左右孩子指针 PointerTag PointerTag ltag, rtag; ltag, rtag; / 左右标志左右标志 BiThrNode, BiThrNode, * * * *BiThrTree;BiThrTree; / 线索二叉树的类型名线索二叉树的类型名通常，线索二叉树指中序线索二叉树，简称线索树。通常，线索二叉树指中序线索二叉树，简称线索树。通常，线索二叉树指中序线索二叉树，简称线索树。通常，线索二叉树指中序线索二叉树，简称线索树。696.4.3 二叉树线索的存储结构二叉树线索的存储结构 为了方便起见，仿照线性表的存储结构：为了方便起见，仿照

130、线性表的存储结构：为了方便起见，仿照线性表的存储结构：为了方便起见，仿照线性表的存储结构：70 在在在在二二二二叉叉叉叉树树树树线线线线索索索索链链链链表表表表上上上上也也也也添添添添加加加加一一一一个个个个头头头头结结结结点点点点，并并并并令令令令其其其其 lchild lchild 域域域域指指指指针针针针指指指指向向向向二二二二叉叉叉叉树树树树的的的的根根根根结结结结点点点点，其其其其 rchild rchild 域域域域指指指指针指向中序遍历二叉树时访问的最后一个结点；针指向中序遍历二叉树时访问的最后一个结点；针指向中序遍历二叉树时访问的最后一个结点；针指向中序遍历二叉树时访问的最后一

131、个结点； 令令令令二二二二叉叉叉叉树树树树中中中中序序序序序序序序列列列列第第第第一一一一个个个个结结结结点点点点的的的的 lchild lchild 域域域域指指指指针和最后一个结点的针和最后一个结点的针和最后一个结点的针和最后一个结点的 rchild rchild 域指针均指向头结点。域指针均指向头结点。域指针均指向头结点。域指针均指向头结点。 (1) (1) 算法思想算法思想算法思想算法思想71 判判判判断断断断给给给给定定定定结结结结点点点点 t t 的的的的左左左左指指指指针针针针 lchild lchild 是是是是否否否否指指指指向向向向头头头头结结结结点点点点 ThrtThrt

132、。若是，则返回。若是，则返回。若是，则返回。若是，则返回 ；若否，则继续下面的操作。；若否，则继续下面的操作。；若否，则继续下面的操作。；若否，则继续下面的操作。 判判判判断断断断给给给给定定定定结结结结点点点点 t t 的的的的左左左左标标标标志志志志 ltag ltag 是是是是否否否否为为为为 1 1。若若若若为为为为 1 1，则则则则t-LChildt-LChild指指指指向向向向t t的的的的前前前前驱驱驱驱。当当当当t-LChild=0t-LChild=0时时时时，则则则则说说说说明明明明 p p 指指指指向向向向结结结结点点点点 t t 的的的的左左左左孩孩孩孩子子子子(p=t-

133、LChild)(p=t-LChild)，这这这这时时时时就就就就需需需需要要要要顺顺顺顺着着着着 p p 所所所所指指指指结结结结点点点点的的的的右右右右链链链链域域域域寻寻寻寻找找找找，直直直直到到到到结结结结点点点点右右右右标标标标志志志志 rtag rtag 为为为为 1 1；若若若若为为为为 1 1，则则则则说说说说明明明明 p p 指指指指向向向向结结结结点点点点 t t 的的的的线线线线索索索索，即即即即 p p 所所所所指指指指向向向向的的的的结结结结点就是结点点就是结点点就是结点点就是结点 t t 的前驱。的前驱。的前驱。的前驱。6.4.4 二叉线索树的操作二叉线索树的操作 1

134、. 1. 在二叉线索树中求结点的中序前驱在二叉线索树中求结点的中序前驱在二叉线索树中求结点的中序前驱在二叉线索树中求结点的中序前驱 int InPre( BiThrTree t, int InPre( BiThrTree t, BiThrTreeBiThrTree p ) p ) / t 指向中序线索树中某一结点，指向中序线索树中某一结点，p 返回此结点的前驱；返回此结点的前驱； 并返回并返回 OK p = t p = t- - - -lchild;lchild;/ 将将 t 的的 lchild 域的值赋给域的值赋给 p if ( p = Thrt ) if ( p = Thrt ) retu

135、rn ERROR; return ERROR; / 若若 p 指向头结点，则出错指向头结点，则出错 if ( t if ( t- - - -ltag = 0)ltag = 0) / 若若 t 的左标志为的左标志为 0 while ( p while ( p- - - -rtag = =0) p = prtag = =0) p = p- - - -rchild; rchild; / 顺着顺着 t 的左孩子的右链域寻找，直到结点右标志是的左孩子的右链域寻找，直到结点右标志是 1 为止为止 return OK; return OK; / InPre(2) (2) 算法实现算法实现算法实现算法实现72

136、 (3) (3) 算法分析算法分析算法分析算法分析73 如如如如果果果果 t t 所所所所指指指指向向向向结结结结点点点点的的的的左左左左孩孩孩孩子子子子有有有有 k k 层层层层右右右右孩孩孩孩子子子子，则则则则需需需需要要要要进进进进行行行行 k k+1 +1 次次次次比比比比较较较较，因因因因此此此此 Inpre Inpre 算算算算法法法法的的的的时时时时间间间间复复复复杂杂杂杂度度度度为为为为 O O( (k k) )。 (1) (1) 算法思想算法思想算法思想算法思想74 判判判判断断断断给给给给定定定定结结结结点点点点 t t 的的的的右右右右指指指指针针针针 rchild rc

137、hild 是是是是否否否否指指指指向向向向头头头头结结结结点点点点 ThrtThrt。若是，则返回。若是，则返回。若是，则返回。若是，则返回 ERROR ERROR；若否，则继续。；若否，则继续。；若否，则继续。；若否，则继续。 判判判判断断断断给给给给定定定定结结结结点点点点 t t 的的的的右右右右标标标标志志志志 rtag rtag 是是是是否否否否为为为为 0 0。若若若若为为为为 0 0，则则则则用用用用 p p 指指指指向向向向结结结结点点点点 t t 的的的的右右右右孩孩孩孩子子子子，这这这这时时时时就就就就需需需需要要要要顺顺顺顺着着着着 p p 所所所所指指指指结结结结点点点

138、点的的的的左左左左链链链链域域域域寻寻寻寻找找找找，直直直直到到到到结结结结点点点点左左左左标标标标志志志志 ltag ltag 为为为为 1 1；若若若若为为为为 1 1，则则则则说说说说明明明明 p p 指指指指向向向向结结结结点点点点 t t 的的的的线线线线索索索索，即即即即 p p 所所所所指指指指向向向向的的的的结结结结点点点点就就就就是是是是结点结点结点结点 t t 的后继。的后继。的后继。的后继。 2. 2. 在二叉线索树中求结点的中序后继在二叉线索树中求结点的中序后继在二叉线索树中求结点的中序后继在二叉线索树中求结点的中序后继 int InNext ( BiThrTree t

139、, BiThrTree p ) / t 指向中序线索树中某一结点，指向中序线索树中某一结点，p 返回此结点的后继；返回此结点的后继； 并返回并返回 OK p = t- -rchild;/ 将将 t 的的 rchild 域值赋给域值赋给 p if ( p = =Thrt ) return ERROR;/ 若若 p 指向头结点，则出错指向头结点，则出错 if ( t- -rtag = 0 ) / 若若 t 的右标志为的右标志为 0 while ( p- -ltag = =0) p = p- -lchild; / 顺着顺着 t 的右孩子的左链域寻找，直到结点左标志是的右孩子的左链域寻找，直到结点左标

140、志是 1 为止为止 return OK; / InNext(2) (2) 算法实现算法实现算法实现算法实现75 (3) 算法分析算法分析76 如如果果 t 所所指指向向结结点点的的右右孩孩子子有有 k 层层左左孩孩子子，则则需需要要进进行行 k+1 次次比比较较，因因此此 Next_Thr 算算法法的的时时间间复复杂杂度度为为 O(k)。 下下下下面面面面给给给给出出出出将将将将值值值值为为为为 e e 的的的的新新新新结结结结点点点点 r r 插插插插入入入入到到到到中中中中序序序序线线线线索索索索树树树树中中中中，作为结点作为结点作为结点作为结点 p p 的右孩子。的右孩子。的右孩子。的右

141、孩子。 (1) 算法思想算法思想77 建立新结点建立新结点 r，使其数据域的值为，使其数据域的值为 e； 如果结点如果结点 p 无右孩子，则做：无右孩子，则做： 将新结点将新结点 r 插入线索树中作为结点插入线索树中作为结点 p 的右孩子。的右孩子。 结结点点 p 的的后后继继是是新新结结点点 r的的后后继继，r的的前前驱驱是是 p；且；且r.ltag = 1，r.rtag = 1。 修改修改 p.rchild,使其指向新结点使其指向新结点 r,且且 t. .rtag = 0。 3. 3. 在二叉线索树中插入结点在二叉线索树中插入结点在二叉线索树中插入结点在二叉线索树中插入结点 如果如果 p

142、有右孩子，则做：有右孩子，则做：78 将新结点将新结点 r 插入到线索树中作为结点插入到线索树中作为结点 p 的右孩子；的右孩子； p 的的右右子子树树在在新新结结点点 r 插插入入之之后后，应应该该成成为为新新结结点点 r 的的右右子子树树，这这样样就就有有 r.rtag = 0；新新结结点点 r 的的前前驱驱是是 p；且；且 r.ltag = 1； 修改修改 p.rchild，使其指向新结点，使其指向新结点 r，且，且 p. .rtag = 0。 求求出出新新结结点点 r 的的后后继继，并并修修改改 r 的的后后继继的的 lchild 域，使其指向新结点域，使其指向新结点 r，即这个结点的

143、前驱应该为，即这个结点的前驱应该为 q。int InsNode(BiThrTree Thrt, BiThrTree p, BiThrTree r) / 将新结点将新结点r插入插入到中序线索树中作为结点到中序线索树中作为结点 p的右孩子，并返回的右孩子，并返回 OK if ( ! ( r = ( BiThrTree ) malloc ( sizeof ( BiThrNode ) ) ) ) exit ( OVERFLOW ); r- -data = e; r- -rchild = p- -rchild;r- -rtag = p- -rtag; r- -lchild = p;r- -ltag =

144、1; p- -rchild = r;p- -rtag = 0; if ( r- -rtag = 0 ) InNext ( &r, &s ); s- -lchild = r; / 若若 r 的右标志为的右标志为 0，则寻找，则寻找 r 的后继的后继 s，并将，并将 r 作为作为 s 的前驱的前驱 return OK /InsNode(2) 算法描述算法描述79 (3) 算法分析算法分析80 InsNode 算算法法的的执执行行时时间间主主要要取取决决于于 InNext (r, s) 算算法法（求求结结点点 r 的的后后继继 s）。如如果果 r 的的右右孩孩子子有有 k 层层左左孩孩子子，则则寻寻

145、找找 r 的的后后继继 s 需需要要进进行行 k+1 次次比比较较，因因此此 Next_Thr 算算法法时时间间复复杂杂度度为为 O(k)。故故 InNext 算算法法的的时间复杂度也为时间复杂度也为 O(k)。 同同理理，可可以以编编写写出出将将值值为为 e 的的新新结结点点 r 插插入入到到中中序序线索树中，作为结点线索树中，作为结点 p 的左孩子。的左孩子。 (1) 算法思想算法思想81 令令 p 指指向向根根结结点点，且且当当二二叉叉树树为为非非空空树树或或遍遍历未结束时，继续做如下操作；历未结束时，继续做如下操作； 顺顺着着 p 的的左左链链域域寻寻找找，直直到到结结点点的的左左标标

146、志志域域 ltag = 1 时为止，即结点的左链域时为止，即结点的左链域 lchild 为空；为空； 访问其左链域访问其左链域 lchild 为空的结点；为空的结点； 4. 遍历二叉线索树遍历二叉线索树 当当 p 的的右右标标志志域域 rtag = 1，并并且且右右链链域域 rchild 不不指指向向头头结结点点时时（即即 p 的的 rchild 指指向向后后继继），则则访访问问后继；后继；82 当当 p 的的右右标标志志域域 rtag = 0（即即 p 的的 rchild 指指向右孩子），或右链域向右孩子），或右链域 rchild 指向头结点时，则令指向头结点时，则令 p = p- -rch

147、ild 当当 p 指指向向非非空空树树或或遍遍历历未未结结束束时时，则则重重复复执执行上述步骤行上述步骤 。void TInOrder ( BiThrTree Thrt) /*Thrt 指向中序线索树的头结点，指向中序线索树的头结点， 头结点的左链域头结点的左链域 lchild 指向根结点，遍历中序线索指向根结点，遍历中序线索树树 T 的非递归算法，的非递归算法， 对每个数据元素调用函数对每个数据元素调用函数 Visit 。*/ p = Thrt-lchild; / p 指向根结点指向根结点 while ( p != Thrt ) / 当空树或遍历结束时，当空树或遍历结束时，p = = Thr

148、t while ( p-ltag = = 0 ) p = p-lchild; / 顺着顺着 p 的左链域寻找，直到结点左标志是的左链域寻找，直到结点左标志是 1 时为止时为止 if ( ! Visit ( p-data ) ) return ERROR; / 访问其左子树为空的结点访问其左子树为空的结点 while ( p-rtag = = 1 & p-rchild ! = Thrt ) / 当当 p 右标志为右标志为 1 且右链域且右链域 rchild 不为头结点时，不为头结点时， 则访问后继结点则访问后继结点 p = p-rchild; Visit ( p-data ); / while

149、/ InOrderTraverse(2) (2) 算法描述算法描述 void TInOrder ( BiThrTree Thrt) /*Thrt 指指向向中中序序线线索索树树的的头头结结点点， 头头结结点点的的左左链链域域 lchild 指指向向根根结结点点， 遍遍历历中中序序线线索树索树 T 的非递归算法，的非递归算法， 对每个数据元素调用函数对每个数据元素调用函数 Visit 。*/ p = Thrt- -lchild; / / p p 指向根结点指向根结点指向根结点指向根结点 while ( p != Thrt Thrt ) / 当空树或遍历结束时，当空树或遍历结束时，p = = Thr

150、t while ( p- -ltag = = 0 ) p = p- -lchild; / 顺着顺着 p 的左链域寻找，直到结点左标志是的左链域寻找，直到结点左标志是 1 时为止时为止(2) (2) 算法描述算法描述算法描述算法描述84 if ( ! Visit ( p- -data ) ) return ERROR; / 访问其左子树为空的结点访问其左子树为空的结点 while ( p while ( p- - - -rtag = = 1 & prtag = = 1 & p- - - -rchild ! = Thrt ) rchild ! = Thrt ) / / 当当当当 p p 右标志为右

151、标志为右标志为右标志为 1 1 且右链域且右链域且右链域且右链域 rchild rchild 不为头结点时，不为头结点时，不为头结点时，不为头结点时， 则访问后继结点则访问后继结点则访问后继结点则访问后继结点p = pp = p- - - -rchild;rchild; Visit ( p Visit ( p- - - -data );data ); (3) 算法分析算法分析85 TInOrder 算法的时间复杂度为算法的时间复杂度为 O(n)。 在在中中序序线线索索树树上上遍遍历历，虽虽然然时时间间复复杂杂度度也也为为 O(n)，但但是是其其常常数数因因子子要要比比在在中中序序二二叉叉树树上

152、上遍遍历历小小，并并且且不不需要设立栈。需要设立栈。 (1) 算法思想算法思想86 由由于于线线索索化化的的实实质质是是将将二二叉叉链链表表中中的的空空指指针针改改为为指指向向前前驱驱或或后后继继线线索索，而而前前驱驱或或后后继继的的信信息息只只有有在在遍遍历历时时才才能能得得到到，因因此此线线索索化化的的过过程程即即为为在在遍遍历历的的过过程程中修改空指针的过程。中修改空指针的过程。 为为了了记记下下遍遍历历过过程程中中访访问问结结点点的的先先后后关关系系，需需要要附附设设指指针针 pre 始始终终指指向向刚刚刚刚访访问问过过的的结结点点，若若指指针针 p 指指向当前访问的结点，则向当前访问

153、的结点，则 pre 指向它的前驱。指向它的前驱。 先线索化以先线索化以 root 为根的二叉树，为根的二叉树， 后线索化头结点。后线索化头结点。 5. 二叉树的线索化二叉树的线索化876.5 树和森林与二叉树的转换树和森林与二叉树的转换树与二叉树的转换树与二叉树的转换森林与二叉树的转换森林与二叉树的转换树和森林的遍历树和森林的遍历 由由于于树树和和二二叉叉树树都都可可以以使使用用二二叉叉链链表表作作为为存存储储结结构构，因因此此可可以以用用二二叉叉链链表表作作为为媒媒介介导导出出树树与与二二叉叉树树之之间间的的一一个个对对应应关关系系。也也就就是是说说，给给定定一一棵棵树树，可可以以找找到到惟

154、惟一一的的一一棵棵二二叉叉树树与与之之对对应应，从从物物理理结结构构来来看看，它它们的二叉链表是相同的，只是解释不同而已。们的二叉链表是相同的，只是解释不同而已。886.5.1 树与二叉树的转换树与二叉树的转换 1. 树转换为二叉树树转换为二叉树 树转换为二叉树的可以按照如下步骤进行：树转换为二叉树的可以按照如下步骤进行：89 加线：在各兄弟结点之间加一连线；加线：在各兄弟结点之间加一连线； 除除线线：对对任任何何结结点点，除除了了其其最最左左边边的的孩孩子子之之外外，去掉该结点与其余孩子的各枝；去掉该结点与其余孩子的各枝； 旋旋转转：将将添添加加的的水水平平连连线线和和原原有有的的连连线线，

155、以以树树的根结点为轴心，按顺时针方向旋转的根结点为轴心，按顺时针方向旋转 45。 2. 2. 二叉树还原为树二叉树还原为树二叉树还原为树二叉树还原为树 二叉树还原为树可以按照如下步骤进行：二叉树还原为树可以按照如下步骤进行：二叉树还原为树可以按照如下步骤进行：二叉树还原为树可以按照如下步骤进行：90 加加线线：若若 p 结结点点是是双双亲亲的的左左孩孩子子，则则将将 p 结结点点的的右右孩孩子子，右右孩孩子子的的右右孩孩子子，沿沿着着右右分分支支搜搜索索到到的的所有右孩子，都分别与所有右孩子，都分别与 p 结点的双亲用线连起来；结点的双亲用线连起来； 除除线线：去去除除原原二二叉叉树树中中所所

156、有有双双亲亲结结点点与与右右孩孩子子的的连线；连线； 旋旋转转：以以树树的的根根结结点点为为轴轴心心，按按逆逆时时针针方方向向旋旋转转 45。 从从从从树树树树与与与与二二二二叉叉叉叉树树树树的的的的转转转转换换换换中中中中可可可可知知知知，转转转转换换换换之之之之后后后后的的的的二二二二叉叉叉叉树树树树的的的的根根根根结结结结点点点点没没没没有有有有右右右右孩孩孩孩子子子子，如如如如果果果果把把把把森森森森林林林林中中中中的的的的第第第第二二二二棵棵棵棵树树树树的的的的根根根根结结结结点点点点看看看看成成成成是是是是第第第第一一一一棵棵棵棵树树树树的的的的根根根根结结结结点点点点的的的的兄兄

157、兄兄弟弟弟弟，则则则则同同同同样样样样可可可可以以以以导导导导出森林和二叉树的对应关系。出森林和二叉树的对应关系。出森林和二叉树的对应关系。出森林和二叉树的对应关系。916.5.2 森林与二叉树的转换森林与二叉树的转换 1. 1. 森林转换为二叉树森林转换为二叉树森林转换为二叉树森林转换为二叉树 森林转换为二叉树可以按照如下步骤进行：森林转换为二叉树可以按照如下步骤进行：森林转换为二叉树可以按照如下步骤进行：森林转换为二叉树可以按照如下步骤进行：92 转换：转换：转换：转换：将森林中的每一棵树转换成二叉树；将森林中的每一棵树转换成二叉树；将森林中的每一棵树转换成二叉树；将森林中的每一棵树转换成

158、二叉树； 连线：连线：连线：连线：将各棵转换后的二叉树的根结点相连；将各棵转换后的二叉树的根结点相连；将各棵转换后的二叉树的根结点相连；将各棵转换后的二叉树的根结点相连； 旋旋旋旋转转转转：将将将将添添添添加加加加的的的的水水水水平平平平连连连连线线线线和和和和原原原原有有有有的的的的连连连连线线线线以以以以第第第第一一一一棵棵棵棵树根结点为轴心，按顺时针方向粗略地旋转树根结点为轴心，按顺时针方向粗略地旋转树根结点为轴心，按顺时针方向粗略地旋转树根结点为轴心，按顺时针方向粗略地旋转 45 45。A AB BD DC CE EF FG GHHI IJ JA AB BC CD DE EF FG G

159、HHI IJ JA AB BE EC CD DF FG GHHI IJ J93转转转转 换换换换连连连连 线线线线旋旋旋旋 转转转转 经经经经过过过过这这这这种种种种方方方方法法法法转转转转换换换换所所所所对对对对应应应应的的的的二二二二叉叉叉叉树树树树是是是是惟惟惟惟一一一一的的的的，且且且且其其其其第第第第一一一一棵棵棵棵树树树树的的的的子子子子树树树树森森森森林林林林转转转转换换换换成成成成二二二二叉叉叉叉树树树树的的的的左左左左子子子子树树树树，剩剩剩剩余余余余树树树树的的的的森林转换成二叉树的右子树。森林转换成二叉树的右子树。森林转换成二叉树的右子树。森林转换成二叉树的右子树。94

160、2. 2. 二叉树还原为森林二叉树还原为森林二叉树还原为森林二叉树还原为森林 二叉树还原为森林可以按照如下步骤进行：二叉树还原为森林可以按照如下步骤进行：二叉树还原为森林可以按照如下步骤进行：二叉树还原为森林可以按照如下步骤进行： 抹抹线线：抹抹掉掉二二叉叉树树根根结结点点右右链链上上所所有有结结点点上上的的连连线，分成若干个以右链上结点为根结点的子二叉树；线，分成若干个以右链上结点为根结点的子二叉树； 转换：转换：将分好的子二叉树转换成树；将分好的子二叉树转换成树； 调整：调整：将转换好的树的根结点排列成一排。将转换好的树的根结点排列成一排。 1. 1. 树的遍历树的遍历树的遍历树的遍历95

161、 先先先先根根根根遍遍遍遍历历历历：若若若若树树树树非非非非空空空空，则则则则先先先先访访访访问问问问树树树树的的的的根根根根结结结结点点点点，然然然然后后后后依次先根遍历根的每棵子树。依次先根遍历根的每棵子树。依次先根遍历根的每棵子树。依次先根遍历根的每棵子树。 后后后后根根根根遍遍遍遍历历历历：若若若若树树树树非非非非空空空空，则则则则先先先先依依依依次次次次后后后后根根根根遍遍遍遍历历历历根根根根的的的的每每每每棵棵棵棵子树，然后访问树的根结点。子树，然后访问树的根结点。子树，然后访问树的根结点。子树，然后访问树的根结点。 层层层层次次次次遍遍遍遍历历历历：若若若若树树树树非非非非空空空

162、空，则则则则从从从从树树树树的的的的根根根根结结结结点点点点起起起起按按按按层层层层从从从从左左左左到右依次访问各结点。到右依次访问各结点。到右依次访问各结点。到右依次访问各结点。 6.5.3 树和森林的遍历树和森林的遍历96 2. 2. 森林的遍历森林的遍历森林的遍历森林的遍历 先先先先序序序序遍遍遍遍历历历历：若若若若森森森森林林林林非非非非空空空空，则则则则：访访访访问问问问森森森森林林林林中中中中第第第第一一一一棵棵棵棵树树树树根根根根结结结结点点点点；先先先先序序序序遍遍遍遍历历历历第第第第一一一一棵棵棵棵树树树树中中中中根根根根结结结结点点点点的的的的子子子子树树树树森森森森林林林

163、林；先先先先序序序序遍历除去第一棵树后剩余的树构成的森林。遍历除去第一棵树后剩余的树构成的森林。遍历除去第一棵树后剩余的树构成的森林。遍历除去第一棵树后剩余的树构成的森林。 中中中中序序序序遍遍遍遍历历历历：若若若若森森森森林林林林非非非非空空空空，则则则则：中中中中序序序序遍遍遍遍历历历历第第第第一一一一棵棵棵棵树树树树中中中中根根根根结结结结点点点点的的的的子子子子树树树树森森森森林林林林；访访访访问问问问森森森森林林林林中中中中第第第第一一一一棵棵棵棵树树树树根根根根结结结结点点点点；中中中中序序序序遍历除去第一棵树后剩余的树构成的森林。遍历除去第一棵树后剩余的树构成的森林。遍历除去第一

164、棵树后剩余的树构成的森林。遍历除去第一棵树后剩余的树构成的森林。 层层层层次次次次遍遍遍遍历历历历：若若若若森森森森林林林林非非非非空空空空，则则则则：对对对对第第第第一一一一棵棵棵棵树树树树从从从从根根根根结结结结点点点点起起起起按按按按层层层层从从从从左左左左到到到到右右右右依依依依次次次次访访访访问问问问结结结结点点点点；按按按按层层层层访访访访问问问问森森森森林林林林中中中中除除除除第第第第一一一一棵树外剩余的树构成的森林。棵树外剩余的树构成的森林。棵树外剩余的树构成的森林。棵树外剩余的树构成的森林。A AB BD DC CE EF FG GHHI IJ JA AB BE EC CD

165、DF FG GHHI IJ J森林森林森林森林先序遍历森林先序遍历森林先序遍历森林先序遍历森林对应的二叉树对应的二叉树对应的二叉树对应的二叉树先序遍历二叉树先序遍历二叉树先序遍历二叉树先序遍历二叉树A B C D E F G H I JA B C D E F G H I J97A A B B C CD D E E F F G G HH I IJ J森林的先序序列对森林的先序序列对应转换之后二叉树应转换之后二叉树的先序序列。的先序序列。 赫赫赫赫夫夫夫夫曼曼曼曼 (Huffman)(Huffman) 树树树树，又又又又称称称称最最最最优优优优二二二二叉叉叉叉树树树树，它它它它是是是是 n n 个

166、个个个带带带带权权权权叶叶叶叶子子子子结结结结点点点点构构构构成成成成的的的的所所所所有有有有二二二二叉叉叉叉树树树树中中中中，带带带带权权权权路路路路径径径径长长长长度度度度最最最最短短短短的的的的二二二二叉叉叉叉树树树树，有有有有着着着着广广广广泛泛泛泛的的的的应应应应用用用用。因因因因为为为为构构构构造造造造这这这这种种种种树树树树的的的的算算算算法法法法最最最最早早早早由由由由赫赫赫赫夫夫夫夫曼曼曼曼 (Huffman) (Huffman) 于于于于 1952 1952 年年年年提提提提出出出出的的的的，所所所所以以以以被称为赫夫曼树。被称为赫夫曼树。被称为赫夫曼树。被称为赫夫曼树。9

167、86.6 赫夫曼树及其应用赫夫曼树及其应用基本概念基本概念99赫夫曼算法赫夫曼算法赫夫曼编码赫夫曼编码赫夫曼树和赫夫曼编码的存储表示赫夫曼树和赫夫曼编码的存储表示赫夫曼编码的算法赫夫曼编码的算法示例示例100 在在在在赫赫赫赫夫夫夫夫曼曼曼曼树树树树及及及及其其其其应应应应用用用用中中中中经经经经常常常常会会会会用用用用到到到到一一一一些些些些基基基基本本本本术术术术语语语语。例如：例如：例如：例如：路径路径路径路径路径长度路径长度路径长度路径长度树的路径长度树的路径长度树的路径长度树的路径长度结点的带权路径长度结点的带权路径长度结点的带权路径长度结点的带权路径长度树的带权路径长度树的带权路径

168、长度树的带权路径长度树的带权路径长度赫夫曼赫夫曼赫夫曼赫夫曼树树树树6.6.1 基本概念基本概念101c cd da ab b7 75 54 42 2 路路路路径径径径：从从从从树树树树中中中中一一一一个个个个结结结结点点点点到到到到另另另另一一一一个个个个结结结结点点点点之之之之间间间间的分支构成两个结点之间的路径。的分支构成两个结点之间的路径。的分支构成两个结点之间的路径。的分支构成两个结点之间的路径。路径长度：路径上的分支数目称为路径长度路径长度：路径上的分支数目称为路径长度路径长度：路径上的分支数目称为路径长度路径长度：路径上的分支数目称为路径长度 树树树树的的的的路路路路径径径径长长

169、长长度度度度：从从从从树树树树根根根根到到到到每每每每一一一一个个个个结结结结点点点点的的的的路路路路径径径径长长长长度度度度之之之之和和和和称称称称为为为为树的路径长度。完全二叉树就是这种路径长度最短的二叉树。树的路径长度。完全二叉树就是这种路径长度最短的二叉树。树的路径长度。完全二叉树就是这种路径长度最短的二叉树。树的路径长度。完全二叉树就是这种路径长度最短的二叉树。 结结结结点点点点的的的的带带带带权权权权路路路路径径径径长长长长度度度度：从从从从该该该该结结结结点点点点到到到到树树树树根根根根之之之之间间间间的的的的路路路路径径径径长长长长度度度度与与与与结点上权的乘积称为结点的带权路

170、径长度。结点上权的乘积称为结点的带权路径长度。结点上权的乘积称为结点的带权路径长度。结点上权的乘积称为结点的带权路径长度。a a7 7例如：结点例如：结点例如：结点例如：结点 a a 的带权路径长度为路径长度的带权路径长度为路径长度的带权路径长度为路径长度的带权路径长度为路径长度 3 3结点权值结点权值结点权值结点权值 7 = 21 7 = 21 树树树树的的的的带带带带权权权权路路路路径径径径长长长长度度度度：树树树树中中中中所所所所有有有有叶叶叶叶子子子子结结结结点点点点的的的的带带带带权权权权路路路路径径径径长长长长度度度度之之之之和称为树的带权路径长度。通常记作和称为树的带权路径长度。

171、通常记作和称为树的带权路径长度。通常记作和称为树的带权路径长度。通常记作 例如：此树的带权路径长度为例如：此树的带权路径长度为例如：此树的带权路径长度为例如：此树的带权路径长度为24243737353512 = 4612 = 46 赫夫曼树的定义：赫夫曼树的定义： 假假设设有有 n 个个权权值值 w1, w2, , wn ，构构造造一一棵棵有有 n 个个叶叶子子结结点点的的二二叉叉树树，每每个个叶叶子子结结点点带带权权为为 wi ，则则其其中中带带权权路路径径长长度度 WPL 最最小小的的二二叉叉树树称称为为最最优优二二叉叉树树或赫夫曼树。或赫夫曼树。102a ab bc cd d7 75 5

172、2 24 4c cd da ab b7 75 54 42 2a ab bc cd d7 75 52 24 4 图图图图 (a) (a) 的带权路径长度为的带权路径长度为的带权路径长度为的带权路径长度为 WPLWPL = 72 = 725252222242 = 3642 = 36(a(a) )(b(b) )(c(c) ) 图图图图 (b) (b) 的带权路径长度为的带权路径长度为的带权路径长度为的带权路径长度为 WPLWPL = 73 = 735353212142 = 4642 = 46 图图图图 (c) (c) 的带权路径长度为的带权路径长度为的带权路径长度为的带权路径长度为 WPLWPL =

173、 71 = 715252232343 = 3543 = 35103 在在在在 3 3 棵棵棵棵二二二二叉叉叉叉树树树树中中中中，以以以以图图图图(c) (c) 所所所所示示示示的的的的二二二二叉叉叉叉树树树树带带带带权权权权路路路路径径径径长长长长度度度度最最最最小小小小。可可可可以以以以验验验验证证证证，它它它它恰恰恰恰为为为为赫赫赫赫夫夫夫夫曼曼曼曼树树树树，即即即即其其其其带带带带权权权权路路路路径径径径长长长长度度度度在在在在所所所所有有有有带带带带权权权权为为为为 7 7、5 5、2 2、4 4 的的的的 4 4 个个个个叶叶叶叶子子子子结结结结点点点点的二叉树中居最小。的二叉树中居

174、最小。的二叉树中居最小。的二叉树中居最小。 下下下下面面面面所所所所示示示示的的的的 3 3 棵棵棵棵二二二二叉叉叉叉树树树树都都都都含含含含有有有有 4 4 个个个个叶叶叶叶子子子子结结结结点点点点 A A、B B、C C、D D，分别带权，分别带权，分别带权，分别带权 7 7、5 5、2 2、4 4。 1. 1. 赫夫曼算法思想赫夫曼算法思想赫夫曼算法思想赫夫曼算法思想 构构构构造造造造赫赫赫赫夫夫夫夫曼曼曼曼树树树树的的的的算算算算法法法法称称称称之之之之为为为为赫赫赫赫夫夫夫夫曼曼曼曼算算算算法法法法，其其其其具具具具体体体体步骤如下：步骤如下：步骤如下：步骤如下：104 根根根根据据

175、据据给给给给定定定定的的的的 n n 个个个个权权权权值值值值 w w1 1, , w w2 2, , , , w wn n ，构构构构成成成成 n n 棵棵棵棵二二二二叉叉叉叉树树树树的的的的集集集集合合合合 F F = = T T1 1, , T T2 2, , , , T Tn n ，其其其其中中中中每每每每棵棵棵棵二二二二叉叉叉叉树树树树 T Ti i 中中中中只只只只有有有有一一一一个个个个带带带带权权权权 w wi i 的的的的根根根根结结结结点点点点，其其其其左左左左子子子子树树树树和和和和右右右右子树均为空。子树均为空。子树均为空。子树均为空。6.6.2 赫夫曼算法赫夫曼算法

176、在在在在 F F 中中中中选选选选取取取取两两两两棵棵棵棵根根根根结结结结点点点点的的的的权权权权值值值值最最最最小小小小的的的的树树树树作作作作为为为为左左左左子子子子树树树树和和和和右右右右子子子子树树树树，构构构构造造造造一一一一棵棵棵棵新新新新的的的的二二二二叉叉叉叉树树树树，并并并并且且且且置置置置新新新新的的的的二二二二叉叉叉叉树树树树的的的的根根根根结结结结点点点点的的的的权权权权值值值值为为为为其其其其左左左左子子子子树树树树和和和和右右右右子子子子树树树树上上上上根根根根结结结结点点点点的权值之和。的权值之和。的权值之和。的权值之和。105 在在在在 F F 中中中中删删删删

177、除除除除在在在在中中中中选选选选中中中中的的的的那那那那两两两两棵棵棵棵根根根根结结结结点点点点权权权权值值值值最小的二叉树，同时将新得到的二叉树加入最小的二叉树，同时将新得到的二叉树加入最小的二叉树，同时将新得到的二叉树加入最小的二叉树，同时将新得到的二叉树加入 F F 中。中。中。中。 重重重重复复复复和和和和 ，直直直直到到到到 F F 中中中中只只只只含含含含一一一一棵棵棵棵树树树树为为为为止止止止。这这这这棵树便是赫夫曼树。棵树便是赫夫曼树。棵树便是赫夫曼树。棵树便是赫夫曼树。6.5.2 哈夫曼树的构造哈夫曼树的构造举例：5，11，26，18，34，15，6构成一棵哈夫曼树6 511

178、1518263411223348771256.5.2 哈夫曼树的构造哈夫曼树的构造整理上面的哈夫曼树如图：6 511151826341122334877125哈夫曼树的构造算法哈夫曼树的构造算法哈夫曼树的类型定义：用静态三叉链表实现哈夫曼哈夫曼树的类型定义：用静态三叉链表实现哈夫曼树类型定义如下：树类型定义如下：#define N 20 /*叶子结点最大值叶子结点最大值*/#define M 2*N-1 /*所有结点的最大值所有结点的最大值*/typedef struct int weight; /*结点的权值结点的权值*/ int parent; /*双亲的下标双亲的下标*/ int Lch

179、ild; /*左孩子结点的下标左孩子结点的下标*/ int Rchild; /*右孩子结点的下标右孩子结点的下标*/HTNode,HuffmanTreeM+1; 哈夫曼树的构造哈夫曼树的构造哈夫曼树构造算法分为两步：哈夫曼树构造算法分为两步：第一步对初始状态的设置。在该步骤中，让第第一步对初始状态的设置。在该步骤中，让第1到到n的单位的权值为所給权值，从第的单位的权值为所給权值，从第n+1到第到第m=2n-1的单的单元的权值都为元的权值都为0.让所有结点的双亲和孩子值都为让所有结点的双亲和孩子值都为0.即即创建创建n个子树，每棵树只有根结点。个子树，每棵树只有根结点。第二步开始实现构造过程，即

180、选取权值最小的两棵第二步开始实现构造过程，即选取权值最小的两棵树根（双亲为树根（双亲为0）进行合并，构造一棵新的树（产生）进行合并，构造一棵新的树（产生新的结点），该树的根结点权值为所选的两棵树的新的结点），该树的根结点权值为所选的两棵树的权值之和，且左右孩子分别为上述所选的两棵树，权值之和，且左右孩子分别为上述所选的两棵树，即所选出的两棵树的双亲为新构造的结点。构造出即所选出的两棵树的双亲为新构造的结点。构造出来的新结点依次存放在第来的新结点依次存放在第n+1到第到第m的单元上。的单元上。 哈夫曼树的构造哈夫曼树的构造void CrtHuffmanTree(HuffmanTree ht, i

181、nt w , int n) / 第一步：对初始状态的设置。第一步：对初始状态的设置。 for(i=1;i=n;i+) hti=wi,0,0,0 ; m=2*n-1; for(i=n+1;i=m;i+) hti=0,0,0,0; /第二步第二步:创建非叶子结点，开始实现构造过程创建非叶子结点，开始实现构造过程. for(i=n+1;ikey=key; s-Lchild=NULL; s-Rchild=NULL; *bst=s; void InsertBST（BSTree *bst , DataType e)/*若在二叉排序树若在二叉排序树bst中不存在关键字等于中不存在关键字等于key的元素，插入

182、该元素的元素，插入该元素*/else if(keykey) InsertBST(&(*(bst)-Lchild),key); void InsertBST（BSTree *bst , DataType e)/*若在二叉排序树若在二叉排序树bst中不存在关键字等于中不存在关键字等于key的元素，插入该元素的元素，插入该元素*/else if(keykey) InsertBST(&(*(bst)-Lchild),key); else if(key(*bst)-key) InsertBST(&(*(bst)-Rchild),key); 二叉排序树创建算法描述：二叉排序树创建算法描述：void Cre

183、ateBST（BSTree *bst)/*从键盘输入元素的值，创建相应的二叉排序树从键盘输入元素的值，创建相应的二叉排序树*/ KeyType key; *bst=NULL; 键盘输入元素值键盘输入元素值key； while（当当key值满足条件值满足条件） InsertBST(bst , key); /插入插入 键盘输入元素值键盘输入元素值key; void CreateBST（BSTree *bst)/*从键盘输入元素的值，创建相应的二叉排序树从键盘输入元素的值，创建相应的二叉排序树*/ KeyType key; *bst=NULL; 键盘输入元素值键盘输入元素值key； while（当当

184、key值满足条件值满足条件） InsertBST(bst , key); /插入插入 键盘输入元素值键盘输入元素值key; 练习：练习： 设关键字的输入顺序为：设关键字的输入顺序为：12，24，28，53，90，45，画出所生成的二叉排序树。，画出所生成的二叉排序树。 二叉排序树查找二叉排序树查找算法思想：算法思想：首先将待查关键字与根结点关键字首先将待查关键字与根结点关键字t进行比较，进行比较，如果：如果： 1）key=t: 则返回根结点地址；则返回根结点地址； 2）keyt: 则进一步查找右子树；则进一步查找右子树； 算法实现（递归）算法实现（递归）BSTree SearchBST(BST

185、ree bst , KeyType key) if(!bst) return NULL; else if(bst-key=t)return bst; /如果查找成功，则返回如果查找成功，则返回 else if(bst-keykey ) return SearchBST(bst-Lchild , key); else return SearchBST(bst-Rchild , key);二叉排序树的删除二叉排序树的删除从二叉排序树中删除一个结点，要保证删除后的二叉树还是一棵二从二叉排序树中删除一个结点，要保证删除后的二叉树还是一棵二叉排序树。叉排序树。算法思想：首先查找要删除结点，如果查找失败，

186、则不作任何删除算法思想：首先查找要删除结点，如果查找失败，则不作任何删除操作，否则，假设要删除的结点为操作，否则，假设要删除的结点为p，其双亲结点为，其双亲结点为f，并假设，并假设p是是f的左孩子（右孩子情况类似），则删除过程分为三种情况讨论：的左孩子（右孩子情况类似），则删除过程分为三种情况讨论：（1）若）若p为叶子结点，则直接删除该结点，其双亲的左孩子为空：为叶子结点，则直接删除该结点，其双亲的左孩子为空： f-Lchild=NULL;free(p);（2）若）若p为单分支结点，即为单分支结点，即p只有左子树，或者只有右子树，则可只有左子树，或者只有右子树，则可将将p的左子树或者右子树直接

187、改为其双亲结点的左子树或者右子树直接改为其双亲结点f的左子树：的左子树： f-Lchild=p-Lchild;(或者或者 f-Lchild=p-Rchild;) free(p); 二叉排序树的删除二叉排序树的删除（3）若）若p为双分支结点，则有两种处理方法：为双分支结点，则有两种处理方法：方法方法1：找到：找到p结点在中序遍历序列中的直接前驱结点在中序遍历序列中的直接前驱s，将，将p的左子树的左子树改为改为f的左子树，将的左子树，将p的右子树改为的右子树改为s的右子树：的右子树：f-Lchild=p-Lchild; s-Rchild=p-Rchild;free(p);方法方法2：找到：找到p结

188、点在中序遍历序列中的直接前驱结点在中序遍历序列中的直接前驱s，然后用，然后用s结点代结点代替替p结点的值，再将结点的值，再将s结点删除，原结点删除，原s结点的左子树改为其双亲结点结点的左子树改为其双亲结点（假设为（假设为q）的右子树：）的右子树：p-key=s-key ; q-Rchild=s-Lchild; free(s);上述的两种方法中还可以将寻找上述的两种方法中还可以将寻找p结点的中序遍历前驱改成寻找中结点的中序遍历前驱改成寻找中序遍历后继，请同学们考虑一下。序遍历后继，请同学们考虑一下。二叉排序树的删除算法描述二叉排序树的删除算法描述BSTNode * DelBST(BSTree t

189、 , KeyType k)BSTNode *p , *q , *f , *s ; /*查找关键字为查找关键字为k的待删除结点位置的待删除结点位置*/ p=t; f=NULL ; /从根结点开始查找从根结点开始查找 while(p) if(p-key=k)break ; f=p; /记录双亲结点位置记录双亲结点位置 if(p-keyk)p=p-Lchild; else p=p-Rchild ; if(p=NULL)return t ; /查找不成功，不作任何操作，直接返回查找不成功，不作任何操作，直接返回 /如果查找成功，则查看如果查找成功，则查看p的情况的情况 if(p-Lchild=p-Rc

190、hild=NULL) /p是叶子结点是叶子结点 if(f=NULL)t=f ; return t; else if(p=f-Lchild)f-Lchild=NULL; free(p); else if(p=f-Rchild)f-Rchild=NULL;free(p); 二叉排序树的删除算法描述二叉排序树的删除算法描述else /如果如果p是单分支结点是单分支结点 if(p-Lchild=NULL) /p无左子树无左子树 if(f=NULL)t=p-Rchild; else if (f-Lchild=p) /若若p是是f的左孩子的左孩子 f-Lchild=p-Rchild; /p的右子树作为的右

191、子树作为f的左子树的左子树 else f-Rchild=p-Rchild ; /p的右子树作为的右子树作为f的右子树的右子树 free(p); if(p-Rchild=NULL) /p无右子树无右子树 if(f=NULL)t=p-Lchild; else if(f-Lchild=p) f-Lchild=p-Lchild; else f-Rchild=p-Lchild; 二叉排序树的删除算法描述二叉排序树的删除算法描述 /如果如果p是双分支结点是双分支结点 if(p-Lchild!=NULL & p-Rchild!=NULL) /寻找寻找p的左子树的最右端结点的左子树的最右端结点 q=p; s=

192、p-Lchild; while(s-Rchild) q=s ; s=s-Rchild; if(q=p)q-Lchild=s-Lchild; else q-Rchild=s-Lchild; p-key=s-key; free(s); /if /else return t; /DelBST 举例：如图是一棵二叉排序树，分别删除举例：如图是一棵二叉排序树，分别删除20和和90的状态为的状态为452453122848908207280604043举例：删除举例：删除45的状态为的状态为452453124890872806044404345245312444890872806040434844平衡二叉排

193、序树平衡二叉排序树平衡二叉排序树又称为平衡二叉排序树又称为AV树。其定义如下：树。其定义如下：一棵平衡二叉排序树一棵平衡二叉排序树 或者是空树，或者是具有如下性质的二叉排序或者是空树，或者是具有如下性质的二叉排序树：树：(1)左子树与右子树的深度之差（左子树与右子树的深度之差（平衡因子平衡因子Balance Factor）的绝）的绝对值小于等于对值小于等于1；(2) 左右子树都是平衡二叉树。左右子树都是平衡二叉树。45245312289000000-1452453122890720000-1-2-1综合设计：综合设计：二叉排序树的综合运用二叉排序树的综合运用实验描述：随机产生100个数，用二叉

194、排序树和任选一种内排序方法进行排序，并对二种算法进行比较。实验要求：输入：要求产生的随机数先写入文本数据文件input.txt中，如没有数据文件input.txt,则先创建数据文件input.txt，之后每次产生的100个随机数均追加到文件input.txt中。输出：（1）从文件input中顺序读出100个数，生成二叉排序树，并对二叉排序树进行中序遍历输出到文件output1.txt中，并从屏幕输出；（2）从文件input中读出相同的数据到数组中，用采用一种内部排序进行排序，输出到文件output2.txt中，并从屏幕输出。对上述算法进行分析，给出和两种算法的优劣比较。所涉及的数据结构：顺序表、二叉链表、文件等。所涉及的算法：二叉排序树生成和遍历，排序算法等。