数据结构与算法 (6).pdf

《数据结构与算法 (6).pdf》由会员分享，可在线阅读，更多相关《数据结构与算法 (6).pdf（128页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构与算法Data Structure And Algorithms第6章树和二叉树树的定义和基本结构二叉树遍历二叉树和线索二叉树树和森林树与等价问题赫夫曼树及其应用回溯法与树的遍历树的计数树型结构是一类非常重要的非线性结构。直观地，树型结构是一类非常重要的非线性结构。直观地，树型结构是树型结构是以分支关系定义的层次结构以分支关系定义的层次结构。树在计算机领域中也有着广泛的应用，例如在编译树在计算机领域中也有着广泛的应用，例如在编译程序中，用树来表示源程序的语法结构；在数据库系统程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织信息；在分析算法的行为时，可用树中，可用树来组织

2、信息；在分析算法的行为时，可用树来描述其执行过程等等。来描述其执行过程等等。本章将详细讨论树和二叉树数据结构，主要介绍树本章将详细讨论树和二叉树数据结构，主要介绍树和二叉树的概念、术语，二叉树的遍历算法。树和二叉和二叉树的概念、术语，二叉树的遍历算法。树和二叉树的各种存储结构以及建立在各种存储结构上的操作及树的各种存储结构以及建立在各种存储结构上的操作及应用等。应用等。第6章树和二叉树6.1 树的基本概念树的基本概念1 树的定义树的定义树树(Tree)是是n(n0)个结点的有限集合个结点的有限集合T，若，若n=0时称时称为空树，否则：为空树，否则：有且只有一个特殊的称为树的根有且只有一个特殊的

3、称为树的根(Root)结点；结点；若若n1时，其余的结点被分为时，其余的结点被分为m(m0)个个互不相交互不相交的子集的子集T1,T2,T3Tm，其中每个子集本身又是一棵，其中每个子集本身又是一棵树，称其为根的子树树，称其为根的子树(Subtree)。这是树的递归定义，即用树来定义树，而只有一个这是树的递归定义，即用树来定义树，而只有一个结点的树必定仅由根组成，如图结点的树必定仅由根组成，如图6-1(a)所示。所示。6.1.1树的定义和基本术语树的定义和基本术语2 树的基本术语树的基本术语 结点结点(node)：一个数据元素及其若干指向其子一个数据元素及其若干指向其子树的分支。树的分支。结点的

4、度结点的度(degree)、树的度树的度：结点所拥有的结点所拥有的子树的棵数称为子树的棵数称为结点的度结点的度。树中结点度的最大值称为。树中结点度的最大值称为树的度树的度。图图6-1树的示树的示例形式例形式AABDCEGFHIMJNKL(a)只有根结点只有根结点(b)一般的树一般的树如图如图6-1(b)中结点中结点A的度是的度是3，结点，结点B的度是的度是2，结点，结点M的度是的度是0，树的度是，树的度是3。叶子叶子(left)结点结点、非叶子结点非叶子结点：树中树中度为度为0的的结点称为结点称为叶子结点叶子结点(或终端结点或终端结点)。相对应地，。相对应地，度不为度不为0的的结点称为结点称为

5、非叶子结点非叶子结点(或非终端结点或分支结点或非终端结点或分支结点)。除根结点外，分支结点又称为内部结点。除根结点外，分支结点又称为内部结点。如图如图6-1(b)中结点中结点H、I、J、K、L、M、N是叶子是叶子结点，而所有其它结点都是分支结点。结点，而所有其它结点都是分支结点。孩子结点孩子结点、双亲结点双亲结点、兄弟结点兄弟结点一个结点的一个结点的子树的根子树的根称为该结点的孩子结点称为该结点的孩子结点(child)或子结点或子结点；相应地，该结点是其孩子结点的双亲结点相应地，该结点是其孩子结点的双亲结点(parent)或父结点。或父结点。如图如图6-1(b)中结点中结点B、C、D是结点是结

6、点A的子结点的子结点，而，而结点结点A是是结点结点B、C、D的的父结点父结点；类似地结点类似地结点E、F是是结点结点B的子结点的子结点，结点，结点B是是结点结点E、F的的父结点。父结点。同一双亲结点的所有子结点互称为同一双亲结点的所有子结点互称为兄弟结点兄弟结点。如图如图6-1(b)中结点中结点B、C、D是兄弟结点；结点是兄弟结点；结点E、F是兄弟结点。是兄弟结点。层次层次、堂兄弟结点堂兄弟结点规定树中根结点的层次为规定树中根结点的层次为1，其余结点的层次等于，其余结点的层次等于其双亲结点的层次加其双亲结点的层次加1。若某结点在第若某结点在第l(l1)层，则其子结点在第层，则其子结点在第l+1

