第6章树与二叉树ppt课件

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

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

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

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

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

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 Da

8、taTypedata;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) 操操操操作作作作也也也也很很很很简简简简单单单单：反反反反复复复复调调调调用用用用 P

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

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

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

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

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

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

16、点点是是是是不不不不同同同同构的。构的。构的。构的。degreedegree child1child1 child2child2childdchildddatadata 其中种种种种存存存存储储储储构构构构造造造造防防防防止止止止了了了了孩孩孩孩子子子子表表表表示示示示法法法法存存存存储储储储构构构构造造造造中中中中出出出出现现现现的的的的空空空空链链链链域域域域，节节节节约约约约存存存存储储储储空空空空间间间间。但但但但是是是是由由由由于于于于每每每每个个个个结结结结点点点点的的的的孩孩孩孩子子子子链链链链域域域域数数数数不同，所以在这种构造上进展的各种操作不易实现。不同，所以在这种构造上进

17、展的各种操作不易实现。不同，所以在这种构造上进展的各种操作不易实现。不同，所以在这种构造上进展的各种操作不易实现。 为结点的度，为结点的度，为结点的度，为结点的度，degree degree 域的值和域的值和域的值和域的值和 d d一样。这一样。这一样。这一样。这10d d (3) (3) 单单单单链链链链表表表表存存存存储储储储构构构构造造造造。即即即即把把把把每每每每个个个个结结结结点点点点的的的的孩孩孩孩子子子子结结结结点点点点陈陈陈陈列列列列起起起起来来来来，看看看看成成成成是是是是一一一一个个个个线线线线性性性性表表表表，且且且且以以以以单单单单链链链链表表表表作作作作为为为为存存存

18、存储储储储构构构构造造造造，那那那那么么么么 n n 个个个个结结结结点点点点有有有有 n n 个个个个孩孩孩孩子子子子链链链链表表表表叶叶叶叶子子子子结结结结点点点点的的的的孩孩孩孩子子子子链链链链表表表表为为为为空空空空表表表表。而而而而 n n 个个个个头头头头指指指指针针针针又又又又组组组组成成成成一一一一个个个个线线线线性性性性表表表表，为为为为了便于查找，可以采用顺序存储构造。了便于查找，可以采用顺序存储构造。了便于查找，可以采用顺序存储构造。了便于查找，可以采用顺序存储构造。11R RA AB BC CD DE EF FG GHHk k树树树树A AB BC CD DR RE E

19、F 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 即即即即可可可可以以以以得得得得到到到到该结点的

20、孩子结点。该结点的孩子结点。该结点的孩子结点。该结点的孩子结点。 在在在在树树树树的的的的孩孩孩孩子子子子单单单单链链链链表表表表构构构构造造造造中中中中，查查查查找找找找某某某某结结结结点点点点的的的的双双双双亲亲亲亲需需需需求求求求按按按按照照照照该该该该结结结结点点点点在在在在头头头头结结结结点点点点顺顺顺顺序序序序表表表表中中中中的的的的位位位位置置置置序序序序号号号号在在在在每每每每个个个个孩孩孩孩子子子子链链链链表表表表中中中中扫扫扫扫描描描描，当当当当在在在在孩孩孩孩子子子子域域域域 child child 中中中中找找找找到到到到一一一一样样样样的的的的序序序序号号号号时时时时

21、，那那那那么么么么单单单单链链链链表表表表表表表表头头头头的的的的结结结结点点点点就就就就是要找的双亲。是要找的双亲。是要找的双亲。是要找的双亲。 例例例例如如如如，要要要要寻寻寻寻觅觅觅觅树树树树中中中中 G G 结结结结点点点点的的的的双双双双亲亲亲亲结结结结点点点点。G G 结结结结点点点点在在在在头头头头结结结结点点点点顺顺顺顺序序序序表表表表中中中中的的的的位位位位置置置置序序序序号号号号为为为为 7 7，那那那那么么么么在在在在孩孩孩孩子子子子链链链链表表表表中中中中查查查查询询询询 child child = = 7 7 的的的的孩孩孩孩子子子子结结结结点点点点，当当当当找找找找

22、到到到到的的的的时时时时候候候候，该该该该单单单单链链链链表表表表的的的的表表表表头头头头结结结结点点点点 F F 就是就是就是就是 G G 的双亲结点。的双亲结点。的双亲结点。的双亲结点。 树树树树的的的的孩孩孩孩子子子子兄兄兄兄弟弟弟弟表表表表示示示示法法法法又又又又称称称称二二二二叉叉叉叉树树树树表表表表示示示示法法法法，或或或或二二二二叉叉叉叉链链链链表表表表表表表表示示示示法法法法，即即即即以以以以二二二二叉叉叉叉链链链链表表表表作作作作为为为为树树树树的的的的存存存存储储储储构构构构造造造造。链链链链表表表表中中中中每每每每个个个个结结结结点点点点的的的的构构构构造造造造一一一一样

23、样样样，都都都都有有有有 3 3 个个个个域域域域：数数数数据据据据域域域域 data data 存存存存放放放放树树树树中中中中结结结结点点点点的的的的信信信信息息息息；孩孩孩孩子子子子域域域域 firstchild firstchild 存存存存放放放放该该该该结结结结点点点点的的的的第第第第一一一一个个个个孩孩孩孩子子子子结结结结点点点点从从从从左左左左算算算算起起起起的的的的地地地地址址址址；兄兄兄兄弟弟弟弟域域域域 nextsibling nextsibling 存存存存放放放放该该该该结结结结点的下一个兄弟结点从左向右的地址。点的下一个兄弟结点从左向右的地址。点的下一个兄弟结点从左

24、向右的地址。点的下一个兄弟结点从左向右的地址。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 树树树树的的的的二二二二叉叉叉叉链链链链表表表表存存存存储储储储构构构构造造造造的的的的最最最最大大大大优优优优点点点点就就就就是是是是结结结结点点点点的的的的构构构构造造造造一一一一致致致致，和和和和前前前前面面面面讲讲讲讲的的的的二二二二叉叉叉叉树树树树表表表表示示示示法法法法完完完完全全全全一一一一样样样样，因因因因此此此此可可可可以

25、以以以利利利利用用用用二二二二叉叉叉叉树树树树的的的的算算算算法法法法来来来来实实实实现现现现对对对对树树树树的操作。的操作。的操作。的操作。 在在在在树树树树的的的的二二二二叉叉叉叉链链链链表表表表存存存存储储储储构构构构造造造造中中中中，易易易易于于于于实实实实现现现现找找找找结结结结点点点点等等等等的的的的操操操操作作作作。假假假假设设设设要要要要访访访访问问问问树树树树中中中中结结结结点点点点 x x 的的的的第第第第 i i 个个个个孩孩孩孩子子子子，那那那那么么么么 只只只只 需需需需 求求求求 先先先先 从从从从 该该该该 结结结结 点点点点 的的的的 firstchild fi

26、rstchild 域域域域找找找找到到到到第第第第 1 1 个个个个孩孩孩孩子子子子结结结结点点点点，然然然然后后后后再再再再沿沿沿沿孩孩孩孩子子子子结结结结点点点点的的的的 nextsibling nextsibling 域域域域延延延延续续续续走走走走 i-1 i-1 步步步步，便便便便可可可可以以以以找找找找到到到到结结结结点点点点 x x 的第的第的第的第 i i 个孩子。个孩子。个孩子。个孩子。 例例例例如如如如，要要要要访访访访问问问问 F F 结结结结点点点点的的的的第第第第 3 3 个个个个孩孩孩孩子子子子，只只只只需需需需先先先先从从从从 F F 结结结结点点点点的的的的 F

27、irstchild Firstchild 域域域域找找找找到到到到第第第第一一一一个个个个孩孩孩孩子子子子 G G 结结结结点点点点后后后后，再再再再沿沿沿沿着着着着 G G 结结结结点点点点的的的的 Nextsibling Nextsibling 域域域域延延延延续续续续走走走走 2 2 步步步步，找找找找到到到到 K K 结结结结点点点点，这这这这就就就就是是是是 F F 结结结结点点点点的的的的第第第第 3 3 个个个个孩孩孩孩子子子子结结结结点点点点。但但但但是是是是，在在在在这这这这个个个个构构构构造造造造上上上上查查查查找找找找某某某某结结结结点点点点的的的的双双双双亲亲亲亲结结结

28、结点点点点不不不不是是是是很很很很方方方方便便便便，假假假假设设设设为为为为每每每每个个个个结结结结点点点点再再再再增增增增设设设设一一一一个个个个双双双双亲亲亲亲 parent parent 域域域域，那那那那么么么么查查查查找找找找某某某某结结结结点点点点的的的的双双双双亲亲亲亲的的的的操操操操作也很方便。作也很方便。作也很方便。作也很方便。 二二二二叉叉叉叉树树树树 (binary (binary tree) tree) 是是是是另另另另一一一一种种种种树树树树型型型型构构构构造造造造，它它它它的的的的特特特特点点点点是是是是每每每每个个个个结结结结点点点点至至至至多多多多只只只只需需需

29、需两两两两棵棵棵棵子子子子树树树树即即即即二二二二叉叉叉叉树树树树中中中中不不不不存存存存在在在在度度度度大大大大于于于于 2 2 的的的的结结结结点点点点，并并并并且且且且，二二二二叉叉叉叉树树树树的的的的子子子子树树树树有有有有左左左左右右右右之之之之分分分分，其其其其次次次次序不能恣意颠倒。序不能恣意颠倒。序不能恣意颠倒。序不能恣意颠倒。二叉树的逻辑构造二叉树的逻辑构造6.2 二叉树二叉树15二叉树的根本性质二叉树的根本性质二叉树的存储构造二叉树的存储构造 二二二二叉叉叉叉树树树树是是是是一一一一个个个个有有有有限限限限的的的的结结结结点点点点的的的的集集集集合合合合，该该该该集集集集合

30、合合合或或或或者者者者为为为为空空空空，或或或或者者者者由由由由一一一一个个个个根根根根结结结结点点点点加加加加上上上上两两两两棵棵棵棵分分分分别别别别称称称称为为为为左左左左子子子子树树树树和和和和右右右右子子子子树树树树的的的的、互不相交的二叉树组成。互不相交的二叉树组成。互不相交的二叉树组成。互不相交的二叉树组成。16 二二二二叉叉叉叉树树树树定定定定义义义义是是是是一一一一个个个个递递递递归归归归定定定定义义义义，即即即即在在在在二二二二叉叉叉叉树树树树的的的的定定定定义义义义中中中中又用到二叉树的概念。又用到二叉树的概念。又用到二叉树的概念。又用到二叉树的概念。6.2.1 二叉树的逻

31、辑构造二叉树的逻辑构造 1. 1. 二叉树的定义二叉树的定义二叉树的定义二叉树的定义 性性性性质质质质1 1：在在在在二二二二叉叉叉叉树树树树的的的的第第第第 i i 层层层层上上上上至至至至多多多多有有有有 2i-1 2i-1 个个个个结结结结点点点点i1i1。 证明：利用归纳法容易证得此性质。证明：利用归纳法容易证得此性质。证明：利用归纳法容易证得此性质。证明：利用归纳法容易证得此性质。 i = 1 i = 1 时，只需一个根结点。时，只需一个根结点。时，只需一个根结点。时，只需一个根结点。2i-1 = 20 = 12i-1 = 20 = 1，命题成立。，命题成立。，命题成立。，命题成立。

32、 假假假假定定定定对对对对一一一一切切切切的的的的 j j (1j(1ji) i)，命命命命题题题题成成成成立立立立，即即即即第第第第 j j 层层层层上上上上至至至至多有多有多有多有 2 j-1 2 j-1 个结点。那么，可以证明个结点。那么，可以证明个结点。那么，可以证明个结点。那么，可以证明 j = i j = i 时命题也成立。时命题也成立。时命题也成立。时命题也成立。 根根根根据据据据归归归归纳纳纳纳假假假假设设设设，第第第第 i-1 i-1 层层层层上上上上至至至至多多多多有有有有 2i-2 2i-2 个个个个结结结结点点点点。由由由由于于于于二二二二叉叉叉叉树树树树的的的的每每每

33、每个个个个结结结结点点点点的的的的度度度度最最最最多多多多为为为为 2 2，所所所所以以以以在在在在第第第第 i i 层层层层上上上上最最最最多多多多的的的的结点数为第结点数为第结点数为第结点数为第 i-1 i-1 层上的层上的层上的层上的 2 2 倍，即倍，即倍，即倍，即 22i-2 = 2i-1 22i-2 = 2i-1。176.2.2 二叉树的根本性质二叉树的根本性质 性性性性质质质质2 2：深深深深度度度度为为为为 k k 的的的的二二二二叉叉叉叉树树树树至至至至多多多多有有有有 2k2k1 1 个个个个结结结结点点点点k1k1。= 2k= 2k1 118 证明：证明：证明：证明： 由

34、性质由性质由性质由性质1 1 可见，深度为可见，深度为可见，深度为可见，深度为 k k 的二叉树的最大结点数为的二叉树的最大结点数为的二叉树的最大结点数为的二叉树的最大结点数为 性性性性质质质质3 3：对对对对任任任任何何何何一一一一棵棵棵棵二二二二叉叉叉叉树树树树 T T，假假假假设设设设其其其其终终终终端端端端结结结结点点点点数数数数为为为为 n0n0，度为，度为，度为，度为 2 2 的结点数为的结点数为的结点数为的结点数为 n2 n2，那么，那么，那么，那么 n0 n0 n2 + 1 n2 + 1。19 证明：证明：证明：证明： (1) (1) 设设设设 n1 n1 为为为为二二二二叉叉

35、叉叉树树树树 T T 中中中中度度度度为为为为 1 1 的的的的结结结结点点点点数数数数。n n 为为为为二二二二叉叉叉叉树树树树中中中中总总总总结结结结点点点点数数数数。由由由由于于于于二二二二叉叉叉叉树树树树中中中中一一一一切切切切结结结结点点点点的的的的度度度度均均均均小小小小于于于于或或或或等等等等于于于于 2 2，那么：，那么：，那么：，那么：n = n0 + n1 + n2 n = n0 + n1 + n2 。 (2) (2) 设设设设 B B 为二叉树为二叉树为二叉树为二叉树 T T 中的分支总数。中的分支总数。中的分支总数。中的分支总数。 从从从从入入入入支支支支的的的的角角角

36、角度度度度看看看看，二二二二叉叉叉叉树树树树中中中中除除除除了了了了根根根根结结结结点点点点外外外外，其其其其他他他他结结结结点都有一个且仅有一个入支，那么：点都有一个且仅有一个入支，那么：点都有一个且仅有一个入支，那么：点都有一个且仅有一个入支，那么：n = B + 1n = B + 1。 从从从从出出出出支支支支的的的的角角角角度度度度看看看看，度度度度为为为为 1 1 的的的的结结结结点点点点只只只只需需需需一一一一个个个个出出出出支支支支，度度度度为为为为 2 2 的结点有两个出支，那么：的结点有两个出支，那么：的结点有两个出支，那么：的结点有两个出支，那么：B = n1 + 2n2B

