大学数据结构课件树和二叉树.ppt

《大学数据结构课件树和二叉树.ppt》由会员分享，可在线阅读，更多相关《大学数据结构课件树和二叉树.ppt（51页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第6 6章章 树和二叉树树和二叉树前前面面讲讲的的线线性性表表主主要要表表现现的的是是数数据据元元素素之之间间的的前前后次序关系，是一种线性结构。后次序关系，是一种线性结构。树树型型结结构构是是以以分分支支关关系系定定义义的的层层次次结结构构。树树形形结结构构在在客客观观世世界界中中广广泛泛存存在在，如如人人类类的的家家庭庭族族谱谱及及各各种种社社会会组组织织机机构构。又又如如计计算算机机文文件件管管理理和和信信息息组组织织也也用用到到树树形形结结构构。本本章章讨讨论论树树的的基基本本概概念念，重重点点讨讨论论二二叉叉树的有关概念、性质、存储结构和各种运算。树的有关概念、性质、存储结构和各种

2、运算。6.1.1 6.1.1 6.1.1 6.1.1 树的定义树的定义树的定义树的定义树树(tree)是由是由n(n0)个结点组成的有限集合个结点组成的有限集合T。n=0的的树称为空树；对树称为空树；对n0的树，有的树，有:(1)仅有仅有一个特殊的结点称为根一个特殊的结点称为根(root)结点结点，根结点，根结点没有前驱结点；没有前驱结点；(2)当当n1时，除根结点外其余的结点分为时，除根结点外其余的结点分为m(m0)个个互互不相交不相交的有限集合的有限集合T1,T2，Tm，其中每个集合，其中每个集合Ti本身又本身又是一棵树，称之为根的子树（是一棵树，称之为根的子树（subtree）。）。注：

3、注：树的定义具有树的定义具有递归性递归性，即，即“树中还有树树中还有树”。仅有一个根结点的树是最小树，仅有一个根结点的树是最小树，6.1 6.1 树基本概念和术语树基本概念和术语 6.1.2 6.1.2 若干术语若干术语若干术语若干术语（从结构上分）（从结构上分）（从结构上分）（从结构上分）分支结点：分支结点：度不为度不为0 0的结点，除叶结点之外的其余结点。的结点，除叶结点之外的其余结点。ABCGEIDHFJMLK结点（结点（nodenode）：）：由数据元素由数据元素和构造数据元素之间关系的和构造数据元素之间关系的指针组成指针组成结点的度：结点的度：结点所拥有结点所拥有的子树的个数的子树的

4、个数树的度：树的度：树中所有结点的度的最大值树中所有结点的度的最大值叶结点：叶结点：度为度为0 0的结点，也称作的结点，也称作终端结点终端结点结点的层次：结点的层次：从根结点到树中某结点所经路径上的分支数从根结点到树中某结点所经路径上的分支数树的深度：树的深度：树中所有结点的层次的最大值树中所有结点的层次的最大值 森林：森林：m m（m m00）棵树的集合）棵树的集合 6.1.2.6.1.2.若干术语若干术语若干术语若干术语（从关系上分）（从关系上分）（从关系上分）（从关系上分）孩子孩子(child)(child)结点结点：树中一个结点的子树的根结点树中一个结点的子树的根结点双亲双亲(pare

5、nt)(parent)结点：结点：若树中某结点有孩子结点，则这个若树中某结点有孩子结点，则这个结点就称作它的孩子结点的双亲结点结点就称作它的孩子结点的双亲结点 兄弟兄弟(sibling)(sibling)结点：结点：具有相同的双亲结点的结点具有相同的双亲结点的结点 ABCGEIDHFJMLK无序树：无序树：树中任意一个结点的各孩子结点之间的树中任意一个结点的各孩子结点之间的次序构成次序构成 无关紧要无关紧要的树的树有序树：有序树：树中任意一个结点的各孩子结点有严格排列次序的树树中任意一个结点的各孩子结点有严格排列次序的树 6.1.2 6.1.2 若干术语若干术语若干术语若干术语（从结构上分）（

6、从结构上分）（从结构上分）（从结构上分）BEFLKBFELK 树的表示形式树的表示形式树的表示形式树的表示形式(1)(1)倒悬树法倒悬树法(直观表示直观表示)(2)(2)集合包含关系图法集合包含关系图法 (3)(3)凹入表示法凹入表示法 ABCGEIDHFJMLK FEKLCGA ABI IJ JMDHABCDEFGHIJKLM6.1.4 6.1.4 树的抽象数据类型树的抽象数据类型树的抽象数据类型树的抽象数据类型数据集合数据集合:树的结点集合，每个结点由数据元素和构造数树的结点集合，每个结点由数据元素和构造数 据元素之间关系的指针组成。据元素之间关系的指针组成。操作集合操作集合:（1 1）创