7、层。层。双亲结点在同一层上的所有结点互称为双亲结点在同一层上的所有结点互称为堂兄弟结点堂兄弟结点。如图如图6-1(b)中结点中结点E、F、G、H、I、J。结点的层次路径结点的层次路径、祖先祖先、子孙子孙从根结点开始，到达某结点从根结点开始，到达某结点p所经过的所有结点成所经过的所有结点成为为结点结点p的的层次路径层次路径(有且只有一条有且只有一条)。结点结点p的层次路径上的所有结点（的层次路径上的所有结点（p除外）称为除外）称为p的的祖先祖先(ancester)。以某一结点为根的子树中的任意结点称为该结点的以某一结点为根的子树中的任意结点称为该结点的子孙结点子孙结点(descent)。树的深度

8、树的深度(depth)：树中结点的最大层次值，又树中结点的最大层次值，又称为树的高度，如图称为树的高度，如图6-1(b)中树的高度为中树的高度为4。有序树和无序树有序树和无序树：对于一棵树，若其中每一个对于一棵树，若其中每一个结点的子树（若有）具有一定的次序，则该树称为结点的子树（若有）具有一定的次序，则该树称为有有序树序树，否则称为，否则称为无序树无序树。森林森林(forest)：是是m(m0)棵互不相交的棵互不相交的树的集树的集合。显然，若将一棵树的根结点删除，剩余的子树就合。显然，若将一棵树的根结点删除，剩余的子树就构成了森林。构成了森林。3 树的表示形式树的表示形式 倒悬树倒悬树。是最