37、 = n1 + 2n2 故：故：故：故：n = n1 + 2n2 + 1n = n1 + 2n2 + 1；最后得到：；最后得到：；最后得到：；最后得到： n0 = n2 + 1 n0 = n2 + 1。 为为为为便便便便于于于于引引引引见见见见下下下下面面面面两两两两个个个个二二二二叉叉叉叉树树树树性性性性质质质质，先先先先了了了了解解解解满满满满二二二二叉叉叉叉树树树树 (full (full binary binary tree) tree) 和和和和完完完完全全全全二二二二叉叉叉叉树树树树 (complete (complete binary binary tree) tree) 的概念

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

39、子结点都在树的最下面的同一层上。子结点都在树的最下面的同一层上。子结点都在树的最下面的同一层上。 满满满满二二二二叉叉叉叉树树树树：一一一一棵棵棵棵深深深深度度度度为为为为 k k 并并并并且且且且有有有有 2k-1 2k-1 个个个个结结结结点点点点的的的的二二二二叉叉叉叉树，称之为满二叉树。树，称之为满二叉树。树，称之为满二叉树。树，称之为满二叉树。 假假假假设设设设对对对对满满满满二二二二叉叉叉叉树树树树的的的的结结结结点点点点进进进进展展展展编编编编号号号号，商商商商定定定定编编编编号号号号从从从从根根根根结结结结点点点点起起起起，自自自自上上上上而而而而下下下下，自自自自左左左左至至

40、至至右右右右。由由由由此此此此可可可可以以以以引引引引出出出出完完完完全全全全二二二二叉叉叉叉树树树树的定义。的定义。的定义。的定义。 完完完完全全全全二二二二叉叉叉叉树树树树的的的的特特特特点点点点是是是是：二二二二叉叉叉叉树树树树中中中中的的的的叶叶叶叶子子子子结结结结点点点点只只只只能能能能够够够够出出出出如如如如今今今今二二二二叉叉叉叉树树树树中中中中层层层层次次次次最最最最大大大大的的的的两两两两层层层层上上上上；最最最最下下下下一一一一层层层层的的的的结结结结点点点点一一一一定定定定是是是是从从从从最最最最左左左左边边边边开开开开场场场场向向向向右右右右放放放放的的的的；并并并并且

41、且且且假假假假设设设设某某某某个个个个结结结结点点点点没没没没有有有有左左左左孩子，那么它一定没有右孩子。孩子，那么它一定没有右孩子。孩子，那么它一定没有右孩子。孩子，那么它一定没有右孩子。21 完完完完全全全全二二二二叉叉叉叉树树树树：一一一一棵棵棵棵深深深深度度度度为为为为 k k 并并并并且且且且有有有有 n n 个个个个结结结结点点点点的的的的二二二二叉叉叉叉树树树树，当当当当且且且且仅仅仅仅当当当当其其其其每每每每一一一一个个个个结结结结点点点点都都都都与与与与深深深深度度度度为为为为 k k 的的的的满满满满二二二二叉叉叉叉树树树树中中中中编号从编号从编号从编号从 1 1 至至至至

42、 n n 的结点一一对应时，称之为完全二叉树。的结点一一对应时，称之为完全二叉树。的结点一一对应时，称之为完全二叉树。的结点一一对应时，称之为完全二叉树。 性质性质性质性质4 4：具有：具有：具有：具有 n n 个结点的完全二叉树的深度为个结点的完全二叉树的深度为个结点的完全二叉树的深度为个结点的完全二叉树的深度为 log2n log2n + 1 + 1 x x 表示不大于表示不大于表示不大于表示不大于 x x 的最大整数的最大整数的最大整数的最大整数22 证明：证明：证明：证明： 设设设设所所所所求求求求完完完完全全全全二二二二叉叉叉叉树树树树深深深深度度度度为为为为 k k，那那那那么么么

43、么它它它它的的的的前前前前 k-1 k-1 层层层层可可可可视视视视为为为为深深深深度度度度为为为为 k-1 k-1 的的的的满满满满二二二二叉叉叉叉树树树树，共共共共有有有有 2k-1-1 2k-1-1 个个个个结结结结点点点点，故故故故该该该该完全二叉树的总结点数完全二叉树的总结点数完全二叉树的总结点数完全二叉树的总结点数 n n 一定满足式子：一定满足式子：一定满足式子：一定满足式子：n n2k-1-12k-1-1。 根据性质根据性质根据性质根据性质 2 2，可以确定：，可以确定：，可以确定：，可以确定：n 2k-1n 2k-1 由此得到：由此得到：由此得到：由此得到：2k-1-12k-

44、1-1n2k-1 n2k-1 或或或或 2k-1 n 2k-1 n2k2k 等价关系：等价关系：等价关系：等价关系：k-1log2nk-1log2nk k由于由于由于由于 k k 是整数，所以是整数，所以是整数，所以是整数，所以 k-1 = k-1 = log2nlog2n ，即，即，即，即 k = k = log2nlog2n + 1 + 1 性性性性质质质质5 5：假假假假设设设设对对对对一一一一棵棵棵棵有有有有 n n 个个个个结结结结点点点点的的的的完完完完全全全全二二二二叉叉叉叉树树树树此此此此二二二二叉叉叉叉树树树树的的的的深深深深度度度度为为为为 log2nlog2n +1+1的

45、的的的结结结结点点点点按按按按照照照照层层层层次次次次编编编编号号号号从从从从第第第第 1 1 层层层层到到到到第第第第 log2nlog2n +1 +1 层层层层，每每每每层层层层从从从从左左左左到到到到右右右右，那那那那么么么么对对对对任任任任一一一一结结结结点点点点 i i1 i n1 i n，有，有，有，有23 (1) (1) 假假假假设设设设 i i = = 1 1，那那那那么么么么结结结结点点点点 i i 是是是是二二二二叉叉叉叉树树树树的的的的根根根根，没没没没有有有有双双双双亲亲亲亲结点；假设结点；假设结点；假设结点；假设 i i 1 1，那么其双亲结点是结点，那么其双亲结点是

46、结点，那么其双亲结点是结点，那么其双亲结点是结点 i / 2i / 2 。 (2) (2) 假假假假设设设设 2i 2i n n，那那那那么么么么结结结结点点点点 i i 没没没没有有有有左左左左孩孩孩孩子子子子结结结结点点点点 i i 为为为为叶叶叶叶子结点；否那么其左孩子是结点子结点；否那么其左孩子是结点子结点；否那么其左孩子是结点子结点；否那么其左孩子是结点 2i 2i。 (3) (3) 假假假假设设设设 2i 2i + + 1 1n n，那那那那么么么么结结结结点点点点 i i 没没没没有有有有右右右右孩孩孩孩子子子子；否否否否那那那那么么么么其右孩子是结点其右孩子是结点其右孩子是结点

47、其右孩子是结点 2i + 1 2i + 1。 二二二二叉叉叉叉树树树树和和和和其其其其他他他他数数数数据据据据构构构构造造造造一一一一样样样样也也也也分分分分顺顺顺顺序序序序存存存存储储储储构构构构造造造造和和和和链链链链式式式式存存存存储储储储构构构构造造造造；而而而而链链链链式式式式存存存存储储储储构构构构造造造造又又又又分分分分二二二二叉叉叉叉链链链链表表表表存存存存储储储储构构构构造造造造和和和和三叉链表存储构造。三叉链表存储构造。三叉链表存储构造。三叉链表存储构造。246.2.3 二叉树的存储构造二叉树的存储构造 二二二二叉叉叉叉树树树树的的的的顺顺顺顺序序序序存存存存储储储储构构构

48、构培培培培育育育育是是是是用用用用一一一一组组组组地地地地址址址址延延延延续续续续的的的的存存存存储单元来存放一棵二叉树的一切结点元素。储单元来存放一棵二叉树的一切结点元素。储单元来存放一棵二叉树的一切结点元素。储单元来存放一棵二叉树的一切结点元素。 # define MAX_TREE_SIZE 100 / # define MAX_TREE_SIZE 100 / 二叉树的最大结点数二叉树的最大结点数二叉树的最大结点数二叉树的最大结点数 typedef DataType SqBiTreeMAX_TREE_SIZE; typedef DataType SqBiTreeMAX_TREE_SIZE;

49、 / / 定义顺序树类型定义顺序树类型定义顺序树类型定义顺序树类型SqBiTreeSqBiTree，商定，商定，商定，商定0 0 号单元存储根结点号单元存储根结点号单元存储根结点号单元存储根结点 SqBiTree bt; / SqBiTree bt; /定义了一棵二叉树定义了一棵二叉树定义了一棵二叉树定义了一棵二叉树btbt25 1. 1. 顺序存储构造顺序存储构造顺序存储构造顺序存储构造 顺顺顺顺序序序序存存存存储储储储构构构构造造造造仅仅仅仅适适适适用用用用于于于于完完完完全全全全二二二二叉叉叉叉树树树树。假假假假设设设设存存存存储储储储普普普普通通通通二二二二叉叉叉叉树树树树，那那那那么

50、么么么会会会会呵呵呵呵斥斥斥斥存存存存储储储储空空空空间间间间的的的的浪浪浪浪费费费费，这这这这时时时时就就就就需需需需求求求求运运运运用用用用二叉树的链式存储构造。二叉树的链式存储构造。二叉树的链式存储构造。二叉树的链式存储构造。 二二二二叉叉叉叉树树树树的的的的链链链链式式式式存存存存储储储储构构构构造造造造主主主主要要要要是是是是设设设设计计计计结结结结点点点点构构构构造造造造。根根根根据据据据结结结结点点点点构构构构造造造造的的的的不不不不同同同同，又又又又可可可可以以以以分分分分为为为为二二二二叉叉叉叉链链链链表表表表存存存存储储储储构构构构造造造造和和和和三三三三叉叉叉叉链表存储构

51、造。链表存储构造。链表存储构造。链表存储构造。26 2. 2. 链式存储构造链式存储构造链式存储构造链式存储构造 (1) (1) 二叉链表存储构造二叉链表存储构造二叉链表存储构造二叉链表存储构造tyepdef struct Node tyepdef struct Node DataType DataTypedata;data; structNode structNode *lchild, *rchild; / *lchild, *rchild; / 左右孩子指针左右孩子指针左右孩子指针左右孩子指针 BiTNode *BiTree; BiTNode *BiTree; / / 二叉链表存储构造类型

52、名二叉链表存储构造类型名二叉链表存储构造类型名二叉链表存储构造类型名lchildlchilddatadatarchildrchild左孩子指针左孩子指针左孩子指针左孩子指针右孩子指针右孩子指针右孩子指针右孩子指针数据域数据域数据域数据域27 二二二二叉叉叉叉树树树树的的的的结结结结点点点点由由由由一一一一个个个个数数数数据据据据元元元元素素素素和和和和分分分分别别别别指指指指向向向向其其其其左左左左、右右右右子子子子树树树树的的的的两两两两个个个个分分分分支支支支构构构构成成成成，那那那那么么么么表表表表示示示示二二二二叉叉叉叉树树树树的的的的链链链链表表表表中中中中的的的的结结结结点点点点包

53、包包包括括括括三三三三个个个个域域域域：数数数数据据据据域域域域、左左左左指指指指针针针针域域域域和和和和右右右右指指指指针针针针域域域域，称称称称为为为为二二二二叉叉叉叉链表存储构造。链表存储构造。链表存储构造。链表存储构造。 (2) (2) 三叉链表存储构造三叉链表存储构造三叉链表存储构造三叉链表存储构造tyepdef struct TriTNode tyepdef struct TriTNode TElemType TElemTypedata;data; struct TriTNode struct TriTNode *lchild, *rchild, *parent;*lchild,

54、*rchild, *parent; TriTNode *TriTree; TriTNode *TriTree; / / 三叉链表存储构造类型名三叉链表存储构造类型名三叉链表存储构造类型名三叉链表存储构造类型名左孩子指针左孩子指针左孩子指针左孩子指针右孩子指针右孩子指针右孩子指针右孩子指针数据域数据域数据域数据域lchildlchilddatadataparentparentrchildrchild双亲指针双亲指针双亲指针双亲指针28 为为为为方方方方便便便便找找找找到到到到结结结结点点点点双双双双亲亲亲亲，在在在在二二二二叉叉叉叉链链链链表表表表构构构构造造造造中中中中添添添添加加加加一一一一

55、个个个个指指指指向向向向其其其其双双双双亲亲亲亲结结结结点点点点的的的的指指指指针针针针域域域域，那那那那么么么么表表表表示示示示二二二二叉叉叉叉树树树树的的的的链链链链表表表表中中中中的的的的结结结结点点点点包包包包括括括括四四四四个个个个域域域域：数数数数据据据据域域域域、左左左左指指指指针针针针域域域域、右右右右指指指指针针针针域域域域和和和和双双双双亲亲亲亲指针域，称为三叉链表存储构造。指针域，称为三叉链表存储构造。指针域，称为三叉链表存储构造。指针域，称为三叉链表存储构造。 在在在在二二二二叉叉叉叉树树树树的的的的很很很很多多多多运运运运用用用用中中中中，常常常常要要要要求求求求在在

56、在在二二二二叉叉叉叉树树树树中中中中查查查查找找找找某某某某些些些些指指指指定定定定的的的的结结结结点点点点或或或或对对对对二二二二叉叉叉叉树树树树中中中中全全全全部部部部结结结结点点点点逐逐逐逐一一一一进进进进展展展展某某某某种种种种操操操操作作作作，这就需求依次访问二叉树中的结点，即遍历二叉树。这就需求依次访问二叉树中的结点，即遍历二叉树。这就需求依次访问二叉树中的结点，即遍历二叉树。这就需求依次访问二叉树中的结点，即遍历二叉树。6.4 遍历二叉树遍历二叉树29 遍遍遍遍历历历历二二二二叉叉叉叉树树树树 (traversing (traversing binary binary tree)

57、 tree) 是是是是指指指指按按按按某某某某种种种种规规规规律律律律巡巡巡巡查查查查二二二二叉叉叉叉树树树树，对对对对树树树树中中中中的的的的每每每每个个个个结结结结点点点点访访访访问问问问一一一一次次次次且且且且仅仅仅仅访访访访问问问问一一一一次次次次。在在在在访访访访问问问问每每每每个个个个结结结结点点点点时时时时可可可可对对对对结结结结点点点点进进进进展展展展各各各各种种种种操操操操作作作作，如如如如：输输输输出结点的信息、对结点进展计数、修正结点的信息等。出结点的信息、对结点进展计数、修正结点的信息等。出结点的信息、对结点进展计数、修正结点的信息等。出结点的信息、对结点进展计数、修正

58、结点的信息等。遍历二叉树的操作定义遍历二叉树的操作定义30遍历二叉树的递归算法遍历二叉树的递归算法遍历二叉树的非递归算法遍历二叉树的非递归算法建立二叉树的算法建立二叉树的算法 二二二二叉叉叉叉树树树树的的的的定定定定义义义义是是是是递递递递归归归归的的的的，一一一一棵棵棵棵非非非非空空空空的的的的二二二二叉叉叉叉树树树树由由由由三三三三个个个个根根根根本本本本单单单单元元元元组组组组成成成成：根根根根结结结结点点点点、左左左左子子子子树树树树和和和和右右右右子子子子树树树树。因因因因此此此此，假假假假设设设设能依次遍历这三部分，便是遍历了整个二叉树。能依次遍历这三部分，便是遍历了整个二叉树。能