7、建）创建MakeTree(T)MakeTree(T)（2 2）撤消）撤消DestroyTree(T)DestroyTree(T)（3 3）双亲结点）双亲结点Parent(T,curr)Parent(T,curr)（4 4）左孩子结点）左孩子结点LeftChild(T,curr)LeftChild(T,curr)（5 5）右兄弟结点）右兄弟结点RightSibling(T,curr)RightSibling(T,curr)（6 6）遍历树）遍历树Traverse(T,Visit()Traverse(T,Visit()树的存储结构树的存储结构树的存储结构树的存储结构 树的结点之间的逻辑关系主要有双

8、亲树的结点之间的逻辑关系主要有双亲-孩子孩子关系，兄弟关系。因此，从结点之间的逻辑关系关系，兄弟关系。因此，从结点之间的逻辑关系分，树的存储结构主要有：分，树的存储结构主要有：双亲表示法、孩子表双亲表示法、孩子表示法、双亲孩子表示法和孩子兄弟表示法示法、双亲孩子表示法和孩子兄弟表示法四种组四种组合。合。指针有指针有常规指针常规指针和和仿真指针仿真指针4H2G1F1E1D0C0B-1AI4data parentdata parent0 01 12 23 34 45 56 67 78 8(1)(1)双亲表示法双亲表示法(a)一棵树一棵树（b)仿真指针的双亲表示法存储结构仿真指针的双亲表示法存储结构

9、树及其使用仿真指针的双亲表示法树及其使用仿真指针的双亲表示法ABCFGEIHD(2)(2)孩子表示法孩子表示法常规指针的孩子表示法常规指针的孩子表示法BCrootAD EF GIH ABCFGEIHD双亲孩子表示法双亲孩子表示法(3)(3)双亲孩子表示法双亲孩子表示法4H2G1F1E1D0C0B-1AI4data parent headdata parent head012345678child nextchild next87123456ABCFGEIHD(4)(4)孩子兄弟表示法孩子兄弟表示法常规指针的孩子兄弟表示法常规指针的孩子兄弟表示法rootBCDEFGHIAABCFGEIHD6.2

10、 二叉树二叉树二叉树二叉树(binary tree)：是是n(n0)个结点的有限集合。个结点的有限集合。n=0的树称为空二叉树；的树称为空二叉树；n0的二叉树由一个根结点以的二叉树由一个根结点以及两棵互不相交的、分别称为及两棵互不相交的、分别称为左子树和右子树左子树和右子树的的二叉树组成二叉树组成。其。其逻辑结构：逻辑结构：一对二（一对二（1:2）左、右子树也是二叉树，所以子树也可以为空树。下图左、右子树也是二叉树，所以子树也可以为空树。下图展现了五种不同形态的二叉树。展现了五种不同形态的二叉树。二叉树的定义二叉树的定义二叉树的定义二叉树的定义n=0n=0n=1n=1n1n1n1n1n1n1基

11、本特征基本特征:每个结点最多只有两棵子树（不存在度大于每个结点最多只有两棵子树（不存在度大于2的结点）；的结点）；左子树和右子树左子树和右子树次序不能颠倒次序不能颠倒。所以下面是两棵不同的树。所以下面是两棵不同的树 二叉树的定义二叉树的定义二叉树的定义二叉树的定义BACEDFGBACEDFG满二叉树：满二叉树：在一棵二叉树中，如果所有分支结点都存在左在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样子树和右子树，并且所有叶子结点都在同一层上，这样的二叉树称为满二叉树。的二叉树称为满二叉树。BACEDFGHIJKLMNO完全二叉树：完全二叉树：如果一棵深度为

12、如果一棵深度为k k，有，有n n个结点的二叉树中各个结点的二叉树中各 结点能够与深度为结点能够与深度为k k的顺序编号的满二叉树从的顺序编号的满二叉树从1 1到到n n标号的标号的 结点相对应的二叉树称为完全二叉树。如下图所示结点相对应的二叉树称为完全二叉树。如下图所示BACEDFGHIJBACEDFGHIJKLMNO(a)满二叉树满二叉树 (b)完全二叉树完全二叉树 数据集合：数据集合：二叉树的结点集合，每个结点由数据元素和构造数二叉树的结点集合，每个结点由数据元素和构造数据元素之间关系的指针组成。据元素之间关系的指针组成。操作集合：操作集合：（1 1）创建）创建MakeTree(T)Ma

13、keTree(T)（2 2）撤消）撤消DestroyTree(T)DestroyTree(T)（3 3）左插入结点）左插入结点InsertLeftNode(curr,x)InsertLeftNode(curr,x)（4 4）右插入结点）右插入结点InsertRightNode(curr,x)InsertRightNode(curr,x)（5 5）左删除子树）左删除子树DeleteLeftTree(curr)DeleteLeftTree(curr)（6 6）右删除子树）右删除子树DeleteRightTree(curr)DeleteRightTree(curr)（7 7）遍历二叉树）遍历二叉树T

14、raverse(T,Visit()Traverse(T,Visit()二叉树抽象数据类型二叉树抽象数据类型二叉树抽象数据类型二叉树抽象数据类型k=ik=i2 2i-1-1 二叉树的重要性质二叉树的重要性质二叉树的重要性质二叉树的重要性质性质性质1 1:二叉树的第二叉树的第二叉树的第二叉树的第i i（i i1 1）层上至多有）层上至多有）层上至多有）层上至多有2 2i-1i-1个结点。个结点。个结点。个结点。i=1i=1 2 21-11-1=2=20 0=1=1i=2i=22 22-12-1=2=21 1=2=2i=3i=32 23-13-1=2=22 2=4=4BACEDFGHIJKLMNOi

15、=4i=42 24-14-1=2=23 3=8=8k=ik=i 二叉树的重要性质二叉树的重要性质二叉树的重要性质二叉树的重要性质性质性质2:2:深度为深度为深度为深度为k(k1)k(k1)的二叉树至多有的二叉树至多有的二叉树至多有的二叉树至多有2 2k k-1-1个结点。个结点。个结点。个结点。k3 2 1k3 2 1 0 00 0 0 00 0 1 1 2 20 0 0 00 0 00 1 1 0 2 0 21 1 0 0 0 01 1 0 0 2 0 0 22 2 +0 0 1 10 0 0 20 0 0 2k-1k-1 0 11 1 1 2 0 11 1 1 2k k-1-1 证明一：证

16、明一：证明一：证明一：2 2 2 20 0 0 0+2+2+2+21 1 1 1+2+2+2+22 2 2 2+2+2+2+2k-1k-1k-1k-1 =2 =2 =2 =2k k k k-1-1-1-11+1+1+1+-1-1-1-1=2=21 1=2=22 2=2=23 3=2=2k-1k-1=2=2k k=2=20 01 00 0 01 00 0 0+1 1k kBACEDFGHIJKLM NOk=ik=i2 2i-1-1证明三：证明三：证明三：证明三：等比数列前等比数列前等比数列前等比数列前n n n n项和的计算公式：项和的计算公式：项和的计算公式：项和的计算公式：证明二：证明二：证

17、明二：证明二：n=kn=ka a1 1=1=1q=2q=2性性质质3 3 对对于于一一棵棵非非空空的的二二叉叉树树，如如果果叶叶结结点点个个数数为为n n0 0，度为度为2 2的结点数为的结点数为n n2 2，则有，则有n n0 0=n=n2 2+1+1。BACEDFGHIJn0=n2+1。证明：设证明：设n n为二叉树的结点总数，为二叉树的结点总数，n n1 1为二叉树为二叉树中度为中度为1 1的结点个数，则有：的结点个数，则有：n=nn=n0 0+n+n1 1+n+n2 2 (1)(1)由于二叉树中除根结点外，由于二叉树中除根结点外，每个结点都有一条与其父每个结点都有一条与其父结点相连的边

18、。所以，有结点相连的边。所以，有n n个结点的二叉树总共有个结点的二叉树总共有 n-1n-1条边。于是有：条边。于是有：n-1=0nn-1=0n0 0+1n+1n1 1+2n+2n2 2 (2)(2)再把再把(1)(1)代入代入(2)(2)，得：，得：n n0 0+n n1 1+n+n2 2-1=n-1=n1 1+2n+2n2 2则可以得到则可以得到:性质性质性质性质4:4:4:4:具有具有具有具有n n个结点的完全二叉树的深度为个结点的完全二叉树的深度为个结点的完全二叉树的深度为个结点的完全二叉树的深度为 loglog2 2(n(n)+1。k-1-1=loglog2 2(n(n)BACEDF

19、GHIJ证明：根据性质证明：根据性质2 2，对于有对于有n n个结个结点的深度为点的深度为k k的完全二叉树有的完全二叉树有:2 2k-1k-1-1-1n n22k k-1-1 因为该不等式各项均为整数，当对两端各加因为该不等式各项均为整数，当对两端各加1 1时不时不等式发生变化得：等式发生变化得：2 2k-1 k-1 n n 2 2k k对不等式求对数，有对不等式求对数，有k-1k-1loglog2 2(n n)1i1时，其双亲是结点时，其双亲是结点i/2 i/2(“/”(“/”表示整除）；表示整除）；若若2in2in，则第，则第i i个结点有编号为个结点有编号为2i2i的左孩子；的左孩子；

20、若若2i+1n2i+1n，则第，则第i i 个结点有编号为个结点有编号为2i+12i+1的右孩子的右孩子 完全二叉树的结点可按从上到下和从左至右的次完全二叉树的结点可按从上到下和从左至右的次序存储在一维数组中，其结点之间的关系可由公式计序存储在一维数组中，其结点之间的关系可由公式计算得到，这就是二叉树的顺序存储结构。下面两棵树算得到，这就是二叉树的顺序存储结构。下面两棵树在数组中的存储结构分别为：在数组中的存储结构分别为：二叉树的存储结构二叉树的存储结构二叉树的存储结构二叉树的存储结构二叉树的存储结构有多种，最常用的有两种：二叉树的存储结构有多种，最常用的有两种：顺序存储结构和链表存储结构顺序

21、存储结构和链表存储结构1.1.二叉树的顺序存储结构二叉树的顺序存储结构BACEDFGHIJKLMNO1204357611810912 13 14 15DA BCONMLKJIHGFE1 12 23 34 45 56 67 78 89 9 1010n=15n=1511111212131314141515满二叉树：满二叉树：结点：结点：i=5i=5父结点：父结点：i/2=5/2=2i/2=5/2=2左孩子：左孩子：2i=2*5=102i=2*5=10右孩子：右孩子：2i+1=2*5+1=112i+1=2*5+1=11完全二叉树：完全二叉树：BACEDFGHIJ1 12 23 34 45 56 67

22、 78 89 9 1010n=10n=10120435768910A BCDJIHGFE对于一般的非完全二叉树对于一般的非完全二叉树BACEGDFA BCGFED1204357611810912数组数组下标下标13 必须首先在非完全二叉树中增添一些并不存在的空结点使之必须首先在非完全二叉树中增添一些并不存在的空结点使之变成完全二叉树的形态。变成完全二叉树的形态。然后再用顺序存储结构存储在一维数组中。然后再用顺序存储结构存储在一维数组中。显然不能直接使用二叉树的顺序存储结构。显然不能直接使用二叉树的顺序存储结构。所以，顺序存储结构仅适于满二叉树或完全二叉树，一般二叉树所以，顺序存储结构仅适于满二

23、叉树或完全二叉树，一般二叉树更适宜用链表存储结构更适宜用链表存储结构二叉树的链式存储结构是用指针建立二叉树中结点之间的关系。二叉树的链式存储结构是用指针建立二叉树中结点之间的关系。二叉二叉树最常用的的链式表储结构是二叉链和三叉链。树最常用的的链式表储结构是二叉链和三叉链。二叉链存储结构的每二叉链存储结构的每个结点包含三个域，分别是数据域个结点包含三个域，分别是数据域data、左孩子指针域、左孩子指针域leftChild和右孩和右孩子指针域子指针域rightChild。二叉链存储结构中每个结点的图示结构为：。二叉链存储结构中每个结点的图示结构为：rightChilddataleftChild 三

24、叉链表的结点比前者多了三叉链表的结点比前者多了一个指向双亲的指针域。一个指向双亲的指针域。2.2.二叉树的链式存储结构二叉树的链式存储结构结点结构描为：结点结构描为：typedef struct node ElemType data;struct node*lch,*rch;Bnode;typedef struct node ElemType data;struct node*lch,*par,*rch;/*par是双亲指针域是双亲指针域*/Bnode3;parrchdatalch结点结构描为：结点结构描为：A BCD F J K ABCDFJK BACDJFK二叉链表二叉链表三叉链表三叉链表

25、二叉树二叉树二叉树的仿真指针存储二叉树的仿真指针存储结构结构是用数组存储二叉树中的结点，是用数组存储二叉树中的结点，数组中每个结点除数据元素域外，再增加仿真指针域用于仿数组中每个结点除数据元素域外，再增加仿真指针域用于仿真常规指针建立二叉树中结点之间的关系。真常规指针建立二叉树中结点之间的关系。二叉树的仿真二叉链存储结构二叉树的仿真二叉链存储结构BACDGEF二叉树的仿真指针二叉树的仿真指针6.2.5 二叉树二叉链表的一个生成算法二叉树二叉链表的一个生成算法 创建二叉树的方法有多种，并且算法都比较复杂，这里我们运创建二叉树的方法有多种，并且算法都比较复杂，这里我们运用二叉树的性质用二叉树的性质

26、5 5，学习一种较简单的生成算法。，学习一种较简单的生成算法。对任意二叉树，首先按满二叉树的结构对其结点进行编号。对任意二叉树，首先按满二叉树的结构对其结点进行编号。1211131416151 12 23 34 45 56 67 78 89 9i123469x111213141516 此树并非完全二叉树，此树并非完全二叉树，因此结点编号不连续。算因此结点编号不连续。算法中用一个辅助向量法中用一个辅助向量s s存存放树结点的指针。该向量放树结点的指针。该向量的类型为：的类型为：Bnode*sMAXSIZEBnode*creat()Bnode*t=NULL;printf(“n i,x=”);sca

27、nf(“%d%d”,&i,&x);while(i!=0&x!=0)q=(Bnode*)malloc(sizeof(Bnode);q-data=x;q-lch=NULL;q-rch=NULL;si=q;/*Bnode*s20 */if(i=1)t=q;/*t为树根结点为树根结点*/else j=i/2;/*j为双亲结点编号为双亲结点编号*/if(i%2)=0)sj-lch=q;else sj-rch=q;printf(“n i,x=”);scanf(“%d%d”,&i,&x);return t;/*creat end*/typedef struct node ElemType data;stru

28、ct node*lch,*rch;Bnode;012345678910 11 12 13 14 15 16 17 18 19*s*s1211131416151 12 23 34 46 69 9ti的父结点：的父结点：ti/2 左孩子：左孩子：t2i 右孩子：右孩子：t2i+16.3 6.3 二叉树遍历二叉树遍历 遍历二叉树是指以一定的次序访问二叉树中的每个遍历二叉树是指以一定的次序访问二叉树中的每个结点，并且每个结点仅访问一次。所谓访问结点是指对结点，并且每个结点仅访问一次。所谓访问结点是指对结点进行各种操作的简称。结点进行各种操作的简称。遍历二叉树的过程实质上是把二叉树的结点进行线遍历二叉树

29、的过程实质上是把二叉树的结点进行线性排列的过程。假如访问结点的操作是输出结点数据域性排列的过程。假如访问结点的操作是输出结点数据域的值，那么遍历的结果就会得到一个线性序列。的值，那么遍历的结果就会得到一个线性序列。由于二叉树有左、右子树，因此遍历的次序不同，由于二叉树有左、右子树，因此遍历的次序不同，得到的结果也就不同。得到的结果也就不同。从二叉树的定义知，一棵二叉树由三部分组成：根从二叉树的定义知，一棵二叉树由三部分组成：根结点、左子树和右子树。结点、左子树和右子树。则有三种不同的遍历次序：则有三种不同的遍历次序：TLR-前序遍历（先根遍历）前序遍历（先根遍历）LTR-中序遍历（中根遍历）中

30、序遍历（中根遍历）LRT-后序遍历后序遍历（后根遍历）（后根遍历）若规定：若规定：T-代表访问根结点代表访问根结点 L-代表遍历根结点的左子树代表遍历根结点的左子树 R-代表遍历根结点的右子树代表遍历根结点的右子树T TL LR RT TL LRABCDDD遍历搜索示意图遍历搜索示意图图中二叉树有四个结点图中二叉树有四个结点ABCDABCD，为了便于理解遍历的思想，为每个没有子树的，为了便于理解遍历的思想，为每个没有子树的结点补上相应的空子树。结点补上相应的空子树。设想有一条搜索路线设想有一条搜索路线.，它从根结点的左侧开始，自上而下，自左至右搜索，它从根结点的左侧开始，自上而下，自左至右搜索

31、，最后从根结点的右侧向上出去。恰好搜索线途经每个有效树结点都是三次最后从根结点的右侧向上出去。恰好搜索线途经每个有效树结点都是三次搜索线第一次经过就访问的结点序列搜索线第一次经过就访问的结点序列ABCDABCD，称先根遍历；搜索线第二次经过才，称先根遍历；搜索线第二次经过才访问的结点序列访问的结点序列BADCBADC，称中根遍历；搜索线第三次经过才访问的序列，称中根遍历；搜索线第三次经过才访问的序列BDCA,BDCA,称后称后根遍历根遍历A,B,C,D A,B,C,D 先根（前序）遍历先根（前序）遍历B,A,D,C B,A,D,C 中根（序）遍历中根（序）遍历B,D,C,A B,D,C,A 后

32、根（序）遍历后根（序）遍历二二叉叉树树选选择择不不同同的的存存储储结结构构，遍遍历历算算法法的的程程序序代代码码会会有有所所不不同同。这这里里确确定定用用二二叉叉链链表表作作为为存存储储结结构构，树树中中结点的结构定义为：结点的结构定义为：typedef struct node ElemType data;struct node*lch,*rch;Bnode;若根为空则结束；否则：若根为空则结束；否则：（1 1）访问根结点；）访问根结点；（2 2）按先根次序遍历左子树；）按先根次序遍历左子树；（3 3）按先根次序遍历右子树。）按先根次序遍历右子树。6.3.1 先根遍历先根遍历（先根遍历（TLR

33、TLR）递归算法为：）递归算法为：若根为空则结束；否则：若根为空则结束；否则：若根为空则结束；否则：若根为空则结束；否则：（1 1 1 1）访问根结点；）访问根结点；）访问根结点；）访问根结点；（2 2 2 2）按先根次序遍历左子树；）按先根次序遍历左子树；）按先根次序遍历左子树；）按先根次序遍历左子树；（3 3 3 3）按先根次序遍历右子树。）按先根次序遍历右子树。）按先根次序遍历右子树。）按先根次序遍历右子树。若根为空则结束；否则：若根为空则结束；否则：若根为空则结束；否则：若根为空则结束；否则：（1 1 1 1）访问根结点；）访问根结点；）访问根结点；）访问根结点；（2 2 2 2）按先

34、根次序遍历左子树；）按先根次序遍历左子树；）按先根次序遍历左子树；）按先根次序遍历左子树；（3 3 3 3）按先根次序遍历右子树。）按先根次序遍历右子树。）按先根次序遍历右子树。）按先根次序遍历右子树。Void preorder(Bnode*p)if(p!=NULL)printf(“%6c”,p-data);preorder(p-lch);preorder(p-rch);/*preorder*/此处假设此处假设ElemTypeElemType为为charchar型型ABCDA B C D p p访问访问A遍历左子树遍历左子树遍历右子树遍历右子树返回返回访问访问B遍历左子树遍历左子树遍历右子树遍

35、历右子树返回返回访问访问C遍历左子树遍历左子树遍历右子树遍历右子树返回返回访问访问D遍历左子树遍历左子树遍历右子树遍历右子树返回返回根为根为NULLNULL返回返回根为根为NULLNULL返回返回根为根为NULLNULL返回返回根为根为NULLNULL返回返回根为根为NULLNULL返回返回先根遍历递归调用示意图先根遍历递归调用示意图先根遍历递归调用示意图先根遍历递归调用示意图若根为空则结束；否则：若根为空则结束；否则：（1 1）按中根次序遍历左子树；）按中根次序遍历左子树；（2 2）访问根结点；）访问根结点；（3 3）按中根次序遍历右子树。）按中根次序遍历右子树。6.3.2 中根遍历中根遍历

36、（中根遍历（LTRLTR）与先根遍历相似，只是在根不空时将算法的第一步）与先根遍历相似，只是在根不空时将算法的第一步与第二步次序对换而已，即：与第二步次序对换而已，即：Void inorder(Bnode*p)if(p!=NULL)inorder(p-lch);printf(“%6c”,p-data);inorder(p-rch);/*inorder*/此处假设此处假设ElemTypeElemType为为charchar型型实现算法的代码也是在先根实现算法的代码也是在先根算法基础上稍做改动，即：算法基础上稍做改动，即：递归算法简练但执行效率较低，递归算法简练但执行效率较低，而且有些高级也不支持

37、递归调而且有些高级也不支持递归调用，作为程序设计能力的训练，用，作为程序设计能力的训练，有必要学习非递归算法。有必要学习非递归算法。s s01234中根遍历的非递归算法如下：中根遍历的非递归算法如下：voide inorderz(Bnode*p)/*栈栈s是是Bnode*s10 */q=p;top=0;/*栈顶指针栈顶指针*/bool=1;/*bool=1表示栈不空表示栈不空*/printf(“n 中根遍历：中根遍历：n”);do while(q!=NULL)top+;stop=q;q=q-lch;if(top=0)bool=0;else q=stop;top-;printf(“%6c”,q-

38、data);/*访问根结点访问根结点*/q=q-rch;while(bool);printf(“n”);/*inorderz */ABCDA B C D p ptopC AB DtoptopB B A AD DC C6.3.3 后根遍历若根为空则结束；否则：若根为空则结束；否则：（1 1）按后根次序遍历左子树；）按后根次序遍历左子树；（2 2）按后根次序遍历右子树；）按后根次序遍历右子树；（3 3）访问根结点。）访问根结点。Void postorder(Bnode*p)if(p!=NULL)postorder(p-lch);postorder(p-rch);printf(“%6c”,p-dat

39、a);/*postorder*/后根遍历的非递归算法较为复杂，它需要两个栈，第一个栈后根遍历的非递归算法较为复杂，它需要两个栈，第一个栈的用途与中根遍历相同，第二个栈用来经过某根结点的次数。两的用途与中根遍历相同，第二个栈用来经过某根结点的次数。两个栈的数据类型为：个栈的数据类型为：Bnode*s10;int s220;Bnode*s10;int s220;具体算法程序留给同学们课外阅读。（具体算法程序留给同学们课外阅读。（P111P111）void levelorder(Bnode*p)Bnode*q20;front=0;rear=0;if(p!=NULL)rear+;qrear=p;/*根

40、结点不空，进队根结点不空，进队*/while(front!=rear)front+;p=qfront;printf(“%6c”,p-data);/*出队并访问出队并访问*/if(p-lch!=NULL)rear+;qrear=p-lch;/*若左孩子不空，进队若左孩子不空，进队*/if(p-rch!=NULL)rear+;qrear=p-rch;/*若左孩子不空，进队若左孩子不空，进队*/*levelorder*/6.3.4 按层遍历二叉树AB C D FJ K BACDJFKpFR109876543210qRRRRRRRFFFFFFFabcdfjkpppppp（1 1）初始化设置一个队列；）

41、初始化设置一个队列；（2 2）把根结点指针入队列；）把根结点指针入队列；（3 3）当队列非空时，循环执行步骤）当队列非空时，循环执行步骤（3.a）到步骤到步骤（3.c）（3.a3.a）出队列取得一个结点指针，访问该结点；）出队列取得一个结点指针，访问该结点；（3.b3.b）若该结点的左子树非空，则将该结点的左子树指）若该结点的左子树非空，则将该结点的左子树指针入队列；针入队列；（3.c3.c）若该结点的右子树非空，则将该结点的右子树指）若该结点的右子树非空，则将该结点的右子树指针入队列；针入队列；（4 4）结束。）结束。按层遍历二叉树的算法可以用语言描述如下：按层遍历二叉树被称为按层遍历二叉树

42、被称为层序遍历层序遍历。层序遍历的要求是：。层序遍历的要求是：按二叉树的层序次序（即按二叉树的层序次序（即从根结点层至叶结点层从根结点层至叶结点层），同一），同一层中按层中按先左子树再右子树先左子树再右子树的次序遍历二叉树。的次序遍历二叉树。可以借助队列实现二叉树的层序遍历可以借助队列实现二叉树的层序遍历。它的特点是，在所有未被访问结点的集合中，排列它的特点是，在所有未被访问结点的集合中，排列在已访问结点集合中最前面结点的左孩子将最先被访问，在已访问结点集合中最前面结点的左孩子将最先被访问，然后是该结点的右孩子。这样，如果把已访问的结点放然后是该结点的右孩子。这样，如果把已访问的结点放在一个队

43、列中，那么，所有未被访问结点的访问次序就在一个队列中，那么，所有未被访问结点的访问次序就可以由存放在队列中的已访问结点的出队列次序决定。可以由存放在队列中的已访问结点的出队列次序决定。因此因此把把二二叉叉树树逆逆时时针针旋旋转转900C，按按照照二二叉叉树树的的凹凹入入表表示示法法打打印印二二叉叉树树。可可把把此此函函数数设设计计成成递递归归函函数数。由由于于把把二二叉叉树树逆逆时时针针旋旋转转900C后后，在在屏屏幕幕上上方方的的首首先先是是右右子子树树，然然后后是是根根结结点点，最最后后是是左左子子树树，所所以以打打印印二二叉叉树树算算法法是是一一种种特特殊殊的的中中序序遍遍历历算法。算法

44、。6.3.5 二叉树遍历的应用1 1 打印二叉树打印二叉树void PrintBiTree(Bnode*bt,int n)int i;if(bt=NULL)return;PrintBiTree(bt-rightChild,n+1);for(i=0;i 0)printf(-);printf(%cn,bt-data);PrintBiTree(bt-leftChild,n+1);在在二二叉叉树树中中查查找找数数据据元元素素操操作作的的要要求求是是：在在bt为为根根结结点点指指针针的的二二叉叉树树中中查查找找数数据据元元素素x，若若查查找找到到数数据据元元素素x时时返返回回该该结结点点的的指指针针；若

45、若查查找不到数据元素找不到数据元素x时返回空指针。时返回空指针。在在二二叉叉树树bt中中查查找找数数据据元元素素x算算法法可可设设计计成成先先序序遍遍历历算算法法，此此时时查查找找结结点点的的次次序序是是：首首先先在在根根结结点点查查找找，然然后后在在左左子子树树查查找找，最最后后在在右右子子树树查查找找。但但是是，和和常常规规递递归归算算法法不不同同的的是是，此此算算法法当当一一个个分分支支上上的的结结点点比比较较完完仍仍未未查查找找到到数数据据元元素素x时时，要要返返回回到到该该结结点点的的双双亲亲结结点点处处继继续续查查找找。因因此此，此此算算法法是是一一个个回回溯算法溯算法。2 2 查

46、找数据元素查找数据元素BiTreeNode*Search(Bnode*bt,ElemType x)BiTreeNode*p;if(bt=NULL)return NULL;if(bt-data=x)return bt;if(bt-leftChild!=NULL)p=Search(bt-leftChild,x);if(p!=NULL)return p;if(bt-rightChild!=NULL)p=Search(bt-rightChild,x);if(p!=NULL)return p;return NULL;6.4 线索二叉树 线索二叉树是另一种分步遍历二叉树的方法。它线索二叉树是另一种分步遍历

47、二叉树的方法。它既可以从前向后既可以从前向后分步遍历二叉树，分步遍历二叉树，又可以从后向前又可以从后向前分步遍历二叉树。分步遍历二叉树。当按某种规则遍历二叉树时，保存遍历时得到的结点的后继结点当按某种规则遍历二叉树时，保存遍历时得到的结点的后继结点信息和前驱结点信息的最常用的方法是建立线索二叉树。信息和前驱结点信息的最常用的方法是建立线索二叉树。对二叉链表存储结构的二叉树分析可知，在有对二叉链表存储结构的二叉树分析可知，在有n n个结点的二叉个结点的二叉树中必定存在树中必定存在n+1n+1个空链域。个空链域。ABCDA B C D p p先根遍历：先根遍历：A,B,C,DA,B,C,D中根遍历

48、：中根遍历：B,A,D,CB,A,D,C后根遍历：后根遍历：B,D,C,AB,D,C,A6.4.1 线索二叉树的基本概念 规定规定：当当某某结结点点的的左左指指针针为为空空时时，令令该该指指针针指指向向按按某某种种方方法法遍遍历历二二叉叉树树后后得到的线性序列中该结点所处位置的前驱结点；得到的线性序列中该结点所处位置的前驱结点；当当某某结结点点的的右右指指针针为为空空时时，令令该该指指针针指指向向按按某某种种方方法法遍遍历历二二叉叉树树后后所得线性序列中该结点所处位置的后继结点。所得线性序列中该结点所处位置的后继结点。仅仅仅仅这这样样做做会会使使我我们们不不能能区区分分左左指指针针指指向向的的

49、结结点点到到底底是是左左孩孩子子结结点点还是前驱结点，右指针指向的结点到底是右孩子结点还是后继结点。还是前驱结点，右指针指向的结点到底是右孩子结点还是后继结点。因因此此我我们们需需要要在在结结点点中中增增加加两两个个线线索索标标志志位位来来区区分分这这两两种种情情况况。线线索标志位定义如下：索标志位定义如下：每个结点的结构：每个结点的结构：lchlch ltagltag datartagrtagrchrch 结点中指向前驱结点和后继结点的指针称为结点中指向前驱结点和后继结点的指针称为线索。线索。在二叉树的在二叉树的结点上加上线索的二叉树称作结点上加上线索的二叉树称作线索二叉树。线索二叉树。对二

50、叉树以某种方法对二叉树以某种方法（如前序、中序或后序方法）遍历使其变为线索二叉树的过程称作（如前序、中序或后序方法）遍历使其变为线索二叉树的过程称作按该方法按该方法对二叉树进行的线索化。对二叉树进行的线索化。typedef struct node ElemType data;struct node*lch,*rch;int ltag,rtag;Btnode;ABCDA B C D 先根遍历：先根遍历：A,B,C,DA,B,C,D中根遍历：中根遍历：B,A,D,CB,A,D,C后根遍历：后根遍历：B,D,C,AB,D,C,AABCD0 A 01 B 10 C 11 D 1NULLNULLNULL