9、常用的表示形式，如图是最常用的表示形式，如图6-1(b)。嵌套集合嵌套集合。是一些集合的集体，对于任何两个是一些集合的集体，对于任何两个集合，或者不相交，或者一个集合包含另一个集合。集合，或者不相交，或者一个集合包含另一个集合。图图6-2(a)是图是图6-1(b)树的嵌套集合形式。树的嵌套集合形式。广义表形式广义表形式。图图6-2(b)是树的广义表形式。是树的广义表形式。树的表示方法的多样化说明了树结构的重要性树的表示方法的多样化说明了树结构的重要性。图图6-2树的表示树的表示形式形式(a)嵌套集合嵌套集合形式形式(b)广义表广义表形式形式(A(B(E(K,L),F),C(G(M,N),D(H

10、,I,J)HIJDFBKLECMNGA6.1.2树的抽象数据类型定义树的抽象数据类型定义ADT Tree数据对象数据对象D：D是具有相同数据类型的数据元素的集是具有相同数据类型的数据元素的集合合。数据关系数据关系R：若：若D为空集为空集，则称为空树则称为空树；基本操作：基本操作：ADT Tree（详见教材（详见教材 Page 118-119）6.2二叉树二叉树6.2.1 二叉树的定义二叉树的定义1二叉树的定义二叉树的定义二叉树二叉树(Binary tree)是是n(n0)个结点的有限集合。若个结点的有限集合。若n=0时称为空树，否则：时称为空树，否则：有且只有一个特殊的称为树的根有且只有一个特

11、殊的称为树的根(Root)结点；结点；若若n1时，其余的结点被分成为时，其余的结点被分成为二个互不相交二个互不相交的的子集子集T1,T2，分别称之为左，分别称之为左、右子树，并且左右子树，并且左、右子树又都是二叉树。右子树又都是二叉树。由此可知，二叉树的由此可知，二叉树的定义是递归定义是递归的。的。二叉树在树结构中起着非常重要的作用。因为二叉二叉树在树结构中起着非常重要的作用。因为二叉树结构简单，存储效率高，树的操作算法相对简单，且树结构简单，存储效率高，树的操作算法相对简单，且任何树都很容易转化成二叉树结构任何树都很容易转化成二叉树结构。上节中引入的有关。上节中引入的有关树的术语也都适用于二

12、叉树。树的术语也都适用于二叉树。2二叉树的基本形态二叉树的基本形态二叉树有二叉树有5种基本形态，如图种基本形态，如图6-3所示。所示。AAAA(a)(b)(c)(d)(e)(a)空空二叉树二叉树(b)单结点单结点二叉树二叉树(c)右子树为空右子树为空(d)左子树为空左子树为空(e)左左、右子树都不空右子树都不空图图6-3二叉二叉树的基本树的基本形态形态6.2.2 6.2.2 二叉树的性质二叉树的性质性质性质1：在非空二叉树中，第在非空二叉树中，第i i层上至多有层上至多有2i-1个结点个结点(i1)。证明证明：用数学归纳法证明。用数学归纳法证明。当当i=1时：只有一个根结点，时：只有一个根结点

13、，21-1=20=1，命题成立。，命题成立。现假设对现假设对i1时，处在第时，处在第i-1层上至多有层上至多有2(i-1)-1个结点。个结点。由归纳假设知，第由归纳假设知，第i-1层上至多有层上至多有2i-2个结点。由于二个结点。由于二叉树每个结点的度最大为叉树每个结点的度最大为2，故在第，故在第i i层上最大结点数为层上最大结点数为第第i-1层上最大结点数的层上最大结点数的2倍。倍。即即22i-22i-1证毕证毕性质性质2：深度为深度为k的二叉树至多有的二叉树至多有2k-1个结点个结点（k1)。证明证明：深度为深度为k的二叉树的最大的结点数为二叉树中每的二叉树的最大的结点数为二叉树中每层上的

14、最大结点数之和。层上的最大结点数之和。由性质由性质1知知，二叉树的第，二叉树的第1层层、第第2层层 第第k层上的结层上的结点数至多有：点数至多有：20、21 2k-1。总的总的结点数至多有：结点数至多有：20+21+2k-1=2k-1 证毕证毕性质性质3：对任何一棵二叉树，若其叶子结点数为对任何一棵二叉树，若其叶子结点数为n0，度，度为为2的结点数为的结点数为n2，则，则n0=n2+1。证明：证明：设二叉树中度为设二叉树中度为1的结点数为的结点数为n1，二叉树中总结，二叉树中总结点数为点数为N，因为二叉树中所有结点均小于或等于，因为二叉树中所有结点均小于或等于2，则，则有：有：N=n0+n1+

15、n2再看二叉树中的分支数：再看二叉树中的分支数：除根结点外，其余每个结点都有唯一的一个进入分除根结点外，其余每个结点都有唯一的一个进入分支，而所有这些分支都是由度为支，而所有这些分支都是由度为1和和2的结点射出的。设的结点射出的。设B为二叉树中的分支总数，则有：为二叉树中的分支总数，则有：N=B+1Bn1+2 n2N=B+1=n1+2 n2+1n0+n1+n2=n1+2 n2+1即即n0=n2+1 证毕证毕满二叉树和完全二叉树满二叉树和完全二叉树一棵深度为一棵深度为k且有且有2k-1个结点的二叉树称为个结点的二叉树称为满二叉满二叉树树(Full Binary Tree)。如图如图6-4(a)就

16、是一棵深度为就是一棵深度为4的满二叉树。的满二叉树。894101151213614157213894101152112673(a)满二叉树满二叉树(b)完全二叉树完全二叉树1362455674213(c)非完全二叉树非完全二叉树图图6-4 特殊形态的特殊形态的二叉二叉树树满二叉树的特点满二叉树的特点：基本特点是每一层上的结点数总是最大结点数。基本特点是每一层上的结点数总是最大结点数。满二叉树的所有的支结点都有左满二叉树的所有的支结点都有左、右子树。右子树。可对满二叉树的结点进行连续编号，若规定从根结点开始，可对满二叉树的结点进行连续编号，若规定从根结点开始，按按“自上而下自上而下、自左至右自左

17、至右”的原则进行。的原则进行。完全二叉树完全二叉树(Complete Binary Tree)：如果深度为：如果深度为k，有，有n个结点的二叉树，当且仅当其每一个结点都与深度为个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从的满二叉树中编号从1到到n的结点一一对应，该二叉树称的结点一一对应，该二叉树称为完全二叉树。为完全二叉树。或深度为或深度为k的满二叉树中编号从的满二叉树中编号从1到到n的前的前n个结点构个结点构成了一棵深度为成了一棵深度为k的完全二叉树。的完全二叉树。其中其中2k-1 n2k-1。完全二叉树是满二叉树的一部分，而满二叉树是完完全二叉树是满二叉树的一部分，而

18、满二叉树是完全二叉树的特例。全二叉树的特例。完全二叉树的特点完全二叉树的特点：若完全二叉树的深度为若完全二叉树的深度为k，则所有的叶子结点都出，则所有的叶子结点都出现在第现在第k k层或层或k-1层。对于任一结点，如果其右子树的最层。对于任一结点，如果其右子树的最大层次为大层次为l，则其左子树的最大层次为，则其左子树的最大层次为l或或l+1 1。性质性质4：n个结点的完全二叉树深度为：个结点的完全二叉树深度为：2n +1 1。其中符号：其中符号：x 表示不大于表示不大于x的最大整数。的最大整数。x 表示不小于表示不小于x的最小整数。的最小整数。证明：证明：假设完全二叉树的深度为假设完全二叉树的

19、深度为k，则根据性质，则根据性质2及完及完全二叉树的定义有：全二叉树的定义有：2k-1-1n2k-1或或2 k-1n2k取对数得：取对数得：k12n1，则其双亲结点编号是，则其双亲结点编号是 i/2 。如果如果2in：则结点：则结点i为叶子结点，无左孩子；否则，为叶子结点，无左孩子；否则，其左孩子结点编号是其左孩子结点编号是2i。如果如果2i+1n：则结点：则结点i无右孩子；否则，其右孩子无右孩子；否则，其右孩子结点编号是结点编号是2i+1。证明证明：用数学归纳法证明。首先证明和，然后用数学归纳法证明。首先证明和，然后由和导出。由和导出。当当i=1时时，由完全二叉树的定义知，结点，由完全二叉树

20、的定义知，结点i的左孩子的左孩子的编号是的编号是2，右孩子的编号是，右孩子的编号是3。若若2n，则二叉树中不存在编号为，则二叉树中不存在编号为2的结点，说明的结点，说明结结点点i的左的左孩子孩子不存在。不存在。若若3n，则二叉树中不存在编号为，则二叉树中不存在编号为3的结点，说明的结点，说明结结点点i的右的右孩子孩子不存在。不存在。现假设对于编号为现假设对于编号为j(1ji)的结点的结点，(2)(2)和和(3)(3)成立。成立。即：即：当当2jn：结点：结点j的左孩子编号是的左孩子编号是2j；当；当2jn时时，结点结点j的左孩子结点不存在。的左孩子结点不存在。当当2j+1n：结点：结点j的右孩

21、子编号是的右孩子编号是2j+1；当；当2j+1n时，结点时，结点j的右孩子结点不存在。的右孩子结点不存在。当当i=j+1时，由完全二叉树的定义知，若结点时，由完全二叉树的定义知，若结点i的左的左孩子结点存在，则其左孩子结点的编号一定等于编号孩子结点存在，则其左孩子结点的编号一定等于编号为为j的右孩子的编号加的右孩子的编号加1，即结点，即结点i的左孩子的编号为：的左孩子的编号为：(2j+1)+1=2(j+1)=2i如图如图6-5所示，且有所示，且有2in。相反，若。相反，若2in，则左孩子结，则左孩子结点不存在。同样地，若结点点不存在。同样地，若结点i的右孩子结点存在，则其的右孩子结点存在，则其

22、右孩子的编号为：右孩子的编号为：2i+1，且有，且有2i+1n。相反，若。相反，若2i+1n，则左孩子结点不存在。结论，则左孩子结点不存在。结论(2)(2)和和(3)(3)得证。得证。再由再由(2)(2)和和(3)(3)来证明来证明(1)。当当i=1时时，显然编号为，显然编号为1的的是根结点，无双亲结点。是根结点，无双亲结点。当当i1时，设编号为时，设编号为i的结点的双亲结点的编号为的结点的双亲结点的编号为m，若编号为若编号为i的结点是其双亲结点的左孩子，则由的结点是其双亲结点的左孩子，则由(2)有：有：i=2m，即，即m=i/2 ；若编号为若编号为i的结点是其的结点是其双亲结点的右孩子，则由

23、双亲结点的右孩子，则由(3)有：有：i=2m+1，即，即m=(i-1)/2 ；当当i1时时，其双亲结点的编号为，其双亲结点的编号为 i/2 。证毕证毕ii+12i2i+12i+22i+3i/2(a)i和和i+1结点在同一层结点在同一层i+12i+22i+3i2i2i+1(b)i和和i+1结点不在同一层结点不在同一层图图6-5 完全完全二叉二叉树中结点树中结点i和和i+1的左右孩子的左右孩子6.2.3二叉树的存储结构二叉树的存储结构1顺序存储结构顺序存储结构二叉树存储结构的类型定义：二叉树存储结构的类型定义：#define MAX_SIZE 100typedef telemtype sqbitr

24、eeMAX_SIZE;用一组地址连续的存储单元依次用一组地址连续的存储单元依次“自上而下自上而下、自左自左至右至右”存储完全二叉树的数据元素。存储完全二叉树的数据元素。对于完全二叉树上编号为对于完全二叉树上编号为i的结点元素存储在一维的结点元素存储在一维数组的下标值为数组的下标值为i-1的分量中的分量中，如图，如图6-6(c)所示。所示。对于一般的二叉树，将其每个结点与完全二叉树上对于一般的二叉树，将其每个结点与完全二叉树上的结点相对照，的结点相对照，存储在一维数组中存储在一维数组中，如图，如图6-6(d)所示。所示。abcdhiejklfg(a)完全二叉树完全二叉树(b)非完全二叉树非完全二

25、叉树abcdefgh1 2 3 4 5 6 7 8 9 10 11 12 a b c d e f g h i j k l(c)完全二叉树的顺序存储形式完全二叉树的顺序存储形式1 2 3 4 5 6 7 8 9 10 11a b c d e h f g(d)非完全二叉树的顺序存储形式非完全二叉树的顺序存储形式图图6-6 二叉二叉树及其树及其顺序存储形式顺序存储形式最坏的情况下，一个深度为最坏的情况下，一个深度为k且只有且只有k个结点的单个结点的单支树需要长度为支树需要长度为2k-1的一维数组的一维数组。2 链式存储结构链式存储结构设计不同的结点结构可构成不同的链式存储结构。设计不同的结点结构可构

26、成不同的链式存储结构。(1)结点的类型及其定义结点的类型及其定义 二叉链表结点二叉链表结点。有三个域：一个数据域，两个分。有三个域：一个数据域，两个分别指向左右子结点的指针域，如图别指向左右子结点的指针域，如图6-7(a)所示。所示。typedef struct BTNode ElemType data;struct BTNode*Lchild,*Rchild;BTNode;三三叉链表结点叉链表结点。除二叉链表的三个域外，再增加一。除二叉链表的三个域外，再增加一个指针域，用来指向结点的父结点，如图个指针域，用来指向结点的父结点，如图6-7(b)所示。所示。typedef struct BTNo

27、de_3 ElemType data;struct BTNode_3 *Lchild,*Rchild,*parent;BTNode_3;Lchild data RchildLchild data parent Rchild(a)二叉链表结点二叉链表结点(b)三三叉链表结点叉链表结点图图6-7 链表结点结构链表结点结构形式形式(2)二叉树的链式存储形式二叉树的链式存储形式例有一棵一般的二叉树，如图例有一棵一般的二叉树，如图6-8(a)所示。以二叉所示。以二叉链表和三叉链表方式存储的结构图分别如图链表和三叉链表方式存储的结构图分别如图6-8(b)、6-8(c)所示。所示。图图6-8 二叉树及其二叉

28、树及其链式存储结构链式存储结构(a)二叉树二叉树afedcbg(c)三三叉链表叉链表a b c d e f g T(b)二二叉链表叉链表a b c d e g f T6.3遍历二叉树及其应用遍历二叉树及其应用遍历二叉树遍历二叉树(Traversing Binary Tree)：是指是指按指定按指定的规律的规律对二叉树中的对二叉树中的每个结点访问一次且仅访问一次每个结点访问一次且仅访问一次。所谓所谓访问访问是指对结点做某种处理。如：输出信息是指对结点做某种处理。如：输出信息、修改结点的值等修改结点的值等。二叉树是一种非线性结构，每个结点都可能有左二叉树是一种非线性结构，每个结点都可能有左、右两棵

29、子树，因此，需要寻找一种规律，使二叉树上的右两棵子树，因此，需要寻找一种规律，使二叉树上的结点能排列在一个线性队列上，从而便于遍历。结点能排列在一个线性队列上，从而便于遍历。二叉树的基本组成：根结点二叉树的基本组成：根结点、左子树左子树、右子树。若右子树。若能依次遍历这三部分，就是遍历了二叉树。能依次遍历这三部分，就是遍历了二叉树。若以若以L、D、R分别表示遍历左子树、遍历根结点和分别表示遍历左子树、遍历根结点和遍历右子树，遍历右子树，则有六种遍历方案：则有六种遍历方案：DLR、LDR、LRD、DRL、RDL、RLD。若规定若规定先左后右先左后右，则只有，则只有前三种前三种情况情况三种情况，分

30、别是：三种情况，分别是：DLR先先(根根)序遍历。序遍历。LDR中中(根根)序遍历。序遍历。LRD后后(根根)序遍历。序遍历。对于二叉树的遍历，分别讨论递归遍历算法和非递对于二叉树的遍历，分别讨论递归遍历算法和非递归遍历算法。递归遍历算法具有非常清晰的结构，但初归遍历算法。递归遍历算法具有非常清晰的结构，但初学者往往难以接受或怀疑，不敢使用。实际上，递归算学者往往难以接受或怀疑，不敢使用。实际上，递归算法是由系统通过使用堆栈来实现控制的。而非递归算法法是由系统通过使用堆栈来实现控制的。而非递归算法中的控制是由设计者定义和使用堆栈来实现的。中的控制是由设计者定义和使用堆栈来实现的。6.3.1先序

31、遍历二叉树先序遍历二叉树1 递归算法递归算法算法的递归定义是：算法的递归定义是：若二叉树为空，则遍历结束；否则若二叉树为空，则遍历结束；否则 访问根结点；访问根结点；先序遍历左子树先序遍历左子树(递归调用本算法递归调用本算法)；先序遍历右子树先序遍历右子树(递归调用本算法递归调用本算法)。先序遍历的递归算法先序遍历的递归算法void PreorderTraverse(BTNode*T)if (T!=NULL)visit(T-data);/*访问根结点访问根结点*/PreorderTraverse(T-Lchild);PreorderTraverse(T-Rchild);说明：说明：visit(

32、)函数是访问结点的数据域，其要求视具体函数是访问结点的数据域，其要求视具体问题而定。树采用二叉链表的存储结构，用指针变量问题而定。树采用二叉链表的存储结构，用指针变量T T来指向。来指向。2 非递归算法非递归算法设设T是指向二叉树根结点的指针变量，非递归算法是：是指向二叉树根结点的指针变量，非递归算法是：若二叉树为空，则返回；否则，令若二叉树为空，则返回；否则，令p=T；访问访问p所指向的结点；所指向的结点；q=p-Rchild，若，若q不为空，则不为空，则q进栈；进栈；p=p-Lchild，若，若p不为空，转不为空，转(1)，否则转，否则转(4)；退栈到退栈到p，转，转(1)，直到栈空为止。

33、，直到栈空为止。算法实现算法实现：#define MAX_NODE 50void PreorderTraverse(BTNode*T)BTNode*StackMAX_NODE,*p=T,*q;int top=0;if (T=NULL)printf(“Binary Tree is Empty!n”);else do visit(p-data);q=p-Rchild;if (q!=NULL)stack+top=q;p=p-Lchild;if(p=NULL)p=stacktop;top-;while(p!=NULL);6.3.2中序遍历二叉树中序遍历二叉树1 递归算法递归算法算法的递归定义是：算法的

34、递归定义是：若二叉树为空，则遍历结束；否则若二叉树为空，则遍历结束；否则 中序遍历左子树中序遍历左子树(递归调用本算法递归调用本算法)；访问根结点；访问根结点；中序遍历右子树中序遍历右子树(递归调用本算法递归调用本算法)。中序遍历的递归算法中序遍历的递归算法void InorderTraverse(BTNode *T)if (T!=NULL)InorderTraverse(T-Lchild);visit(T-data);/*访问根结点访问根结点*/InorderTraverse(T-Rchild);/*图图6-8(a)的二叉树，输出的次序是：的二叉树，输出的次序是：cbegdfa*/2 非递归

35、算法非递归算法设设T是指向二叉树根结点的指针变量，非递归算法是：是指向二叉树根结点的指针变量，非递归算法是：若二叉树为空，则返回；否则，令若二叉树为空，则返回；否则，令p=T 若若p不为空，不为空，p进栈，进栈，p=p-Lchild；否则否则(即即p为空为空)，退栈到，退栈到p，访问，访问p所指向的结点；所指向的结点；p=p-Rchild，转，转(1)；直到栈空为止。直到栈空为止。算法实现算法实现：#define MAX_NODE 50void InorderTraverse(BTNode *T)BTNode *StackMAX_NODE,*p=T;int top=0,bool=1;if (T

36、=NULL)printf(“Binary Tree is Empty!n”);else do while(p!=NULL)stack+top=p;p=p-Lchild;if (top=0)bool=0;else p=stacktop;top-;visit(p-data);p=p-Rchild;while(bool!=0);6.3.3后序遍历二叉树后序遍历二叉树1 递归算法递归算法算法的递归定义是：算法的递归定义是：若二叉树为空，则遍历结束，否则若二叉树为空，则遍历结束，否则 后序遍历左子树后序遍历左子树(递归调用本算法递归调用本算法)；后序遍历右子树后序遍历右子树(递归调用本算法递归调用本算法

37、)；访问根结点访问根结点。后序遍历的递归算法后序遍历的递归算法void PostorderTraverse(BTNode*T)if (T!=NULL)PostorderTraverse(T-Lchild);PostorderTraverse(T-Rchild);visit(T-data);/*访问根结点访问根结点*/*/*图图6-8(a)的二叉树，输出的次序是：的二叉树，输出的次序是：cgefdbacgefdba*/*/遍历二叉树的算法中基本操作是访问结点，因此，遍历二叉树的算法中基本操作是访问结点，因此，无论是哪种次序的遍历，对有无论是哪种次序的遍历，对有n个结点的二叉树，其时个结点的二叉树

38、，其时间复杂度均为间复杂度均为O(n)。如图如图6-9所示的二叉树表示表达式：所示的二叉树表示表达式：(a+b*(c-d)-e/f)按不同的次序遍历此二叉树，将访问的结点按先后次序按不同的次序遍历此二叉树，将访问的结点按先后次序排列起来的次序是：排列起来的次序是：其先序序列为：其先序序列为：-+a*b-cd/ef其中序序列为：其中序序列为：a+b*c-d-e/f其后序序列为：其后序序列为：abcd-*+ef/-/fe-dcb*a+图图6-9 表达式表达式(a+b*(c-d)-e/f)二叉树二叉树2 非递归算法非递归算法在后序遍历中，根结点是最后被访问的。因此，在在后序遍历中，根结点是最后被访问

39、的。因此，在遍历过程中，当搜索指针指向某一根结点时，不能立即遍历过程中，当搜索指针指向某一根结点时，不能立即访问，而要先遍历其左子树，此时访问，而要先遍历其左子树，此时根结点进栈根结点进栈。当其左。当其左子树遍历完后再搜索到该根结点时，还是不能访问，还子树遍历完后再搜索到该根结点时，还是不能访问，还需遍历其右子树。所以，此需遍历其右子树。所以，此根结点还需再次进栈根结点还需再次进栈，当其，当其右子树遍历完后再退栈到到该根结点时，才能被访问。右子树遍历完后再退栈到到该根结点时，才能被访问。因此，设立一个状态标志变量因此，设立一个状态标志变量tag：0：结点暂不能访问结点暂不能访问1：结点可以被访

40、问结点可以被访问tag=其次，设两个堆栈其次，设两个堆栈S1、S2，S1保存结点，保存结点，S2保存结保存结点的点的状态标志变量状态标志变量tag。S1和和S2共用一个栈顶共用一个栈顶指针。指针。设设T是指向根结点的指针变量，非递归算法是：是指向根结点的指针变量，非递归算法是：若二叉树为空，则返回；否则，令若二叉树为空，则返回；否则，令p=T；第一次经过根结点第一次经过根结点p，不访问：，不访问：p进栈进栈S1，tag 赋值赋值0，进栈，进栈S2，p=p-Lchild。若若p不为空，转不为空，转(1)，否则，取状态标志值，否则，取状态标志值tag：若若tag=0：对栈：对栈S1，不访问，不出栈

41、；修改，不访问，不出栈；修改S2栈顶栈顶元素值元素值(tag赋值赋值1)，取，取S1栈顶元素的右子树，即栈顶元素的右子树，即p=S1top-Rchild，转，转(1)；若若tag=1：S1退栈，访问该结点；退栈，访问该结点；直到栈空为止。直到栈空为止。算法实现算法实现：#define MAX_NODE 50void PostorderTraverse(BTNode*T)BTNode*S1MAX_NODE,*p=T;int S2MAX_NODE,top=0,bool=1;if (T=NULL)printf(“Binary Tree is Empty!n”);else do while(p!=NU

42、LL)S1+top=p;S2top=0;p=p-Lchild;if (top=0)bool=0;else if (S2top=0)p=S1top-Rchild;S2top=1;else p=S1top;top-;visit(p-data);p=NULL;/*使循环继续进行而不至于死循环使循环继续进行而不至于死循环*/while(bool!=0);6.3.4层次遍历二叉树层次遍历二叉树 队首元素出队到队首元素出队到p p；访问访问p p所指向的结点；所指向的结点；将将p p所指向的结点的左、右子结点依次入队。直到队空所指向的结点的左、右子结点依次入队。直到队空为止。为止。层次遍历二叉树，是从根结