59、依次遍历这三部分，便是遍历了整个二叉树。能依次遍历这三部分，便是遍历了整个二叉树。 设设设设以以以以 L L、D D、R R 分分分分别别别别表表表表示示示示遍遍遍遍历历历历左左左左子子子子树树树树、访访访访问问问问根根根根结结结结点点点点和和和和遍遍遍遍历历历历右右右右子子子子树树树树，那那那那么么么么能能能能够够够够有有有有 DLRDLR、LDRLDR、LRDLRD、DRLDRL、RDLRDL、RLD RLD 六六六六种种种种遍遍遍遍历历历历二二二二叉叉叉叉树树树树的的的的方方方方案案案案。假假假假设设设设限限限限定定定定先先先先左左左左子子子子树树树树后后后后右右右右子子子子树树树树，那

60、那那那么么么么只只只只需需需需前前前前三三三三种种种种方方方方案案案案，分分分分别别别别称称称称之之之之为为为为先先先先根根根根序序序序遍遍遍遍历历历历 DLRDLR、中中中中根根根根序序序序遍遍遍遍历历历历 LDR LDR 和和和和后后后后根根根根序序序序遍遍遍遍历历历历 LRDLRD。遍遍遍遍历历历历左左左左子子子子树树树树和和和和右右右右子子子子树树树树的的的的规规规规律律律律和和和和遍遍遍遍历历历历整整整整个个个个二二二二叉叉叉叉树树树树的的的的规律一样，因此这三种遍历都具有递归性。规律一样，因此这三种遍历都具有递归性。规律一样，因此这三种遍历都具有递归性。规律一样，因此这三种遍历都具

61、有递归性。316.3.1 遍历二叉树的操作定义遍历二叉树的操作定义 (1) (1) 先根序先根序先根序先根序DLR DLR 遍历二叉树的操作定义遍历二叉树的操作定义遍历二叉树的操作定义遍历二叉树的操作定义 假设二叉树为空，那么空操作；否那么：假设二叉树为空，那么空操作；否那么：假设二叉树为空，那么空操作；否那么：假设二叉树为空，那么空操作；否那么： 访问根结点；访问根结点；访问根结点；访问根结点； 先序遍历左子树；先序遍历左子树；先序遍历左子树；先序遍历左子树； 先序遍历右子树。先序遍历右子树。先序遍历右子树。先序遍历右子树。32 (2) (2) 中根序中根序中根序中根序LDR LDR 遍历二

62、叉树的操作定义遍历二叉树的操作定义遍历二叉树的操作定义遍历二叉树的操作定义 假设二叉树为空，那么空操作；否那么：假设二叉树为空，那么空操作；否那么：假设二叉树为空，那么空操作；否那么：假设二叉树为空，那么空操作；否那么： 中序遍历左子树；中序遍历左子树；中序遍历左子树；中序遍历左子树； 访问根结点；访问根结点；访问根结点；访问根结点； 中序遍历右子树。中序遍历右子树。中序遍历右子树。中序遍历右子树。33 (3) (3) 后根序后根序后根序后根序LRD LRD 遍历二叉树的操作定义遍历二叉树的操作定义遍历二叉树的操作定义遍历二叉树的操作定义 假设二叉树为空，那么空操作；否那么：假设二叉树为空，那

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

64、历二叉树的递归算法中序遍历二叉树的递归算法中序遍历二叉树的递归算法中序遍历二叉树的递归算法后序遍历二叉树的递归算法后序遍历二叉树的递归算法后序遍历二叉树的递归算法后序遍历二叉树的递归算法6.3.2 遍历二叉树的递归算法遍历二叉树的递归算法1. 1. 先序遍历二叉树的递归算法先序遍历二叉树的递归算法先序遍历二叉树的递归算法先序遍历二叉树的递归算法 void PreOrder (BiTree root) void PreOrder (BiTree root) /* /* 采采采采用用用用二二二二叉叉叉叉链链链链表表表表存存存存储储储储构构构构造造造造，rootroot为为为为指指指指向向向向二二二

65、二叉叉叉叉树树树树根根根根结结结结点点点点指指指指针针针针，Visit Visit 是是是是对对对对数数数数据据据据元元元元素素素素操操操操作作作作的的的的运运运运用用用用函函函函数数数数，先先先先序序序序遍遍遍遍历历历历二二二二叉叉叉叉树树树树rootroot的的的的递递递递归归归归算算算算法法法法，对每个数据元素调用函数对每个数据元素调用函数对每个数据元素调用函数对每个数据元素调用函数 Visit Visit 。*/*/ if (root!=NULL) if (root!=NULL) / / 假设假设假设假设rootroot不为空不为空不为空不为空36 Visit(root-data) V

66、isit(root-data) / / 访问根结点访问根结点访问根结点访问根结点 PreOrder (root-LChild) PreOrder (root-LChild) / / 先序遍历左子树先序遍历左子树先序遍历左子树先序遍历左子树PreOrder (root-RChild) /PreOrder (root-RChild) /先序遍历右子树先序遍历右子树先序遍历右子树先序遍历右子树 / PreOrder / PreOrder2. 2. 中序遍历二叉树的递归算法中序遍历二叉树的递归算法中序遍历二叉树的递归算法中序遍历二叉树的递归算法 void InOrder (BiTree root) v

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

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

69、右子树中序遍历右子树中序遍历右子树 / InOrder / InOrder3. 3. 后序遍历二叉树的递归算法后序遍历二叉树的递归算法后序遍历二叉树的递归算法后序遍历二叉树的递归算法38 void PostOrder (BiTree root) void PostOrder (BiTree root) /* /* 采采采采用用用用二二二二叉叉叉叉链链链链表表表表存存存存储储储储构构构构造造造造，rootroot为为为为指指指指向向向向二二二二叉叉叉叉树树树树根根根根结结结结点点点点指指指指针针针针，Visit Visit 是是是是对对对对数数数数据据据据元元元元素素素素操操操操作作作作的的的的

70、运运运运用用用用函函函函数数数数，后后后后序序序序遍遍遍遍历历历历二二二二叉叉叉叉树树树树rootroot的的的的递递递递归归归归算算算算法法法法，对每个数据元素调用函数对每个数据元素调用函数对每个数据元素调用函数对每个数据元素调用函数 Visit Visit 。*/*/ if (root!=NULL) if (root!=NULL) / / 假设假设假设假设rootroot不为空不为空不为空不为空 PostOrder (root-LChild) PostOrder (root-LChild) / / 后序遍历左子树后序遍历左子树后序遍历左子树后序遍历左子树 PostOrder (root-R

71、Child) / PostOrder (root-RChild) /后序遍历右子树后序遍历右子树后序遍历右子树后序遍历右子树 Visit(root-data) Visit(root-data) / / 访问根结点访问根结点访问根结点访问根结点 / PostOrder / PostOrder int Visit ( DataType e ) int Visit ( DataType e ) printf (e); printf (e);/ / 输出数据元素输出数据元素输出数据元素输出数据元素 e e 的值的值的值的值 return OK; return OK; / PrintElement /

72、PrintElement 对对对对每每每每个个个个数数数数据据据据元元元元素素素素进进进进展展展展访访访访问问问问的的的的时时时时候候候候，可可可可以以以以运运运运用用用用调调调调用用用用函数函数函数函数 Visit Visit，最简单的，最简单的，最简单的，最简单的 Visit Visit 函数是：函数是：函数是：函数是：39 在在在在有有有有些些些些算算算算法法法法言言言言语语语语中中中中是是是是不不不不允允允允许许许许递递递递归归归归调调调调用用用用的的的的，所所所所以以以以也也也也有有有有必必必必要要要要讨讨讨讨论论论论遍遍遍遍历历历历二二二二叉叉叉叉树树树树的的的的非非非非递递递递归

73、归归归算算算算法法法法。非非非非递递递递归归归归的的的的程程程程序序序序中中中中要要要要用用用用栈栈栈栈来来来来保保保保管管管管遍遍遍遍历历历历经经经经过过过过的的的的途途途途径径径径，才才才才干干干干访访访访问问问问到到到到二二二二叉叉叉叉树树树树中中中中的的的的每每每每一个结点。分为：一个结点。分为：一个结点。分为：一个结点。分为：先序遍历二叉树的非递归算法先序遍历二叉树的非递归算法先序遍历二叉树的非递归算法先序遍历二叉树的非递归算法40中序遍历二叉树的非递归算法中序遍历二叉树的非递归算法中序遍历二叉树的非递归算法中序遍历二叉树的非递归算法后序遍历二叉树的非递归算法后序遍历二叉树的非递归算

74、法后序遍历二叉树的非递归算法后序遍历二叉树的非递归算法6.3.3 遍历二叉树的非递归算法遍历二叉树的非递归算法 1. 1. 先序遍历二叉树的非递归算法先序遍历二叉树的非递归算法先序遍历二叉树的非递归算法先序遍历二叉树的非递归算法(1) (1) 算法思算法思算法思算法思想想想想 运运运运用用用用一一一一个个个个栈栈栈栈 S S，用用用用以以以以存存存存放放放放曾曾曾曾经经经经访访访访问问问问过过过过的的的的根根根根结结结结点点点点指指指指针针针针，以以以以备备备备在在在在访访访访问问问问该该该该结结结结点点点点的的的的左左左左子子子子树树树树之之之之后后后后再再再再访访访访问问问问其其其其右右右

75、右子子子子树树树树。显显显显然，开场时栈应该为空。然，开场时栈应该为空。然，开场时栈应该为空。然，开场时栈应该为空。 算算算算法法法法开开开开场场场场时时时时，先先先先将将将将栈栈栈栈 S S 初初初初始始始始化化化化，然然然然后后后后令令令令 p p 指指指指向向向向二二二二叉树的根结点，即叉树的根结点，即叉树的根结点，即叉树的根结点，即 p = root p = root。 假假假假设设设设指指指指向向向向根根根根结结结结点点点点的的的的指指指指针针针针非非非非空空空空或或或或者者者者栈栈栈栈非非非非空空空空，那那那那么么么么做做做做如下操作：如下操作：如下操作：如下操作：41 假假假假设

76、设设设指指指指向向向向根根根根结结结结点点点点的的的的指指指指针针针针非非非非空空空空，那那那那么么么么访访访访问问问问根根根根结结结结点点点点；然然然然后后后后将将将将根根根根结结结结点点点点指指指指针针针针进进进进栈栈栈栈；最最最最后后后后将将将将指指指指针针针针指指指指向向向向该该该该结结结结点点点点的的的的左左左左子子子子树根结点，继续遍历；树根结点，继续遍历；树根结点，继续遍历；树根结点，继续遍历；42 假假假假设设设设指指指指向向向向根根根根结结结结点点点点的的的的指指指指针针针针为为为为空空空空，那那那那么么么么应应应应该该该该退退退退至至至至上上上上一一一一层即将栈顶存放的指针

77、出栈。有两种情况：层即将栈顶存放的指针出栈。有两种情况：层即将栈顶存放的指针出栈。有两种情况：层即将栈顶存放的指针出栈。有两种情况： 当指针为空并且栈为空时，遍历终了。当指针为空并且栈为空时，遍历终了。当指针为空并且栈为空时，遍历终了。当指针为空并且栈为空时，遍历终了。 假假假假设设设设从从从从左左左左子子子子树树树树前前前前往往往往，那那那那么么么么应应应应将将将将指指指指针针针针指指指指向向向向当当当当前前前前层层层层即栈顶指针所指根结点的右子树根结点，即栈顶指针所指根结点的右子树根结点，即栈顶指针所指根结点的右子树根结点，即栈顶指针所指根结点的右子树根结点， 继续遍历。继续遍历。继续遍历

78、。继续遍历。 假假假假设设设设从从从从右右右右子子子子树树树树前前前前往往往往，那那那那么么么么阐阐阐阐明明明明当当当当前前前前层层层层遍遍遍遍历历历历终终终终了了了了，应应应应该该该该继继继继续续续续退退退退栈栈栈栈。从从从从另另另另一一一一个个个个角角角角度度度度看看看看，这这这这意意意意味味味味着着着着遍遍遍遍历历历历右右右右子子子子树树树树时不再需求保管当前层的根指针，可以直接修正指针。时不再需求保管当前层的根指针，可以直接修正指针。时不再需求保管当前层的根指针，可以直接修正指针。时不再需求保管当前层的根指针，可以直接修正指针。PreOrder PreOrder 非递归算法的时间复杂度

79、非递归算法的时间复杂度非递归算法的时间复杂度非递归算法的时间复杂度 树树树树中中中中非非非非空空空空链链链链域域域域的的的的个个个个数数数数为为为为 2n2+n12n2+n1，再再再再由由由由二二二二叉叉叉叉树树树树的的的的性性性性质质质质 3 (n0 = n2+1) 3 (n0 = n2+1)，可知：，可知：，可知：，可知：2n2 + n1 = n2 + n2 + n1 = n0 + n1 + n2 - 1 = n - 12n2 + n1 = n2 + n2 + n1 = n0 + n1 + n2 - 1 = n - 1所以，遍历每个结点的时间复杂度为所以，遍历每个结点的时间复杂度为所以，遍

80、历每个结点的时间复杂度为所以，遍历每个结点的时间复杂度为 O(n) O(n)。(2) (2) 算法分算法分算法分算法分析析析析43 假假假假定定定定二二二二叉叉叉叉树树树树 T T 有有有有 n n 个个个个结结结结点点点点，算算算算法法法法中中中中对对对对每每每每个个个个结结结结点点点点都都都都要要要要入入入入栈栈栈栈和和和和出出出出栈栈栈栈一一一一次次次次。因因因因此此此此，入入入入栈栈栈栈和和和和出出出出栈栈栈栈都都都都要要要要执执执执行行行行 n n 次次次次。此此此此外外外外，只只只只需需需需当当当当 p p 为为为为非非非非空空空空时时时时，才才才才对对对对当当当当前前前前在在在在

81、栈栈栈栈顶顶顶顶的的的的结结结结点点点点信信信信息进展访问。息进展访问。息进展访问。息进展访问。PreOrderPreOrder非递归算法所需附加空间非递归算法所需附加空间非递归算法所需附加空间非递归算法所需附加空间44 算算算算法法法法所所所所需需需需求求求求的的的的附附附附加加加加空空空空间间间间为为为为栈栈栈栈用用用用以以以以存存存存放放放放曾曾曾曾经经经经访访访访问问问问的的的的根根根根结结结结点点点点的的的的容容容容量量量量。栈栈栈栈的的的的容容容容量量量量与与与与树树树树的的的的深深深深度度度度有有有有关关关关，假假假假设设设设每每每每个个个个结结结结点点点点需需需需求求求求 1

82、1 个个个个存存存存储储储储单单单单位位位位，那那那那么么么么遍遍遍遍历历历历深深深深度度度度为为为为 k k 的的的的二二二二叉树，栈需求叉树，栈需求叉树，栈需求叉树，栈需求 k k 个存储单位，即所需求的空间为个存储单位，即所需求的空间为个存储单位，即所需求的空间为个存储单位，即所需求的空间为 O(k) O(k)。 2. 2. 中序遍历二叉树的非递归算法中序遍历二叉树的非递归算法中序遍历二叉树的非递归算法中序遍历二叉树的非递归算法 算法思想算法思想算法思想算法思想45 运运运运用用用用一一一一个个个个栈栈栈栈 S S，用用用用以以以以存存存存放放放放待待待待访访访访问问问问的的的的根根根根

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

84、。 假假假假设设设设指指指指向向向向根根根根结结结结点点点点的的的的指指指指针针针针非非非非空空空空或或或或者者者者栈栈栈栈 S S 非非非非空空空空，那那那那么么么么做如下操作：做如下操作：做如下操作：做如下操作： 假假假假设设设设指指指指向向向向根根根根结结结结点点点点指指指指针针针针非非非非空空空空，那那那那么么么么将将将将该该该该指指指指针针针针进进进进栈栈栈栈，然后将指针指向该结点左子树根结点，继续遍历。然后将指针指向该结点左子树根结点，继续遍历。然后将指针指向该结点左子树根结点，继续遍历。然后将指针指向该结点左子树根结点，继续遍历。46 假假假假设设设设指指指指向向向向根根根根结结

85、结结点点点点指指指指针针针针为为为为空空空空，那那那那么么么么应应应应退退退退至至至至上上上上一一一一层层层层即将栈顶存放的指针出栈：即将栈顶存放的指针出栈：即将栈顶存放的指针出栈：即将栈顶存放的指针出栈： 当指针为空并且栈为空时，遍历终了。当指针为空并且栈为空时，遍历终了。当指针为空并且栈为空时，遍历终了。当指针为空并且栈为空时，遍历终了。 假假假假设设设设从从从从左左左左子子子子树树树树前前前前往往往往，那那那那么么么么应应应应访访访访问问问问当当当当前前前前层层层层即即即即栈栈栈栈顶顶顶顶指指指指针针针针所所所所指指指指的的的的根根根根结结结结点点点点，然然然然后后后后将将将将指指指指针

86、针针针指指指指向向向向该该该该结结结结点点点点的的的的右右右右子子子子树根结点，继续遍历；树根结点，继续遍历；树根结点，继续遍历；树根结点，继续遍历； 假假假假设设设设从从从从右右右右子子子子树树树树前前前前往往往往，那那那那么么么么阐阐阐阐明明明明当当当当前前前前层层层层遍遍遍遍历历历历终终终终了了了了，应应应应继继继继续续续续退退退退栈栈栈栈。从从从从另另另另一一一一个个个个角角角角度度度度看看看看，这这这这意意意意味味味味着着着着遍遍遍遍历历历历右右右右子子子子树树树树时时时时不再需求保管当前层的根指针，可直接修正指针。不再需求保管当前层的根指针，可直接修正指针。不再需求保管当前层的根指

87、针，可直接修正指针。不再需求保管当前层的根指针，可直接修正指针。(2)(2)算法描画算法描画void InOrder(BiTree root) void InOrder(BiTree root) /*/*采用二叉链表存储构造，采用二叉链表存储构造，采用二叉链表存储构造，采用二叉链表存储构造，Visit Visit 是对元素操作的运用函数。是对元素操作的运用函数。是对元素操作的运用函数。是对元素操作的运用函数。 中序遍历二叉树中序遍历二叉树中序遍历二叉树中序遍历二叉树T T 的非递归算法，的非递归算法，的非递归算法，的非递归算法，对每个元素调用函数对每个元素调用函数对每个元素调用函数对每个元素调

88、用函数 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 不为空，或者栈不为空，或者栈不为空，或者栈不为空，或者栈 S S 不为空时不为空时不为空

89、时不为空时 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 为空为空为空为空 Pop ( &S, &p ) / Pop ( &S, &p ) /

90、 退栈，将上一层的根结点指针弹出退栈，将上一层的根结点指针弹出退栈，将上一层的根结点指针弹出退栈，将上一层的根结点指针弹出 Visit (p-data); / Visit (p-data); / 访问访问访问访问 p p 指针指向的结点指针指向的结点指针指向的结点指针指向的结点 p = p-Rchild; / p = p-Rchild; / 指针指向右子树根结点，遍历右子树指针指向右子树根结点，遍历右子树指针指向右子树根结点，遍历右子树指针指向右子树根结点，遍历右子树 / else / else / while / while / InOrder / InOrder 树树树树中中中中空空空空链

91、链链链域域域域的的的的个个个个数数数数为为为为 2n0+n12n0+n1，再再再再由由由由二二二二叉叉叉叉树树树树的的的的性性性性质质质质3 (n0 = n2+1)3 (n0 = n2+1)，可知：，可知：，可知：，可知：2n0 + n1 = n0 + n0 + n1 = n0 + n1 + n2 + 1 = n + 12n0 + n1 = n0 + n0 + n1 = n0 + n1 + n2 + 1 = n + 1所以，遍历每个结点的时间复杂度为所以，遍历每个结点的时间复杂度为所以，遍历每个结点的时间复杂度为所以，遍历每个结点的时间复杂度为 O(n) O(n)。(3) (3) 算算算算法法

92、法法分分分分析析析析48InOrder InOrder 非递归算法的时间复杂度非递归算法的时间复杂度非递归算法的时间复杂度非递归算法的时间复杂度 假假假假定定定定二二二二叉叉叉叉树树树树 root root 有有有有 n n 个个个个结结结结点点点点，算算算算法法法法中中中中对对对对每每每每个个个个结结结结点点点点都都都都要要要要入入入入栈栈栈栈和和和和出出出出栈栈栈栈一一一一次次次次。因因因因此此此此，入入入入栈栈栈栈和和和和出出出出栈栈栈栈都都都都要要要要执执执执行行行行 n n 次次次次。此此此此外外外外，只只只只需需需需当当当当 p p 为为为为空空空空时时时时，才才才才对对对对当当当

93、当前前前前在在在在栈栈栈栈顶顶顶顶的的的的结结结结点点点点信息进展访问。信息进展访问。信息进展访问。信息进展访问。InOrder InOrder 非递归算法所需附加空间非递归算法所需附加空间非递归算法所需附加空间非递归算法所需附加空间49 算算算算法法法法所所所所需需需需附附附附加加加加空空空空间间间间为为为为栈栈栈栈用用用用以以以以存存存存放放放放待待待待访访访访问问问问的的的的根根根根结结结结点点点点的的的的容容容容量量量量。栈栈栈栈的的的的容容容容量量量量与与与与树树树树的的的的深深深深度度度度有有有有关关关关，假假假假设设设设每每每每个个个个结结结结点点点点需需需需求求求求 1 1 个

94、个个个存存存存储储储储单单单单位位位位，那那那那么么么么遍遍遍遍历历历历深深深深度度度度为为为为 k k 的的的的二二二二叉叉叉叉树树树树，栈需求栈需求栈需求栈需求 k k 个存储单位，即所需求的空间为个存储单位，即所需求的空间为个存储单位，即所需求的空间为个存储单位，即所需求的空间为 O(k) O(k)。 3. 3. 后序遍历二叉树的非递归算法后序遍历二叉树的非递归算法后序遍历二叉树的非递归算法后序遍历二叉树的非递归算法50(1) (1) 算算算算法法法法思思思思想想想想 在在在在后后后后序序序序遍遍遍遍历历历历中中中中，当当当当搜搜搜搜索索索索指指指指针针针针指指指指向向向向某某某某一一一

95、一结结结结点点点点时时时时，不不不不能能能能马马马马上上上上进进进进展展展展访访访访问问问问，而而而而先先先先要要要要遍遍遍遍历历历历其其其其左左左左子子子子树树树树，所所所所以以以以要要要要将将将将此此此此结结结结点点点点入入入入栈栈栈栈保保保保管管管管。当当当当遍遍遍遍历历历历完完完完它它它它的的的的左左左左子子子子树树树树后后后后，退退退退栈栈栈栈再再再再次次次次得得得得到到到到该该该该结结结结点点点点时时时时，还还还还不不不不能能能能进进进进展展展展访访访访问问问问，还还还还需需需需求求求求遍遍遍遍历历历历其其其其右右右右子子子子树树树树。所以，需求再次将此结点入栈保管。所以，需求再次

96、将此结点入栈保管。所以，需求再次将此结点入栈保管。所以，需求再次将此结点入栈保管。 为为为为了了了了区区区区别别别别同同同同一一一一结结结结点点点点的的的的两两两两次次次次入入入入栈栈栈栈，在在在在此此此此算算算算法法法法中中中中，设设设设计一个栈计一个栈计一个栈计一个栈 S S 存放存放存放存放 SElemType SElemType 类型的数据，其构造为：类型的数据，其构造为：类型的数据，其构造为：类型的数据，其构造为： typedef struct SElemType / typedef struct SElemType / 顺序栈中数据的构造定义顺序栈中数据的构造定义顺序栈中数据的构造

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

98、栈，可以访问。 SElemType; SElemType; 算算算算法法法法开开开开场场场场时时时时，先先先先将将将将栈栈栈栈 S S 初初初初始始始始化化化化，然然然然后后后后令令令令 p p 指指指指向向向向二二二二叉树的根结点，即叉树的根结点，即叉树的根结点，即叉树的根结点，即 p = root p = root。51 假假假假设设设设指指指指向向向向根根根根结结结结点点点点指指指指针针针针不不不不为为为为空空空空，先先先先将将将将 tag tag 置置置置零零零零；再再再再将将将将 tag tag 和和和和根根根根结结结结点点点点一一一一道道道道送送送送入入入入栈栈栈栈中中中中；然然然

99、然后后后后将将将将指指指指针针针针指指指指向向向向该该该该结结结结点点点点的左子树根结点；继续遍历。的左子树根结点；继续遍历。的左子树根结点；继续遍历。的左子树根结点；继续遍历。52 假假假假设设设设指指指指向向向向根根根根结结结结点点点点指指指指针针针针为为为为空空空空，那那那那么么么么应应应应退退退退至至至至上上上上一一一一层层层层，即即即即将将将将栈栈栈栈顶顶顶顶存存存存放放放放的的的的数数数数据据据据项项项项SElemTypeSElemType类类类类型型型型，包包包包括括括括二二二二叉叉叉叉树树树树结点指针和标志变量出栈：结点指针和标志变量出栈：结点指针和标志变量出栈：结点指针和标志

100、变量出栈： 直到栈为空并且指针为空时，遍历终了。直到栈为空并且指针为空时，遍历终了。直到栈为空并且指针为空时，遍历终了。直到栈为空并且指针为空时，遍历终了。 假假假假设设设设 tag tag 为为为为 0 0，那那那那么么么么改改改改动动动动 tag tag 值值值值，将将将将 tag tag 置置置置 1 1；再再再再把把把把 tag tag 和和和和弹弹弹弹出出出出的的的的结结结结点点点点重重重重新新新新装装装装入入入入栈栈栈栈中中中中；然然然然后后后后将将将将指指指指针针针针指指指指向向向向该结点的右子树根结点；继续遍历。该结点的右子树根结点；继续遍历。该结点的右子树根结点；继续遍历。该

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

102、叉树遍历二叉树遍历二叉树 T T 的非递归算法，对每个元素调用函数的非递归算法，对每个元素调用函数的非递归算法，对每个元素调用函数的非递归算法，对每个元素调用函数Visit*/Visit*/ SElemtype Data; SElemtype Data; InitStack (S); Data.p = root; InitStack (S); Data.p = root; / / 运用栈运用栈运用栈运用栈 S S 存放待访问的根结点。令存放待访问的根结点。令存放待访问的根结点。令存放待访问的根结点。令 Data.p Data.p 指向二叉树根结点指向二叉树根结点指向二叉树根结点指向二叉树根结点

103、 do do if ( Data.p ) if ( Data.p ) / / 假设假设假设假设 Data.p Data.p 非空非空非空非空Data.tag = 0;Data.tag = 0;/ / 将将将将 Data.tag Data.tag 置零置零置零置零Push ( S, Data );Push ( S, Data );/ / 将将将将 Data.tag Data.tag 和和和和 Data.p Data.p 一道送入栈一道送入栈一道送入栈一道送入栈 S S Data.p = Data.p-lchild;Data.p = Data.p-lchild;/ / 将将将将指指指指针针针针指指

104、指指向向向向左左左左子子子子树树树树根根根根结结结结点点点点，遍遍遍遍历左子树历左子树历左子树历左子树 (2) (2) 算法描算法描算法描算法描画画画画53 else else / / 假设假设假设假设 Data.p Data.p 为空为空为空为空 Pop ( S, Data ); Pop ( S, Data );/ / 将将将将 Data.tag Data.tag 和和和和 Data.p Data.p 一道弹出一道弹出一道弹出一道弹出 if ( Data.tag = 0 ) / if ( Data.tag = 0 ) / 假设标志变量假设标志变量假设标志变量假设标志变量 Data.tag D

105、ata.tag 为零为零为零为零 Data.tag = 1; / Data.tag = 1; / 将将将将 Data.tag Data.tag 置为置为置为置为 1 1 Push ( S, Data ) Push ( S, Data )/ / 将将将将 Data.tag Data.tag 和和和和 Data.p Data.p 一一一一道道道道送送送送入入入入栈栈栈栈 S S 中中中中 Data.p Data.p = = Data.p-rchild; Data.p-rchild; / / 将将将将指指指指针针针针指指指指向向向向右右右右子子子子树树树树根根根根结结结结点点点点，遍遍遍遍历右子树历

106、右子树历右子树历右子树 54 else else / / 假设标志变量假设标志变量假设标志变量假设标志变量 Data.tag Data.tag 为为为为 1 1 Visit ( Data.p ); / Visit ( Data.p ); / 访问访问访问访问 Data.p Data.p 指向的结点指向的结点指向的结点指向的结点 Data.p = NULL; Data.p = NULL; / / 将将将将 Data.p Data.p 指针置空指针置空指针置空指针置空 while ( ! Data.p & StackEmpty (S) ); while ( ! Data.p & StackEmpt

107、y (S) );return OK;return OK; / PostOrderTraverse / PostOrderTraverse(3) (3) 算算算算法法法法分分分分析析析析55PostOrder 非递归算法的时间复杂度非递归算法的时间复杂度 假假定定二二叉叉树树 root 有有 n 个个结结点点，算算法法中中对对每每个个结结点点都都要要进进展展两两次次入入栈栈和和出出栈栈。因因此此，入入栈栈和和出出栈栈都都要要执执行行 2n 次，那么入栈、出栈的时间复杂度为次，那么入栈、出栈的时间复杂度为 O(n)。 此此外外，每每当当 Data.p 为为空空时时，就就弹弹出出栈栈顶顶的的数数据据

108、项项 Data，然然后后根根据据 Data.tag 的的值值能能否否为为零零，或或访访问问刚刚弹弹出出的的结结点点，或或使使数数据据项项重重新新进进栈栈。重重新新入入栈栈的的时时间间曾曾经经算算在在入入栈栈、出出栈栈所所需需时时间间之之内内，访访问问结结点点的的时时间间显显然然为为 O(n)。所所以以，算算法法总总的的时时间间复复杂杂度度为为 O(n)+O(n)，或者为，或者为 O(n)。PostOrder PostOrder 非递归算法所需附加空间非递归算法所需附加空间非递归算法所需附加空间非递归算法所需附加空间56 算算算算法法法法所所所所需需需需求求求求的的的的附附附附加加加加空空空空间