43、点开始遍历，按层次次层次遍历二叉树，是从根结点开始遍历，按层次次序序“自上而下自上而下，从左至右从左至右”访问树中的各结点。访问树中的各结点。为保证是按层次遍历，必须设置一个队列，初始化为保证是按层次遍历，必须设置一个队列，初始化时为空。时为空。设设T是指向根结点的指针变量，层次遍历非递归算是指向根结点的指针变量，层次遍历非递归算法是：法是：若二叉树为空，则返回；否则，令若二叉树为空，则返回；否则，令p=T，p入队；入队；#define MAX_NODE 50void LevelorderTraverse(BTNode*T)BTNode*QueueMAX_NODE,*p=T;int front

44、=0,rear=0;if (p!=NULL)Queue+rear=p;/*根结点入队根结点入队*/while(frontdata);if(p-Lchild!=NULL)Queue+rear=p-Lchild;/*左结点入队左结点入队*/if(p-Rchild!=NULL)Queue+rear=p-Rchild;/*右结点入队右结点入队*/“遍历”是二叉树最重要的基本操作，是各种其它“遍历”是二叉树最重要的基本操作，是各种其它操作的基础，二叉树的许多其它操作都可以通过遍历来操作的基础，二叉树的许多其它操作都可以通过遍历来实现。如建立二叉树的存储结构、求二叉树的结点数、实现。如建立二叉树的存储结构