109、间间间比比比比前前前前面面面面两两两两个个个个算算算算法法法法多多多多。由由由由于于于于 Data.tag Data.tag 变变变变量量量量用用用用 1 1 位位位位二二二二进进进进制制制制就就就就可可可可以以以以表表表表示示示示，因因因因此此此此，所所所所需需需需求求求求的空间依然为的空间依然为的空间依然为的空间依然为 O(k) O(k)，其中，其中，其中，其中 k k 为二叉树的深度。为二叉树的深度。为二叉树的深度。为二叉树的深度。后序遍历方法二算法思想后序遍历方法二算法思想后序遍历方法二算法思想后序遍历方法二算法思想57 从从从从当当当当前前前前结结结结点点点点开开开开场场场场, ,进

110、进进进栈栈栈栈并并并并走走走走左左左左子子子子树树树树, ,直直直直到到到到左左左左子子子子树树树树为为为为空空空空 否那么，走右子树。否那么，走右子树。否那么，走右子树。否那么，走右子树。直到栈为空并且指针为空时，遍历终了。直到栈为空并且指针为空时，遍历终了。直到栈为空并且指针为空时，遍历终了。直到栈为空并且指针为空时，遍历终了。 假假假假设设设设栈栈栈栈顶顶顶顶结结结结点点点点的的的的右右右右子子子子树树树树为为为为空空空空, ,或或或或栈栈栈栈顶顶顶顶结结结结点点点点的的的的右右右右子子子子树树树树为为为为刚刚刚刚访访访访问问问问过过过过的的的的结结结结点点点点, ,那那那那么么么么退退

111、退退栈栈栈栈并并并并访访访访问问问问，然然然然后后后后将将将将当当当当前前前前结结结结点点点点指指指指针置为空。针置为空。针置为空。针置为空。 遍遍遍遍历历历历二二二二叉叉叉叉树树树树是是是是二二二二叉叉叉叉树树树树各各各各种种种种操操操操作作作作的的的的根根根根底底底底，可可可可以以以以在在在在遍遍遍遍历历历历的的的的过过过过程程程程中中中中对对对对结结结结点点点点进进进进展展展展各各各各种种种种操操操操作作作作，比比比比如如如如：对对对对于于于于一一一一棵棵棵棵知知知知树树树树可可可可以以以以求求求求结结结结点点点点的的的的双双双双亲亲亲亲，求求求求结结结结点点点点的的的的孩孩孩孩子子子子

112、结结结结点点点点，断断断断定定定定结结结结点点点点所所所所在在在在的的的的层层层层次次次次等等等等；反反反反之之之之，给给给给定定定定一一一一棵棵棵棵二二二二叉叉叉叉树树树树的的的的遍遍遍遍历历历历序序序序列列列列结结结结点，可建立二叉树的存储构造。点，可建立二叉树的存储构造。点，可建立二叉树的存储构造。点，可建立二叉树的存储构造。586.3.4 建立二叉树的算法建立二叉树的算法 例例例例如如如如，假假假假设设设设按按按按照照照照先先先先序序序序序序序序列列列列建建建建立立立立二二二二叉叉叉叉树树树树的的的的二二二二叉叉叉叉链链链链表表表表构构构构造造造造，对对对对以以以以下下下下图图图图所所

113、所所示示示示二二二二叉叉叉叉树树树树，可可可可以以以以按按按按照照照照“ “扩扩扩扩展展展展先先先先序序序序遍遍遍遍历历历历顺顺顺顺序读入字符，即可以建立相应的二叉链表。序读入字符，即可以建立相应的二叉链表。序读入字符，即可以建立相应的二叉链表。序读入字符，即可以建立相应的二叉链表。A AB BC CD DF FE EG GA B C A B C D E D E G G F F59 void CreateBiTree ( BiTree *bt) void CreateBiTree ( BiTree *bt) /*/*按按按按先先先先序序序序次次次次序序序序输输输输入入入入二二二二叉叉叉叉树树树

114、树中中中中结结结结点点点点的的的的值值值值一一一一个个个个字字字字符符符符， 圆圆圆圆点点点点字字字字符符符符表表表表示空树。构造二叉链表表示的二叉树示空树。构造二叉链表表示的二叉树示空树。构造二叉链表表示的二叉树示空树。构造二叉链表表示的二叉树 T T。*/*/ / CreateBiTree / CreateBiTree scanf (&ch); scanf (&ch);/ / 输入字符输入字符输入字符输入字符 if ( ch = = if ( ch = = ) *bt = NULL; ) *bt = NULL;/ / 假设是字符那么令指针为空假设是字符那么令指针为空假设是字符那么令指针为空

115、假设是字符那么令指针为空 else else if ( ! ( *bt = ( BiTNode * ) malloc ( sizeof ( BiTNode ) ) ) ) if ( ! ( *bt = ( BiTNode * ) malloc ( sizeof ( BiTNode ) ) ) ) return; return; (*bt)-data = ch; (*bt)-data = ch;/ / 生成根结点生成根结点生成根结点生成根结点 CreateBiTree ( &(*bt)-LChild ); CreateBiTree ( &(*bt)-LChild );/ / 构造左子树构造左子树

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

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

118、算，假假假假设设设设所所所所思思思思索索索索的的的的结结结结点点点点是是是是非非非非叶叶叶叶子子子子结结结结点点点点，那么该结点的左孩子就是它的后继结点。那么该结点的左孩子就是它的后继结点。那么该结点的左孩子就是它的后继结点。那么该结点的左孩子就是它的后继结点。 假假假假设设设设结结结结点点点点的的的的左左左左孩孩孩孩子子子子不不不不存存存存在在在在，那那那那么么么么该该该该结结结结点点点点的的的的右右右右孩孩孩孩子子子子就就就就是它的后继结点。是它的后继结点。是它的后继结点。是它的后继结点。 假假假假设设设设所所所所思思思思索索索索的的的的结结结结点点点点是是是是叶叶叶叶子子子子结结结结点点

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

120、F FE EG G前驱前驱前驱前驱前驱前驱前驱前驱63 对对对对于于于于求求求求前前前前驱驱驱驱运运运运算算算算，假假假假设设设设所所所所思思思思索索索索的的的的结结结结点点点点是是是是非非非非叶叶叶叶子子子子结结结结点点点点，那么该结点的右孩子就是它的前驱结点。那么该结点的右孩子就是它的前驱结点。那么该结点的右孩子就是它的前驱结点。那么该结点的右孩子就是它的前驱结点。 假设该结点的右孩子不存在，那么该结点的左孩子假设该结点的右孩子不存在，那么该结点的左孩子假设该结点的右孩子不存在，那么该结点的左孩子假设该结点的右孩子不存在，那么该结点的左孩子就是它的前驱结点。就是它的前驱结点。就是它的前驱结

121、点。就是它的前驱结点。 假设所思索的结点是叶子结点，那么要找到该结点假设所思索的结点是叶子结点，那么要找到该结点假设所思索的结点是叶子结点，那么要找到该结点假设所思索的结点是叶子结点，那么要找到该结点的前驱结点，就必需遍历二叉树。的前驱结点，就必需遍历二叉树。的前驱结点，就必需遍历二叉树。的前驱结点，就必需遍历二叉树。 对于求后继运算，在后序排序下，不论何种情况都对于求后继运算，在后序排序下，不论何种情况都对于求后继运算，在后序排序下，不论何种情况都对于求后继运算，在后序排序下，不论何种情况都需求遍历二叉树。需求遍历二叉树。需求遍历二叉树。需求遍历二叉树。 (3) (3) 中序排序如何实现求前

122、驱和求后继运算？中序排序如何实现求前驱和求后继运算？中序排序如何实现求前驱和求后继运算？中序排序如何实现求前驱和求后继运算？ 对对对对于于于于求求求求后后后后继继继继运运运运算算算算，假假假假设设设设所所所所思思思思索索索索的的的的结结结结点点点点有有有有右右右右孩孩孩孩子子子子，那那那那么么么么就就就就要要要要从从从从该该该该右右右右孩孩孩孩子子子子开开开开场场场场，顺顺顺顺着着着着该该该该右右右右孩孩孩孩子子子子的的的的左左左左孩孩孩孩子子子子链链链链域域域域找找找找下下下下去去去去，不不不不断断断断找找找找到到到到左左左左孩孩孩孩子子子子的的的的链链链链域域域域是是是是空空空空为为为为止

123、止止止，最最最最后后后后这这这这个个个个结结结结点点点点就就就就是是是是所所所所思思思思索索索索结结结结点点点点的的的的后后后后继继继继结结结结点点点点；假假假假设设设设所所所所思思思思索索索索的的的的结结结结点点点点无无无无右右右右孩孩孩孩子，那么就要遍历二叉树。子，那么就要遍历二叉树。子，那么就要遍历二叉树。子，那么就要遍历二叉树。N NR1R1R2R2RkRk后继后继后继后继64 对对对对于于于于求求求求前前前前驱驱驱驱运运运运算算算算，假假假假设设设设所所所所思思思思索索索索的的的的结结结结点点点点有有有有左左左左孩孩孩孩子子子子，那那那那么么么么就就就就要要要要从从从从该该该该左左左

124、左孩孩孩孩子子子子开开开开场场场场，顺顺顺顺着着着着该该该该左左左左孩孩孩孩子子子子的的的的右右右右孩孩孩孩子子子子链链链链域域域域找找找找下下下下去去去去，不不不不断断断断找找找找到到到到右右右右孩孩孩孩子子子子的的的的链链链链域域域域是是是是空空空空为为为为止止止止，最最最最后后后后这这这这个个个个结结结结点点点点就就就就是是是是所所所所思思思思索索索索结结结结点点点点的的的的前前前前驱驱驱驱结结结结点点点点；假假假假设设设设所所所所思思思思索索索索的的的的结结结结点点点点无无无无左左左左孩孩孩孩子，那么就要遍历二叉树。子，那么就要遍历二叉树。子，那么就要遍历二叉树。子，那么就要遍历二叉树

125、。N NR1R1R2R2RkRk前驱前驱前驱前驱 方方方方法法法法一一一一：为为为为了了了了方方方方便便便便地地地地实实实实现现现现求求求求结结结结点点点点的的的的前前前前驱驱驱驱和和和和求求求求后后后后继继继继运运运运算算算算，可可可可以以以以在在在在原原原原有有有有二二二二叉叉叉叉链链链链表表表表的的的的结结结结点点点点构构构构造造造造中中中中，再再再再添添添添加加加加两两两两个个个个链链链链域域域域：plink plink 和和和和 nlinknlink，分分分分别别别别指指指指示示示示结结结结点点点点在在在在依依依依任任任任一一一一次次次次序序序序遍历时得到的前驱和后继信息。遍历时得到

126、的前驱和后继信息。遍历时得到的前驱和后继信息。遍历时得到的前驱和后继信息。 (4) (4) 如如如如何何何何保保保保管管管管在在在在遍遍遍遍历历历历二二二二叉叉叉叉树树树树的的的的动动动动态态态态过过过过程程程程中中中中得得得得到到到到的的的的某某某某一结点的前驱和后继信息？一结点的前驱和后继信息？一结点的前驱和后继信息？一结点的前驱和后继信息？ 方法有两个。方法有两个。方法有两个。方法有两个。65 方方方方法法法法二二二二： 在在在在有有有有 n n 个个个个结结结结点点点点的的的的二二二二叉叉叉叉树树树树中中中中，有有有有 n+1 n+1 个个个个空空空空链链链链域域域域。由由由由此此此此

127、，可可可可以以以以利利利利用用用用这这这这些些些些空空空空链链链链域域域域来来来来存存存存放放放放结结结结点点点点的的的的前前前前驱驱驱驱和后继的信息。和后继的信息。和后继的信息。和后继的信息。66 试试试试做做做做如如如如下下下下规规规规定定定定：假假假假设设设设结结结结点点点点有有有有左左左左子子子子树树树树，那那那那么么么么其其其其 lchild lchild 域域域域指指指指示示示示其其其其左左左左孩孩孩孩子子子子，否否否否那那那那么么么么令令令令 lchild lchild 域域域域指指指指示示示示其其其其前前前前驱驱驱驱；假假假假设设设设结结结结点点点点有有有有右右右右子子子子树树

128、树树，那那那那么么么么其其其其 rchild rchild 域域域域指指指指示示示示其其其其右右右右孩孩孩孩子子子子，否否否否那那那那么令么令么令么令 rchild rchild 域指示其后继。域指示其后继。域指示其后继。域指示其后继。 为为为为了了了了防防防防止止止止混混混混淆淆淆淆，需需需需改改改改动动动动二二二二叉叉叉叉链链链链表表表表的的的的结结结结点点点点构构构构造造造造，添添添添加两个标志域：加两个标志域：加两个标志域：加两个标志域：ltag ltag 和和和和 rtag rtag。lchildlchildltagltagdatadatartagrtagrchildrchild其中

129、：其中：其中：其中：ltag =ltag =0 01 1lchild lchild 域指示结点的左孩子域指示结点的左孩子域指示结点的左孩子域指示结点的左孩子lchild lchild 域指示结点的前驱域指示结点的前驱域指示结点的前驱域指示结点的前驱rtag =rtag =0 01 1rchild rchild 域指示结点的右孩子域指示结点的右孩子域指示结点的右孩子域指示结点的右孩子rchild rchild 域指示结点的后继域指示结点的后继域指示结点的后继域指示结点的后继左孩子或前驱域左孩子或前驱域左孩子或前驱域左孩子或前驱域右孩子或后继域右孩子或后继域右孩子或后继域右孩子或后继域数据域数据域

130、数据域数据域左标志域左标志域左标志域左标志域右标志域右标志域右标志域右标志域676.4.2 二叉线索树的定义二叉线索树的定义 这这这这种种种种存存存存储储储储方方方方式式式式利利利利用用用用了了了了二二二二叉叉叉叉链链链链表表表表中中中中原原原原有有有有的的的的空空空空链链链链域域域域，提高了构造的存储密度，是一种适用的做法。提高了构造的存储密度，是一种适用的做法。提高了构造的存储密度，是一种适用的做法。提高了构造的存储密度，是一种适用的做法。 相关概念如下：相关概念如下：相关概念如下：相关概念如下：68 线线线线索索索索链链链链表表表表：以以以以这这这这种种种种结结结结点点点点构构构构造造造

131、造构构构构成成成成的的的的二二二二叉叉叉叉链链链链表表表表作作作作为二叉树的存储构造称之。为二叉树的存储构造称之。为二叉树的存储构造称之。为二叉树的存储构造称之。 线线线线索索索索：在在在在线线线线索索索索链链链链表表表表中中中中指指指指向向向向结结结结点点点点前前前前驱驱驱驱和和和和后后后后继继继继的的的的指指指指针称之。针称之。针称之。针称之。 线索二叉树：加上线索的二叉树称之。线索二叉树：加上线索的二叉树称之。线索二叉树：加上线索的二叉树称之。线索二叉树：加上线索的二叉树称之。 线线线线索索索索化化化化：对对对对二二二二叉叉叉叉树树树树以以以以某某某某种种种种次次次次序序序序遍遍遍遍历历

132、历历使使使使其其其其变变变变为为为为线线线线索二叉树的过程称之。索二叉树的过程称之。索二叉树的过程称之。索二叉树的过程称之。typedef struct BiThrNode typedef struct BiThrNode DataType DataType data; data; / / 数据域数据域数据域数据域 struct BiThrNode struct BiThrNode *lchild, *rchild; *lchild, *rchild;/ / 左右孩子指针左右孩子指针左右孩子指针左右孩子指针 PointerTag PointerTag ltag, rtag; ltag, rta

133、g; / / 左右标志左右标志左右标志左右标志 BiThrNode, *BiThrTree; BiThrNode, *BiThrTree; / / 线索二叉树的类型名线索二叉树的类型名线索二叉树的类型名线索二叉树的类型名通常，线索二叉树指中序线索二叉树，简称线索树。通常，线索二叉树指中序线索二叉树，简称线索树。通常，线索二叉树指中序线索二叉树，简称线索树。通常，线索二叉树指中序线索二叉树，简称线索树。696.4.3 二叉树线索的存储构造二叉树线索的存储构造 为了方便起见，仿照线性表的存储构造：为了方便起见，仿照线性表的存储构造：为了方便起见，仿照线性表的存储构造：为了方便起见，仿照线性表的存储

134、构造：70 在在在在二二二二叉叉叉叉树树树树线线线线索索索索链链链链表表表表上上上上也也也也添添添添加加加加一一一一个个个个头头头头结结结结点点点点，并并并并令令令令其其其其 lchild lchild 域域域域指指指指针针针针指指指指向向向向二二二二叉叉叉叉树树树树的的的的根根根根结结结结点点点点，其其其其 rchild rchild 域域域域指指指指针指向中序遍历二叉树时访问的最后一个结点；针指向中序遍历二叉树时访问的最后一个结点；针指向中序遍历二叉树时访问的最后一个结点；针指向中序遍历二叉树时访问的最后一个结点； 令令令令二二二二叉叉叉叉树树树树中中中中序序序序序序序序列列列列第第第第一

135、一一一个个个个结结结结点点点点的的的的 lchild lchild 域域域域指指指指针和最后一个结点的针和最后一个结点的针和最后一个结点的针和最后一个结点的 rchild rchild 域指针均指向头结点。域指针均指向头结点。域指针均指向头结点。域指针均指向头结点。 (1) (1) 算法思想算法思想算法思想算法思想71 判判判判别别别别给给给给定定定定结结结结点点点点 t t 的的的的左左左左指指指指针针针针 lchild lchild 能能能能否否否否指指指指向向向向头头头头结结结结点点点点 ThrtThrt。假假假假设设设设是是是是，那那那那么么么么前前前前往往往往 ；假假假假设设设设否否

136、否否，那那那那么么么么继继继继续续续续下下下下面面面面的的的的操操操操作。作。作。作。 判判判判别别别别给给给给定定定定结结结结点点点点 t t 的的的的左左左左标标标标志志志志 ltag ltag 能能能能否否否否为为为为 1 1。假假假假设设设设为为为为 1 1，那那那那么么么么t-LChildt-LChild指指指指向向向向t t的的的的前前前前驱驱驱驱。当当当当t-LChild=0t-LChild=0时时时时，那那那那么么么么阐阐阐阐明明明明 p p 指指指指向向向向结结结结点点点点 t t 的的的的左左左左孩孩孩孩子子子子(p=t-LChild)(p=t-LChild)，这这这这时时

137、时时就就就就需需需需求求求求顺顺顺顺着着着着 p p 所所所所指指指指结结结结点点点点的的的的右右右右链链链链域域域域寻寻寻寻觅觅觅觅，直直直直到到到到结结结结点点点点右右右右标标标标志志志志 rtag rtag 为为为为 1 1；假假假假设设设设为为为为 1 1，那那那那么么么么阐阐阐阐明明明明 p p 指指指指向向向向结结结结点点点点 t t 的的的的线线线线索索索索，即即即即 p p 所指向的结点就是结点所指向的结点就是结点所指向的结点就是结点所指向的结点就是结点 t t 的前驱。的前驱。的前驱。的前驱。6.4.4 二叉线索树的操作二叉线索树的操作 1. 1. 在二叉线索树中求结点的中序

138、前驱在二叉线索树中求结点的中序前驱在二叉线索树中求结点的中序前驱在二叉线索树中求结点的中序前驱 int InPre( BiThrTree t, BiThrTree p ) int InPre( BiThrTree t, BiThrTree p ) / / t t 指指指指向向向向中中中中序序序序线线线线索索索索树树树树中中中中某某某某一一一一结结结结点点点点，p p 前前前前往往往往此此此此结结结结点点点点的的的的前前前前驱驱驱驱； 并并并并前前前前往往往往 OKOK p = t-lchild; p = t-lchild;/ / 将将将将 t t 的的的的 lchild lchild 域的值赋

139、给域的值赋给域的值赋给域的值赋给 p p if ( p = Thrt ) if ( p = Thrt ) return ERROR; return ERROR; / / 假假假假设设设设 p p 指指指指向向向向头头头头结结结结点点点点，那那那那么么么么出出出出错错错错 if ( t-ltag = 0) if ( t-ltag = 0) / / 假设假设假设假设 t t 的左标志为的左标志为的左标志为的左标志为 0 0 while ( p-rtag = =0) p = p-rchild; while ( p-rtag = =0) p = p-rchild; / / 顺着顺着顺着顺着 t t 的

140、左孩子的右链域寻觅，直到结点右标志是的左孩子的右链域寻觅，直到结点右标志是的左孩子的右链域寻觅，直到结点右标志是的左孩子的右链域寻觅，直到结点右标志是 1 1 为止为止为止为止 return OK; return OK; / InPre / InPre(2) (2) 算法实现算法实现算法实现算法实现72 (3) (3) 算法分析算法分析算法分析算法分析73 假假假假设设设设 t t 所所所所指指指指向向向向结结结结点点点点的的的的左左左左孩孩孩孩子子子子有有有有 k k 层层层层右右右右孩孩孩孩子子子子，那那那那么么么么需需需需求求求求进进进进展展展展 k+1 k+1 次次次次比比比比较较较较

141、，因因因因此此此此 Inpre Inpre 算算算算法法法法的的的的时时时时间间间间复复复复杂杂杂杂度度度度为为为为 O(k)O(k)。 (1) (1) 算法思想算法思想算法思想算法思想74 判判判判别别别别给给给给定定定定结结结结点点点点 t t 的的的的右右右右指指指指针针针针 rchild rchild 能能能能否否否否指指指指向向向向头头头头结结结结点点点点 ThrtThrt。假设是，那么前往。假设是，那么前往。假设是，那么前往。假设是，那么前往 ERROR ERROR；假设否，那么继续。；假设否，那么继续。；假设否，那么继续。；假设否，那么继续。 判判判判别别别别给给给给定定定定结结

142、结结点点点点 t t 的的的的右右右右标标标标志志志志 rtag rtag 能能能能否否否否为为为为 0 0。假假假假设设设设为为为为 0 0，那那那那么么么么用用用用 p p 指指指指向向向向结结结结点点点点 t t 的的的的右右右右孩孩孩孩子子子子，这这这这时时时时就就就就需需需需求求求求顺顺顺顺着着着着 p p 所所所所指指指指结结结结点点点点的的的的左左左左链链链链域域域域寻寻寻寻觅觅觅觅，直直直直到到到到结结结结点点点点左左左左标标标标志志志志 ltag ltag 为为为为 1 1；假假假假设设设设为为为为 1 1，那那那那么么么么阐阐阐阐明明明明 p p 指指指指向向向向结结结结点

143、点点点 t t 的的的的线线线线索索索索，即即即即 p p 所所所所指指指指向向向向的的的的结点就是结点结点就是结点结点就是结点结点就是结点 t t 的后继。的后继。的后继。的后继。 2. 2. 在二叉线索树中求结点的中序后继在二叉线索树中求结点的中序后继在二叉线索树中求结点的中序后继在二叉线索树中求结点的中序后继 int InNext ( BiThrTree t, BiThrTree p ) int InNext ( BiThrTree t, BiThrTree p ) / / t t 指指指指向向向向中中中中序序序序线线线线索索索索树树树树中中中中某某某某一一一一结结结结点点点点，p p

144、前前前前往往往往此此此此结结结结点点点点的的的的后后后后继继继继； 并并并并前前前前往往往往 OKOK p = t-rchild; p = t-rchild;/ / 将将将将 t t 的的的的 rchild rchild 域值赋给域值赋给域值赋给域值赋给 p p if ( p = =Thrt ) if ( p = =Thrt ) return ERROR; return ERROR;/ / 假假假假设设设设 p p 指指指指向向向向头头头头结结结结点点点点，那那那那么么么么出出出出错错错错 if ( t-rtag = 0 ) if ( t-rtag = 0 ) / / 假设假设假设假设 t t

145、 的右标志为的右标志为的右标志为的右标志为 0 0 while ( p-ltag = =0) p = p-lchild; while ( p-ltag = =0) p = p-lchild; / / 顺着顺着顺着顺着 t t 的右孩子的左链域寻觅，直到结点左标志是的右孩子的左链域寻觅，直到结点左标志是的右孩子的左链域寻觅，直到结点左标志是的右孩子的左链域寻觅，直到结点左标志是 1 1 为止为止为止为止 return OK; return OK; / InNext / InNext(2) (2) 算法实现算法实现算法实现算法实现75 (3) (3) 算法分析算法分析算法分析算法分析76 假假假假

146、设设设设 t t 所所所所指指指指向向向向结结结结点点点点的的的的右右右右孩孩孩孩子子子子有有有有 k k 层层层层左左左左孩孩孩孩子子子子，那那那那么么么么需需需需求求求求进进进进展展展展 k+1 k+1 次次次次比比比比较较较较，因因因因此此此此 Next_Thr Next_Thr 算算算算法法法法的的的的时时时时间间间间复复复复杂杂杂杂度度度度为为为为 O(k) O(k)。 下下下下面面面面给给给给出出出出将将将将值值值值为为为为 e e 的的的的新新新新结结结结点点点点 r r 插插插插入入入入到到到到中中中中序序序序线线线线索索索索树树树树中中中中，作为结点作为结点作为结点作为结点

147、p p 的右孩子。的右孩子。的右孩子。的右孩子。 (1) (1) 算法思想算法思想算法思想算法思想77 建立新结点建立新结点建立新结点建立新结点 r r，使其数据域的值为，使其数据域的值为，使其数据域的值为，使其数据域的值为 e e； 假设结点假设结点假设结点假设结点 p p 无右孩子，那么做：无右孩子，那么做：无右孩子，那么做：无右孩子，那么做： 将新结点将新结点将新结点将新结点 r r 插入线索树中作为结点插入线索树中作为结点插入线索树中作为结点插入线索树中作为结点 p p 的右孩子。的右孩子。的右孩子。的右孩子。 结结结结点点点点 p p 的的的的后后后后继继继继是是是是新新新新结结结结

148、点点点点 r r的的的的后后后后继继继继，r r的的的的前前前前驱驱驱驱是是是是 p p；且；且；且；且r.ltag = 1r.ltag = 1，r.rtag = 1r.rtag = 1。 修正修正修正修正 p.rchild, p.rchild,使其指向新结点使其指向新结点使其指向新结点使其指向新结点 r, r,且且且且 t.rtag = 0 t.rtag = 0。 3. 3. 在二叉线索树中插入结点在二叉线索树中插入结点在二叉线索树中插入结点在二叉线索树中插入结点 假设假设假设假设 p p 有右孩子，那么做：有右孩子，那么做：有右孩子，那么做：有右孩子，那么做：78 将新结点将新结点将新结点

149、将新结点 r r 插入到线索树中作为结点插入到线索树中作为结点插入到线索树中作为结点插入到线索树中作为结点 p p 的右孩子；的右孩子；的右孩子；的右孩子； p p 的的的的右右右右子子子子树树树树在在在在新新新新结结结结点点点点 r r 插插插插入入入入之之之之后后后后，应应应应该该该该成成成成为为为为新新新新结结结结点点点点 r r 的的的的右右右右子子子子树树树树，这这这这样样样样就就就就有有有有 r.rtag r.rtag = = 0 0；新新新新结结结结点点点点 r r 的的的的前前前前驱驱驱驱是是是是 p p；且；且；且；且 r.ltag = 1 r.ltag = 1； 修正修正修

150、正修正 p.rchild p.rchild，使其指向新结点，使其指向新结点，使其指向新结点，使其指向新结点 r r，且，且，且，且 p.rtag = 0 p.rtag = 0。 求求求求出出出出新新新新结结结结点点点点 r r 的的的的后后后后继继继继，并并并并修修修修正正正正 r r 的的的的后后后后继继继继的的的的 lchild lchild 域，使其指向新结点域，使其指向新结点域，使其指向新结点域，使其指向新结点 r r，即这个结点的前驱应该为，即这个结点的前驱应该为，即这个结点的前驱应该为，即这个结点的前驱应该为 q q。int InsNode(BiThrTree Thrt, BiTh

151、rTree p, BiThrTree r) / 将将新新结结点点r插插入入到到中中序序线线索索树树中中作作为为结结点点 p的的右右孩孩子子，并并前前往往 OK if ( ! ( r = ( BiThrTree ) malloc ( sizeof ( BiThrNode ) ) ) ) if ( ! ( r = ( BiThrTree ) malloc ( sizeof ( BiThrNode ) ) ) ) exit ( OVERFLOW ); exit ( OVERFLOW ); r-data = e; r-data = e; r-rchild = p-rchild; r-rchild =

152、p-rchild;r-rtag = p-rtag;r-rtag = p-rtag; r-lchild = p; r-lchild = p;r-ltag = 1;r-ltag = 1; p-rchild = r; p-rchild = r;p-rtag = 0;p-rtag = 0; if ( r-rtag = 0 ) InNext ( &r, &s ); s-lchild = r; if ( r-rtag = 0 ) InNext ( &r, &s ); s-lchild = r; / / 假假假假设设设设 r r 的的的的右右右右标标标标志志志志为为为为 0 0，那那那那么么么么寻寻寻寻觅觅

153、觅觅 r r 的的的的后后后后继继继继 s s，并并并并将将将将 r r 作作作作为为为为 s s 的的的的前驱前驱前驱前驱 return OK return OK /InsNode /InsNode(2) 算法描画算法描画79 (3) 算法分析算法分析80 InsNode InsNode 算算算算法法法法的的的的执执执执行行行行时时时时间间间间主主主主要要要要取取取取决决决决于于于于 InNext InNext (r, (r, s) s) 算算算算法法法法求求求求结结结结点点点点 r r 的的的的后后后后继继继继 s s。假假假假设设设设 r r 的的的的右右右右孩孩孩孩子子子子有有有有 k

154、 k 层层层层左左左左孩孩孩孩子子子子，那那那那么么么么寻寻寻寻觅觅觅觅 r r 的的的的后后后后继继继继 s s 需需需需求求求求进进进进展展展展 k+1 k+1 次次次次比比比比较较较较，因因因因此此此此 Next_Thr Next_Thr 算算算算法法法法时时时时间间间间复复复复杂杂杂杂度度度度为为为为 O(k)O(k)。故故故故 InNext InNext 算算算算法法法法的时间复杂度也为的时间复杂度也为的时间复杂度也为的时间复杂度也为 O(k) O(k)。 同同同同理理理理，可可可可以以以以编编编编写写写写出出出出将将将将值值值值为为为为 e e 的的的的新新新新结结结结点点点点 r