45、、求二叉树的结点数、求二叉树的深度等。求二叉树的深度等。6.3.5 二叉树遍历算法的应用二叉树遍历算法的应用1 二叉树的二叉链表创建二叉树的二叉链表创建 按满二叉树方式建立按满二叉树方式建立(补充补充)在此补充按满二叉树的方式对结点进行编号建立链在此补充按满二叉树的方式对结点进行编号建立链式二叉树。对每个结点，输入式二叉树。对每个结点，输入i、ch。i：结点编号，按从小到大的顺序输入结点编号，按从小到大的顺序输入ch：结点内容，假设是字符结点内容，假设是字符在建立过程中借助一个一维数组在建立过程中借助一个一维数组Sn，编号为，编号为i的的结点保存在结点保存在Si中中。算法实现算法实现：#def

46、ine MAX_NODE 50typedef struct BTNode char data;struct BTNode*Lchild,*Rchild;BTNode;BTNode*Create_BTree(void)/*建立链式二叉树，返回指向根结点的指针变量建立链式二叉树，返回指向根结点的指针变量*/BTNode*T,*p,*sMAX_NODE;char ch;int i,j;while(1)scanf(“%d”,&i);if (i=0)break;/*以编号以编号0作为输入结束作为输入结束*/else ch=getchar();p=(BTNode*)malloc(sizeof(BTNode

47、);pdata=ch;pLchild=pRchild=NULL;si=p;if(i=1)T=p;else j=i/2;/*j是是i的双亲结点编号的双亲结点编号*/if(i%2=0)sj-Lchild=p;else sj-Rchild=p;return(T);按先序遍历方式建立按先序遍历方式建立对一棵二叉树进行“扩充”，就可以得到由该二叉对一棵二叉树进行“扩充”，就可以得到由该二叉树所扩充的二叉树。有两棵二叉树树所扩充的二叉树。有两棵二叉树T1及其扩充的二叉树及其扩充的二叉树T2如图如图6-10所示。所示。图图6-10二叉树二叉树T1及其扩充及其扩充二叉树二叉树T2ABCDEFG(a)二叉树二叉

48、树T1(b)T1的扩充的扩充二叉树二叉树T2ABCDEFG?二叉树的扩充方法是：在二叉树中结点的每一个空二叉树的扩充方法是：在二叉树中结点的每一个空链域处增加一个扩充的结点链域处增加一个扩充的结点(总是叶子结点，用方框总是叶子结点，用方框“”表示”表示)。对于二叉树的结点值：。对于二叉树的结点值：是是char类型：扩充结点值为“？”；类型：扩充结点值为“？”；是是int类型：扩充结点值为类型：扩充结点值为0或或-1；下面的算法是二叉树的先序创建的递归算法，读入下面的算法是二叉树的先序创建的递归算法，读入一棵二叉树对应的扩充二叉树的先序遍历的结点值序列。一棵二叉树对应的扩充二叉树的先序遍历的结点

49、值序列。每读入一个结点值就进行分析：每读入一个结点值就进行分析：若是扩充结点值：令根指针为若是扩充结点值：令根指针为NULL；若是若是(正常正常)结点值：动态地为根指针分配一个结结点值：动态地为根指针分配一个结点，将该值赋给根结点，然后递归地创建根的左点，将该值赋给根结点，然后递归地创建根的左子树和右子树。子树和右子树。算法实现算法实现：#define NULLKY?#define MAX_NODE 50typedef struct BTNode char data;struct BTNode*Lchild,*Rchild;BTNode;BTNode*Preorder_Create_BTree

50、(BTNode*T)/*建立链式二叉树，返回指向根结点的指针变量建立链式二叉树，返回指向根结点的指针变量*/char ch;ch=getchar();getchar();if (ch=NULLKY)T=NULL;return(T);else T=(BTNode*)malloc(sizeof(BTNode);Tdata=ch;Preorder_Create_BTree(T-Lchild);Preorder_Create_BTree(T-Rchild);return(T);当希望创建图当希望创建图6-10(a)所示的二叉树时，输入的字符所示的二叉树时，输入的字符序列应当是：序列应当是：ABD?E?