155、 r 插插插插入入入入到到到到中中中中序序序序线索树中，作为结点线索树中，作为结点线索树中，作为结点线索树中，作为结点 p p 的左孩子。的左孩子。的左孩子。的左孩子。 (1) (1) 算法思想算法思想算法思想算法思想81 令令令令 p p 指指指指向向向向根根根根结结结结点点点点，且且且且当当当当二二二二叉叉叉叉树树树树为为为为非非非非空空空空树树树树或或或或遍遍遍遍历未终了时，继续做如下操作；历未终了时，继续做如下操作；历未终了时，继续做如下操作；历未终了时，继续做如下操作； 顺顺顺顺着着着着 p p 的的的的左左左左链链链链域域域域寻寻寻寻觅觅觅觅，直直直直到到到到结结结结点点点点的的的

156、的左左左左标标标标志志志志域域域域 ltag = 1 ltag = 1 时为止，即结点的左链域时为止，即结点的左链域时为止，即结点的左链域时为止，即结点的左链域 lchild lchild 为空；为空；为空；为空； 访问其左链域访问其左链域访问其左链域访问其左链域 lchild lchild 为空的结点；为空的结点；为空的结点；为空的结点； 4. 4. 遍历二叉线索树遍历二叉线索树遍历二叉线索树遍历二叉线索树 当当当当 p p 的的的的右右右右标标标标志志志志域域域域 rtag rtag = = 1 1，并并并并且且且且右右右右链链链链域域域域 rchild rchild 不不不不指指指指向向

157、向向头头头头结结结结点点点点时时时时即即即即 p p 的的的的 rchild rchild 指指指指向向向向后后后后继继继继，那那那那么么么么访访访访问后继；问后继；问后继；问后继；82 当当当当 p p 的的的的右右右右标标标标志志志志域域域域 rtag rtag = = 0 0即即即即 p p 的的的的 rchild rchild 指指指指向右孩子，或右链域向右孩子，或右链域向右孩子，或右链域向右孩子，或右链域 rchild rchild 指向头结点时，那么令指向头结点时，那么令指向头结点时，那么令指向头结点时，那么令 p = p-rchild p = p-rchild 当当当当 p p

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

159、hrt ) / 当空树或遍历终了时，当空树或遍历终了时，p = = Thrt 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

160、 = p-rchild; Visit ( p-data ); / while / InOrderTraverse(2) (2) 算法描画算法描画 void TInOrder ( BiThrTree Thrt) void TInOrder ( BiThrTree Thrt) /*Thrt /*Thrt 指指指指向向向向中中中中序序序序线线线线索索索索树树树树的的的的头头头头结结结结点点点点， 头头头头结结结结点点点点的的的的左左左左链链链链域域域域 lchild lchild 指指指指向向向向根根根根结结结结点点点点， 遍遍遍遍历历历历中中中中序序序序线线线线索索索索树树树树 T T 的的的的非

161、非非非递递递递归归归归算算算算法法法法， 对对对对每每每每个个个个数数数数据据据据元元元元素素素素调调调调用函数用函数用函数用函数 Visit Visit 。*/*/ p = Thrt-lchild; / p p = Thrt-lchild; / p 指向根结点指向根结点指向根结点指向根结点 while ( p != Thrt ) / while ( p != Thrt ) / 当空树或遍历终了时，当空树或遍历终了时，当空树或遍历终了时，当空树或遍历终了时，p = = Thrt p = = Thrt while ( p-ltag = = 0 ) p = p-lchild; while ( p-

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

163、p-rchild ! = Thrt ) while ( p-rtag = = 1 & p-rchild ! = Thrt ) / / 当当当当 p p 右右右右标标标标志志志志为为为为 1 1 且且且且右右右右链链链链域域域域 rchild rchild 不不不不为为为为头头头头结结结结点点点点时时时时， 那那那那么么么么访访访访问问问问后继结点后继结点后继结点后继结点p = p-rchild;p = p-rchild; Visit ( p-data ); Visit ( p-data ); (3) (3) 算法分析算法分析算法分析算法分析85 TInOrder TInOrder 算法的时间复

164、杂度为算法的时间复杂度为算法的时间复杂度为算法的时间复杂度为 O(n) O(n)。 在在在在中中中中序序序序线线线线索索索索树树树树上上上上遍遍遍遍历历历历，虽虽虽虽然然然然时时时时间间间间复复复复杂杂杂杂度度度度也也也也为为为为 O(n)O(n)，但但但但是是是是其其其其常常常常数数数数因因因因子子子子要要要要比比比比在在在在中中中中序序序序二二二二叉叉叉叉树树树树上上上上遍遍遍遍历历历历小小小小，并并并并且且且且不不不不需求设立栈。需求设立栈。需求设立栈。需求设立栈。 (1) 算法思想算法思想86 由由于于线线索索化化的的本本质质是是将将二二叉叉链链表表中中的的空空指指针针改改为为指指向向

165、前前驱驱或或后后继继线线索索，而而前前驱驱或或后后继继的的信信息息只只需需在在遍遍历历时时才才干干得得到到，因因此此线线索索化化的的过过程程即即为为在在遍遍历历的的过过程程中修正空指针的过程。中修正空指针的过程。 为为了了记记下下遍遍历历过过程程中中访访问问结结点点的的先先后后关关系系，需需求求附附设设指指针针 pre 一一直直指指向向刚刚刚刚访访问问过过的的结结点点，假假设设指指针针 p 指向当前访问的结点，那么指向当前访问的结点，那么 pre 指向它的前驱。指向它的前驱。 先线索化以先线索化以 root 为根的二叉树，为根的二叉树， 后线索化头结点。后线索化头结点。 5. 5. 二叉树的线

166、索化二叉树的线索化二叉树的线索化二叉树的线索化876.5 树和森林与二叉树的转换树和森林与二叉树的转换树与二叉树的转换树与二叉树的转换森林与二叉树的转换森林与二叉树的转换树和森林的遍历树和森林的遍历 由由由由于于于于树树树树和和和和二二二二叉叉叉叉树树树树都都都都可可可可以以以以运运运运用用用用二二二二叉叉叉叉链链链链表表表表作作作作为为为为存存存存储储储储构构构构造造造造，因因因因此此此此可可可可以以以以用用用用二二二二叉叉叉叉链链链链表表表表作作作作为为为为媒媒媒媒介介介介导导导导出出出出树树树树与与与与二二二二叉叉叉叉树树树树之之之之间间间间的的的的一一一一个个个个对对对对应应应应关关关

167、关系系系系。也也也也就就就就是是是是说说说说，给给给给定定定定一一一一棵棵棵棵树树树树，可可可可以以以以找找找找到到到到独独独独一一一一的的的的一一一一棵棵棵棵二二二二叉叉叉叉树树树树与与与与之之之之对对对对应应应应，从从从从物物物物理理理理构构构构造造造造来来来来看看看看，它它它它们的二叉链表是一样的，只是解释不同而已。们的二叉链表是一样的，只是解释不同而已。们的二叉链表是一样的，只是解释不同而已。们的二叉链表是一样的，只是解释不同而已。886.5.1 树与二叉树的转换树与二叉树的转换 1. 1. 树转换为二叉树树转换为二叉树树转换为二叉树树转换为二叉树 树转换为二叉树的可以按照如下步骤进展

168、：树转换为二叉树的可以按照如下步骤进展：树转换为二叉树的可以按照如下步骤进展：树转换为二叉树的可以按照如下步骤进展：89 加线：在各兄弟结点之间加一连线；加线：在各兄弟结点之间加一连线；加线：在各兄弟结点之间加一连线；加线：在各兄弟结点之间加一连线； 除除除除线线线线：对对对对任任任任何何何何结结结结点点点点，除除除除了了了了其其其其最最最最左左左左边边边边的的的的孩孩孩孩子子子子之之之之外外外外，去掉该结点与其他孩子的各枝；去掉该结点与其他孩子的各枝；去掉该结点与其他孩子的各枝；去掉该结点与其他孩子的各枝； 旋旋旋旋转转转转：将将将将添添添添加加加加的的的的程程程程度度度度连连连连线线线线和

169、和和和原原原原有有有有的的的的连连连连线线线线，以以以以树树树树的根结点为轴心，按顺时针方向旋转的根结点为轴心，按顺时针方向旋转的根结点为轴心，按顺时针方向旋转的根结点为轴心，按顺时针方向旋转 45 45。 2. 2. 二叉树复原为树二叉树复原为树二叉树复原为树二叉树复原为树 二叉树复原为树可以按照如下步骤进展：二叉树复原为树可以按照如下步骤进展：二叉树复原为树可以按照如下步骤进展：二叉树复原为树可以按照如下步骤进展：90 加加线线：假假设设 p 结结点点是是双双亲亲的的左左孩孩子子，那那么么将将 p 结结点点的的右右孩孩子子，右右孩孩子子的的右右孩孩子子，沿沿着着右右分分支支搜搜索索到的一切

170、右孩子，都分别与到的一切右孩子，都分别与 p 结点的双亲用线连起来；结点的双亲用线连起来； 除除线线：去去除除原原二二叉叉树树中中一一切切双双亲亲结结点点与与右右孩孩子子的的连线；连线； 旋旋转转：以以树树的的根根结结点点为为轴轴心心，按按逆逆时时针针方方向向旋旋转转 45。 从从从从树树树树与与与与二二二二叉叉叉叉树树树树的的的的转转转转换换换换中中中中可可可可知知知知，转转转转换换换换之之之之后后后后的的的的二二二二叉叉叉叉树树树树的的的的根根根根结结结结点点点点没没没没有有有有右右右右孩孩孩孩子子子子，假假假假设设设设把把把把森森森森林林林林中中中中的的的的第第第第二二二二棵棵棵棵树树树

171、树的的的的根根根根结结结结点点点点看看看看成成成成是是是是第第第第一一一一棵棵棵棵树树树树的的的的根根根根结结结结点点点点的的的的兄兄兄兄弟弟弟弟，那那那那么么么么同同同同样样样样可可可可以以以以导出森林和二叉树的对应关系。导出森林和二叉树的对应关系。导出森林和二叉树的对应关系。导出森林和二叉树的对应关系。916.5.2 森林与二叉树的转换森林与二叉树的转换 1. 1. 森林转换为二叉树森林转换为二叉树森林转换为二叉树森林转换为二叉树 森林转换为二叉树可以按照如下步骤进展：森林转换为二叉树可以按照如下步骤进展：森林转换为二叉树可以按照如下步骤进展：森林转换为二叉树可以按照如下步骤进展：92 转

172、换：将森林中的每一棵树转换成二叉树；转换：将森林中的每一棵树转换成二叉树；转换：将森林中的每一棵树转换成二叉树；转换：将森林中的每一棵树转换成二叉树； 连线：将各棵转换后的二叉树的根结点相连；连线：将各棵转换后的二叉树的根结点相连；连线：将各棵转换后的二叉树的根结点相连；连线：将各棵转换后的二叉树的根结点相连； 旋旋旋旋转转转转：将将将将添添添添加加加加的的的的程程程程度度度度连连连连线线线线和和和和原原原原有有有有的的的的连连连连线线线线以以以以第第第第一一一一棵棵棵棵树根结点为轴心，按顺时针方向粗略地旋转树根结点为轴心，按顺时针方向粗略地旋转树根结点为轴心，按顺时针方向粗略地旋转树根结点为

173、轴心，按顺时针方向粗略地旋转 45 45。A AB BD DC CE EF FG GHHI IJ JA AB BC CD DE EF FG GHHI IJ JA AB BE EC CD DF FG GHHI IJ J93转转转转 换换换换连连连连 线线线线旋旋旋旋 转转转转 经经经经过过过过这这这这种种种种方方方方法法法法转转转转换换换换所所所所对对对对应应应应的的的的二二二二叉叉叉叉树树树树是是是是独独独独一一一一的的的的，且且且且其其其其第第第第一一一一棵棵棵棵树树树树的的的的子子子子树树树树森森森森林林林林转转转转换换换换成成成成二二二二叉叉叉叉树树树树的的的的左左左左子子子子树树树树，

174、剩剩剩剩余余余余树树树树的的的的森林转换成二叉树的右子树。森林转换成二叉树的右子树。森林转换成二叉树的右子树。森林转换成二叉树的右子树。94 2. 2. 二叉树复原为森林二叉树复原为森林二叉树复原为森林二叉树复原为森林 二叉树复原为森林可以按照如下步骤进展：二叉树复原为森林可以按照如下步骤进展：二叉树复原为森林可以按照如下步骤进展：二叉树复原为森林可以按照如下步骤进展： 抹抹线线：抹抹掉掉二二叉叉树树根根结结点点右右链链上上一一切切结结点点上上的的连连线，分成假设干个以右链上结点为根结点的子二叉树；线，分成假设干个以右链上结点为根结点的子二叉树； 转换：将分好的子二叉树转换成树；转换：将分好的

175、子二叉树转换成树； 调整：将转换好的树的根结点陈列成一排。调整：将转换好的树的根结点陈列成一排。 1. 1. 树的遍历树的遍历树的遍历树的遍历95 先先先先根根根根遍遍遍遍历历历历：假假假假设设设设树树树树非非非非空空空空，那那那那么么么么先先先先访访访访问问问问树树树树的的的的根根根根结结结结点点点点，然后依次先根遍历根的每棵子树。然后依次先根遍历根的每棵子树。然后依次先根遍历根的每棵子树。然后依次先根遍历根的每棵子树。 后后后后根根根根遍遍遍遍历历历历：假假假假设设设设树树树树非非非非空空空空，那那那那么么么么先先先先依依依依次次次次后后后后根根根根遍遍遍遍历历历历根根根根的的的的每棵子树

176、，然后访问树的根结点。每棵子树，然后访问树的根结点。每棵子树，然后访问树的根结点。每棵子树，然后访问树的根结点。 层层层层次次次次遍遍遍遍历历历历：假假假假设设设设树树树树非非非非空空空空，那那那那么么么么从从从从树树树树的的的的根根根根结结结结点点点点起起起起按按按按层层层层从左到右依次访问各结点。从左到右依次访问各结点。从左到右依次访问各结点。从左到右依次访问各结点。 6.5.3 树和森林的遍历树和森林的遍历96 2. 2. 森林的遍历森林的遍历森林的遍历森林的遍历 先先先先序序序序遍遍遍遍历历历历：假假假假设设设设森森森森林林林林非非非非空空空空，那那那那么么么么：访访访访问问问问森森森

177、森林林林林中中中中第第第第一一一一棵棵棵棵树树树树根根根根结结结结点点点点；先先先先序序序序遍遍遍遍历历历历第第第第一一一一棵棵棵棵树树树树中中中中根根根根结结结结点点点点的的的的子子子子树树树树森森森森林林林林；先序遍历除去第一棵树后剩余的树构成的森林。先序遍历除去第一棵树后剩余的树构成的森林。先序遍历除去第一棵树后剩余的树构成的森林。先序遍历除去第一棵树后剩余的树构成的森林。 中中中中序序序序遍遍遍遍历历历历：假假假假设设设设森森森森林林林林非非非非空空空空，那那那那么么么么：中中中中序序序序遍遍遍遍历历历历第第第第一一一一棵棵棵棵树树树树中中中中根根根根结结结结点点点点的的的的子子子子树

178、树树树森森森森林林林林；访访访访问问问问森森森森林林林林中中中中第第第第一一一一棵棵棵棵树树树树根根根根结结结结点点点点；中序遍历除去第一棵树后剩余的树构成的森林。中序遍历除去第一棵树后剩余的树构成的森林。中序遍历除去第一棵树后剩余的树构成的森林。中序遍历除去第一棵树后剩余的树构成的森林。 层层层层次次次次遍遍遍遍历历历历：假假假假设设设设森森森森林林林林非非非非空空空空，那那那那么么么么：对对对对第第第第一一一一棵棵棵棵树树树树从从从从根根根根结结结结点点点点起起起起按按按按层层层层从从从从左左左左到到到到右右右右依依依依次次次次访访访访问问问问结结结结点点点点；按按按按层层层层访访访访问问

179、问问森森森森林林林林中中中中除除除除第一棵树外剩余的树构成的森林。第一棵树外剩余的树构成的森林。第一棵树外剩余的树构成的森林。第一棵树外剩余的树构成的森林。A AB BD DC CE EF FG GHHI IJ JA AB BE EC CD 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森林的先

180、序序列对森林的先序序列对应转换之后二叉树应转换之后二叉树的先序序列。的先序序列。 赫赫赫赫夫夫夫夫曼曼曼曼 (Huffman) (Huffman) 树树树树，又又又又称称称称最最最最优优优优二二二二叉叉叉叉树树树树，它它它它是是是是 n n 个个个个带带带带权权权权叶叶叶叶子子子子结结结结点点点点构构构构成成成成的的的的一一一一切切切切二二二二叉叉叉叉树树树树中中中中，带带带带权权权权途途途途径径径径长长长长度度度度最最最最短短短短的的的的二二二二叉叉叉叉树树树树，有有有有着着着着广广广广泛泛泛泛的的的的运运运运用用用用。由由由由于于于于构构构构造造造造这这这这种种种种树树树树的的的的算算算算

181、法法法法最最最最早早早早由由由由赫赫赫赫夫夫夫夫曼曼曼曼 (Huffman) (Huffman) 于于于于 1952 1952 年年年年提提提提出出出出的的的的，所所所所以以以以被称为赫夫曼树。被称为赫夫曼树。被称为赫夫曼树。被称为赫夫曼树。986.6 赫夫曼树及其运用赫夫曼树及其运用根本概念根本概念99赫夫曼算法赫夫曼算法赫夫曼编码赫夫曼编码赫夫曼树和赫夫曼编码的存储表示赫夫曼树和赫夫曼编码的存储表示赫夫曼编码的算法赫夫曼编码的算法例如例如100 在在在在赫赫赫赫夫夫夫夫曼曼曼曼树树树树及及及及其其其其运运运运用用用用中中中中经经经经常常常常会会会会用用用用到到到到一一一一些些些些根根根根本

182、本本本术术术术语语语语。例如：例如：例如：例如：途径途径途径途径途径长度途径长度途径长度途径长度树的途径长度树的途径长度树的途径长度树的途径长度结点的带权途径长度结点的带权途径长度结点的带权途径长度结点的带权途径长度树的带权途径长度树的带权途径长度树的带权途径长度树的带权途径长度赫夫曼树赫夫曼树赫夫曼树赫夫曼树6.6.1 根本概念根本概念101c cd da ab b7 75 54 42 2 途途途途径径径径：从从从从树树树树中中中中一一一一个个个个结结结结点点点点到到到到另另另另一一一一个个个个结结结结点点点点之之之之间间间间的分支构成两个结点之间的途径。的分支构成两个结点之间的途径。的分支

183、构成两个结点之间的途径。的分支构成两个结点之间的途径。途径长度：途径上的分支数目称为途径长度途径长度：途径上的分支数目称为途径长度途径长度：途径上的分支数目称为途径长度途径长度：途径上的分支数目称为途径长度 树树树树的的的的途途途途径径径径长长长长度度度度：从从从从树树树树根根根根到到到到每每每每一一一一个个个个结结结结点点点点的的的的途途途途径径径径长长长长度度度度之之之之和和和和称称称称为为为为树的途径长度。完全二叉树就是这种途径长度最短的二叉树。树的途径长度。完全二叉树就是这种途径长度最短的二叉树。树的途径长度。完全二叉树就是这种途径长度最短的二叉树。树的途径长度。完全二叉树就是这种途径

184、长度最短的二叉树。 结结结结点点点点的的的的带带带带权权权权途途途途径径径径长长长长度度度度：从从从从该该该该结结结结点点点点到到到到树树树树根根根根之之之之间间间间的的的的途途途途径径径径长长长长度度度度与与与与结点上权的乘积称为结点的带权途径长度。结点上权的乘积称为结点的带权途径长度。结点上权的乘积称为结点的带权途径长度。结点上权的乘积称为结点的带权途径长度。a a7 7例如：结点例如：结点例如：结点例如：结点 a a 的带权途径长度为途径长度的带权途径长度为途径长度的带权途径长度为途径长度的带权途径长度为途径长度 3 3结点权值结点权值结点权值结点权值 7 = 21 7 = 21 树树树

185、树的的的的带带带带权权权权途途途途径径径径长长长长度度度度：树树树树中中中中一一一一切切切切叶叶叶叶子子子子结结结结点点点点的的的的带带带带权权权权途途途途径径径径长长长长度度度度之之之之和称为树的带权途径长度。通常记作和称为树的带权途径长度。通常记作和称为树的带权途径长度。通常记作和称为树的带权途径长度。通常记作 例如：此树的带权途径长度为例如：此树的带权途径长度为例如：此树的带权途径长度为例如：此树的带权途径长度为24243737353512 = 4612 = 46 赫夫曼树的定义：赫夫曼树的定义：赫夫曼树的定义：赫夫曼树的定义： 假假假假设设设设有有有有 n n 个个个个权权权权值值值值

186、 w1, w1, w2, w2, , , wn wn ，构构构构造造造造一一一一棵棵棵棵有有有有 n n 个个个个叶叶叶叶子子子子结结结结点点点点的的的的二二二二叉叉叉叉树树树树，每每每每个个个个叶叶叶叶子子子子结结结结点点点点带带带带权权权权为为为为 wi wi ，那那那那么么么么其其其其中中中中带带带带权权权权途途途途径径径径长长长长度度度度 WPL WPL 最最最最小小小小的的的的二二二二叉叉叉叉树树树树称称称称为为为为最最最最优优优优二二二二叉叉叉叉树或赫夫曼树。树或赫夫曼树。树或赫夫曼树。树或赫夫曼树。102a ab bc cd d7 75 52 24 4c cd da ab b7

187、75 54 42 2a ab bc cd d7 75 52 24 4 图图图图 (a) (a) 的带权途径长度为的带权途径长度为的带权途径长度为的带权途径长度为 WPL = 72 WPL = 725252222242 = 3642 = 36(a(a) )(b(b) )(c(c) ) 图图图图 (b) (b) 的带权途径长度为的带权途径长度为的带权途径长度为的带权途径长度为 WPL = 73 WPL = 735353212142 = 4642 = 46 图图图图 (c) (c) 的带权途径长度为的带权途径长度为的带权途径长度为的带权途径长度为 WPL = 71 WPL = 71525223234

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

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

190、n 个个个个权权权权值值值值 w1, w1, w2, w2, , , wn wn ，构构构构成成成成 n n 棵棵棵棵二二二二叉叉叉叉树树树树的的的的集集集集合合合合 F F = = T1, T1, T2, T2, , , Tn Tn ，其其其其中中中中每每每每棵棵棵棵二二二二叉叉叉叉树树树树 Ti Ti 中中中中只只只只需需需需一一一一个个个个带带带带权权权权 wi wi 的的的的根根根根结结结结点点点点，其其其其左左左左子子子子树树树树和和和和右右右右子树均为空。子树均为空。子树均为空。子树均为空。6.6.2 赫夫曼算法赫夫曼算法 在在在在 F F 中中中中选选选选取取取取两两两两棵棵棵棵

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

192、两两两棵棵棵棵根根根根结结结结点点点点权权权权值值值值最小的二叉树，同时将新得到的二叉树参与最小的二叉树，同时将新得到的二叉树参与最小的二叉树，同时将新得到的二叉树参与最小的二叉树，同时将新得到的二叉树参与 F F 中。中。中。中。 反反反反复复复复和和和和 ，直直直直到到到到 F F 中中中中只只只只含含含含一一一一棵棵棵棵树树树树为为为为止止止止。这这这这棵树便是赫夫曼树。棵树便是赫夫曼树。棵树便是赫夫曼树。棵树便是赫夫曼树。6.5.2 哈夫曼树的构造哈夫曼树的构造举例：5，11，26，18，34，15，6构成一棵哈夫曼树6 5111518263411223348771256.5.2 哈夫

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

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

195、两棵树根双亲为树根双亲为0进展合并，构造一棵新的树产生进展合并，构造一棵新的树产生新的结点，该树的根结点权值为所选的两棵树的新的结点，该树的根结点权值为所选的两棵树的权值之和，且左右孩子分别为上述所选的两棵树，权值之和，且左右孩子分别为上述所选的两棵树，即所选出的两棵树的双亲为新构造的结点。构造出即所选出的两棵树的双亲为新构造的结点。构造出来的新结点依次存放在第来的新结点依次存放在第n+1到第到第m的单元上。的单元上。 哈夫曼树的构造哈夫曼树的构造void CrtHuffmanTree(HuffmanTree ht, int w , int n) / 第一步：对初始形状的设置。第一步：对初始形

196、状的设置。 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 InsertBSTBSTree *bst , DataType e)/*假设在二叉排序树假设在二叉排序树bst中不存在关键字等于中不存在关键字等于key的元的元素，插入该元素素，插入该元素*/else if(keykey) Insert

197、BST(&(*(bst)-Lchild),key); void InsertBSTBSTree *bst , DataType e)/*假设在二叉排序树假设在二叉排序树bst中不存在关键字等于中不存在关键字等于key的元的元素，插入该元素素，插入该元素*/else if(keykey) InsertBST(&(*(bst)-Lchild),key); else if(key(*bst)-key) InsertBST(&(*(bst)-Rchild),key); 二叉排序树创建算法描画：二叉排序树创建算法描画：void CreateBSTBSTree *bst)/*从键盘输入元素的值，创建相应的

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

199、入 键盘输入元素值键盘输入元素值key; 练习：练习： 设关键字的输入顺序为：设关键字的输入顺序为：12，24，28，53，90，45，画出所生成的二叉排序树。，画出所生成的二叉排序树。 二叉排序树查找二叉排序树查找算法思想：算法思想：首先将待查关键字与根结点关键字首先将待查关键字与根结点关键字t进展比较，进展比较，假设：假设： 1key=t: 那么前往根结点地址；那么前往根结点地址； 2keyt: 那么进一步查找右子树；那么进一步查找右子树； 算法实现递归算法实现递归BSTree SearchBST(BSTree bst , KeyType key) if(!bst) return NULL

200、; else if(bst-key=t)return bst; /假设查找胜利，那么前往假设查找胜利，那么前往 else if(bst-keykey ) return SearchBST(bst-Lchild , key); else return SearchBST(bst-Rchild , key);二叉排序树的删除二叉排序树的删除从二叉排序树中删除一个结点，要保证删除后的二叉树还是一棵二从二叉排序树中删除一个结点，要保证删除后的二叉树还是一棵二叉排序树。叉排序树。算法思想：首先查找要删除结点，假设查找失败，那么不作任何删算法思想：首先查找要删除结点，假设查找失败，那么不作任何删除操作，否

201、那么，假设要删除的结点为除操作，否那么，假设要删除的结点为p，其双亲结点为，其双亲结点为f，并假设，并假设p是是f的左孩子右孩子情况类似，那么删除过程分为三种情况讨的左孩子右孩子情况类似，那么删除过程分为三种情况讨论：论：1假设假设p为叶子结点，那么直接删除该结点，其双亲的左孩子为为叶子结点，那么直接删除该结点，其双亲的左孩子为空：空： f-Lchild=NULL;free(p);2假设假设p为单分支结点，即为单分支结点，即p只需左子树，或者只需右子树，那只需左子树，或者只需右子树，那么可将么可将p的左子树或者右子树直接改为其双亲结点的左子树或者右子树直接改为其双亲结点f的左子树：的左子树：

202、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结点在中序遍历序列中的直接前驱结点在中序遍历序列中的直接前驱s，然后用，然

203、后用s结点替结点替代代p结点的值，再将结点的值，再将s结点删除，原结点删除，原s结点的左子树改为其双亲结点结点的左子树改为其双亲结点假设为假设为q的右子树：的右子树：p-key=s-key ; q-Rchild=s-Lchild; free(s);上述的两种方法中还可以将寻觅上述的两种方法中还可以将寻觅p结点的中序遍历前驱改成寻觅中结点的中序遍历前驱改成寻觅中序遍历后继，请同窗们思索一下。序遍历后继，请同窗们思索一下。二叉排序树的删除算法描画二叉排序树的删除算法描画BSTNode * DelBST(BSTree t , KeyType k)BSTNode *p , *q , *f , *s ;

204、 /*查找关键字为查找关键字为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-Rchild=NULL) /p是叶子结点是叶子结点 if(f=NULL)t=f

205、; 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的右子树作为的右子树作为f的左子树的左子树 else f-Rchild=p-Rchild

206、 ; /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=p-Lchild; while(s-Rchild) q=s ; s=s-

207、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平衡二叉排序树平衡二叉排序树平衡二叉排序树又称为平衡二叉排序树又称为AV树。其定义

208、如下：树。其定义如下：一棵平衡二叉排序树一棵平衡二叉排序树 或者是空树，或者是具有如下性质的二叉排序或者是空树，或者是具有如下性质的二叉排序树：树：(1)左子树与右子树的深度之差平衡因子左子树与右子树的深度之差平衡因子Balance Factor的绝的绝对值小于等于对值小于等于1；(2) 左右子树都是平衡二叉树。左右子树都是平衡二叉树。45245312289000000-1452453122890720000-1-2-1综合设计：二叉排序树的综合运用综合设计：二叉排序树的综合运用实验描画：随机产生100个数，用二叉排序树和任选一种内排序方法进展排序，并对二种算法进展比较。实验要求：输入：要求产生的随机数先写入文本数据文件input.txt中，如没有数据文件input.txt,那么先创建数据文件input.txt，之后每次产生的100个随机数均追加到文件input.txt中。输出：1从文件input中顺序读出100个数，生成二叉排序树，并对二叉排序树进展中序遍历输出到文件output1.txt中，并从屏幕输出；2从文件input中读出一样的数据到数组中，用采用一种内部排序进展排序，输出到文件output2.txt中，并从屏幕输出。对上述算法进展分析，给出和两种算法的优劣比较。所涉及的数据构造：顺序表、二叉链表、文件等。所涉及的算法：二叉排序树生成和遍历，排序算法等。