6.3 遍历二叉树和线索二叉树（知识点二） 遍历二叉树 一、问题的提出

Presentation on theme: "6.3 遍历二叉树和线索二叉树（知识点二） 遍历二叉树 一、问题的提出"— Presentation transcript:

1 6.3 遍历二叉树和线索二叉树（知识点二） 6.3.1 遍历二叉树 一、问题的提出
6.3 遍历二叉树和线索二叉树（知识点二） 6.3.1 遍历二叉树 一、问题的提出 顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次。 “访问”的含义可以很广，如：输出结点的信息等。 “遍历”是任何类型均有的操作，对线性结构而言，只有一条搜索路径（因为每个结点均只有一个后继），故不需要另加讨论。 而二叉树是非线性结构，每个结点有两个后继，则存在如何遍历即按什么样的搜索路径遍历的问题。

2 对二叉树，可有六条搜索路径： 1、 （先根访问） （1）先（遍历）访问根节点； （2）（遍历）访问左子树后右;（递归） （3）（遍历）访问右子树； （递归） 2、中根访问 （1）先（遍历）访问左子树；递归） （2）其次（遍历）访问根节点； （3）再（遍历）访问右子树； （递归） 3、后根访问 （1）先（遍历）访问左子树；（递归） （2）其次（遍历）访问右子树；（递归） （3）再（遍历）访问根节点；

3 4、 （先根逆访问） （1）先（遍历）访问根节点； （2）（遍历）访问右子树； （递归） （3）（遍历）访问左子树;（递归） 5、中根逆访问 （1）先（遍历）访问右子树； （递归） （2）其次（遍历）访问根节点； （3）再（遍历）访问左子树；递归） 6、后根逆访问 （1）先（遍历）访问右子树；（递归） （2）其次（遍历）访问左子树；（递归） （3）再（遍历）访问根节点； 一般只用前三种遍历就可以，即先根访问、中根访问和后根访问。

4 二、先左后右的遍历算法 1、先（根）序的遍历算法 2、中（根）序的遍历算法 3、后（根）序的遍历算法

5 1. 前序遍历算法 表达式语法树 前序遍历二叉树算法 的核心是： 若二叉树不为空， 则 —访问根结点； 前序遍历左子树； 前序遍历右子树。
ROOT 前序遍历二叉树算法 的核心是： 若二叉树不为空， 则 —访问根结点； 前序遍历左子树； 前序遍历右子树。 遍历结果： + a * b - c d / e f 表达式语法树

6 2.中序遍历 表达式语法树 中序遍历二叉树算法 的框架是： 若二叉树不为空，则 —中序遍历左子树； 访问根结点 ； 中序遍历右子树。
遍历结果 a + b * c - d - e / f ROOT 表达式语法树

7 3. 后序遍历 表达式语法树 后序遍历二叉树算法 的框架是： 若二叉树为空，； 则 后序遍历左子树； 后序遍历右子树 ； 访问根结点。
遍历结果： a b c d - * + e f / - ROOT 表达式语法树

8 三、层序遍历 表达式语法树 按自上而下，每层从 左到右顺序访问结点。 例如：右图的遍历结果： - + / a * e f b - c d
@作为作业题完成 表达式语法树

9 两个推论 推论一：若已知一棵二叉树的前序序列和中序序列,则可以唯一的确定这棵二叉树.
推论二：若已知一棵二叉树的后序序列和中序序列,则也可以唯一的确定这棵二叉树. 例1：假如一个二叉树的前序遍历序列为：- + a * b - c d / e f；其中序遍历序列为：a + b * c - d - e / f；（1）根据前序遍历结果可以看出该二叉树的根节点为“-”；（2）根据中序遍历结果可以看出其左子树部分结果为{a + b * c - d }；右子树部分结果为{e / f}；（3）根据左子树部分结果 {a + b * c - d }可以找出该树的最左节点为“a”; 最右结点为“ d”；（4）再根据前序遍历结果”+”紧跟在根结点“-”的后面，因此，“a”的当前的根结点为“＋”；（５）再根据前序和中序结果找出“*” 作为当前“＋”的右结点，….。依此类推，得出当前的二叉树（如前面的二叉树例子）。

10 例：证明：一棵二叉树的前序序列和中序序列可 以唯一的确定这棵二叉树。 用归纳法证明： 1、当 n = 1时，结论显然成立；
证明推论一（１） 例：证明：一棵二叉树的前序序列和中序序列可 以唯一的确定这棵二叉树。 用归纳法证明： 1、当 n = 1时，结论显然成立； 2、假定当 n <= k 时，结论成立； 3、当 n = k + 1 时，假定前序序列为和中序序列分别为： {a1，…，am} 和 {b1， … ，bm}

11 (1)若j = 1时，二叉树无左子树，由 {a2，…，am} 和 {b2， … ，bm} 可以唯一确定二叉树的右子树；
证明推论一（２） 如中序序列中与前序序列a1相同的元素为bj。 (1)若j = 1时，二叉树无左子树，由 {a2，…，am} 和 {b2， … ，bm} 可以唯一确定二叉树的右子树； (2)若j = m时，二叉树无右子树，由 {a2，…，am} 和 {b1， … ，bm-1} 可以唯一确定二叉树的左子树； (3)若如2<=j<=m-1，则子序列 {a2，…，aj} 和 {b1， … ，bj-1}唯一确定二叉树的左子树；子序列{aj+1，…，am} 和 {bj+1， … ，bm}唯一确定二叉树的右 子树；

12 {b1，… ，bj-1，bj ，bj+1，… ，bm }
证明推论一（３） {a1，a2 ， …，aj， aj+1， …，am} 个数相同 {b1，… ，bj-1，bj ，bj+1，… ，bm } 唯一的确定左子树 唯一的确定右子树

13 例：已知前序序列为 { ABHFDECKG } ，中序序列为 { HBDFAEKCG }, 试构造二叉树。
解：过程如下：

14 如果前序序列固定不变，给出不同的中序序列，可得到不同的二叉树。
前序序列：1，2，3，4，5，6，7，8，9 中序序列a：3，2，5，4，1，6，8，7，9 中序序列b：4，3，5，2，1，7，6，8，9

15 例：若二叉树有 3 个结点 { 1, 2, 3 }，前序序列为 123，则可得5种不同的二叉树。

16 先序遍历 先序遍历序列：A B D C 算法参见P129
D L R 前序遍历二叉树算法是: 若二叉树为空，则空操作； 否则 访问根结点 (D)； 先序遍历左子树 (L)； 先序遍历右子树 (R)。 D L R A D L R B > D L R C > > A D B C D > > 先序遍历序列：A B D C 算法参见P129

17 中序遍历二叉树算法： 若二叉树为空，则空操作； 否则: 中序遍历左子树 (L)； 访问根结点 (D)； 中序遍历右子树 (R)。
A L D R > B L D R > C > A D B C > D > 中序遍历序列：B D A C

18 后序遍历 后序遍历序列： D B C A L R D 后序遍历二叉树算法是:
> > C A D B C > > D 后序遍历序列： D B C A

19 四、算法的递归描述 // 用链表存储结构表示二叉树。 typedef char TElemType;
先序遍历二叉树算法6.1 二叉链表结点定义 // 用链表存储结构表示二叉树。 typedef char TElemType; typedef struct BiTNode { TElemType data; struct BiTNode *lchild, *rchild; // 左右孩子指 }BiTNode, *BiTree;

20 1、先序遍历二叉树算法6.1 //算法6.1，P129改动，先序递归遍历T,对每个结点调用函数Visit一次且仅一次 void PreOrderTraverse(BiTree T,int(*Visit)(TElemType)){ if(T) // T不空 { Visit(T->data); //先序访问根结点 PreOrderTraverse(T->lchild,Visit); // 先序遍历左子树 PreOrderTraverse(T->rchild,Visit); // 先序遍历右子树 }

21 仍然以下面的二叉树为例： PreOrderTraverse(BiTree T,int(*Visit)(TElemType)){ ① if(T) // T不空 ② { ③Visit(T->data);//先序访问根A结点 ④PreOrderTraverse(T->lchild,Visit); ∆1 ⑤PreOrderTraverse(T->rchild,Visit); ⑥ } ⑦ } 转第一次递归,参数为：A的左 #include <stdio.h> int main() { …; PreOrderTraverse(T,vi); ∆0: Printf…; …; } 1 3 ∆0, T,vi A D B C 2 先执行① ② ③首先访问结点A； 再执行语句④转入第一次递归； Top=2 ∆1, ⑤,A ∆0, T,vi

22 执行第一次递归，参数为“A的左”=B A的左=B
PreOrderTraverse(BiTree T,int(*Visit)(TElemType)){ ① if(T) // T不空,因这时T=B ② { ③Visit(T->data); //访问B结点 ④PreOrderTraverse(T->lchild,Visit); ∆2 ⑤PreOrderTraverse(T->rchild,Visit); ⑥ } ⑦ } 转第二次递归 下次参数为B的左： 2 1 Top=3 ∆2, ⑤,B ∆1, ⑤,A ∆0, T,vi

23 执行第二次递归，参数为“B的左”=^ ∆2, ⑤,B ∆1, ⑤,A B的左=^
Top=3 ∆2, ⑤,B B的左=^ ∆1, ⑤,A ∆0, T,vi PreOrderTraverse(BiTree T,int(*Visit)(TElemType)){ ① if(T) // T=B的左=^ } //当前递归结束，需要从地址栈弹出 下次操作的参数为：∆2, ⑤,B 1 Pop(s,p) Top=2 ∆1, ⑤,A 2 ∆0, T,vi

24 执行∆2, ⑤,B如下： 转第三次递归 ∆2 ⑤PreOrderTraverse(T->rchild,Visit); ∆3 ⑥ }
⑦ } 2 参数为 B 的右=D 1 Top=3 ∆3, ⑥,B ∆1, ⑤,A ∆0, T,vi

25 执行第三次递归 B的右=D PreOrderTraverse(BiTree T,int(*Visit)(TElemType)){
① if(T) // T不空 ② { ③Visit(T->data); //访问D结点 ④PreOrderTraverse(T->lchild,Visit); ∆4 ⑤PreOrderTraverse(T->rchild,Visit); ⑥ } ⑦ } 转第四次递归 参数为 D 的 左=^ 2 1 Top=4 ∆4, ⑤,D Push(s,p) ∆3, ⑥,B ∆1, ⑤,A ∆0, T,vi

26 执行第四次递归 D的左=^ Top=4 ∆4, ⑤,D ∆3, ⑥,B ∆1, ⑤,A PreOrderTraverse(BiTree T,int(*Visit)(TElemType)){ ① if(T) // T=空 因为 ⑦ } //当前递归结束，需要从地址栈弹出 下次操作的参数为： ∆0, T,vi , ∆4, ⑤,D 2 下次操作参数 1 Pop(s,p) Top=3 ∆3, ⑥,B ∆1, ⑤,A ∆1, ⑤,A ∆0, T,vi ∆0, T,vi

27 当前执行操作参数 转第五次递归 参数为 D 的 右=^ ∆4 ⑤PreOrderTraverse(T->rchild,Visit);
Top=2 当前执行操作参数 ∆1, ⑤,A , ∆4, ⑤,D ∆0, T,vi 转第五次递归 参数为 D 的 右=^ ∆4 ⑤PreOrderTraverse(T->rchild,Visit); ∆5 ⑥ } ⑦ } 2 1 Push(s,p) Top=3 ∆5, ⑥,D ∆1, ⑤,A ∆0, T,vi

28 执行第五次递归（D的右=^） ∆5, ⑥,D ∆1, ⑤,A
Top=3 执行第五次递归（D的右=^） ∆5, ⑥,D ∆1, ⑤,A ∆0, T,vi PreOrderTraverse(BiTree T,int(*Visit)(TElemType)){ ① if(T) // T=空 ⑦ } //当前递归结束，需要从地址栈弹出下次操作的参数为： ∆5, ⑥,D 2 1 Pop(s,p) Top=2 ∆1, ⑤,A ∆0, T,vi

29 当前执行操作参数 ∆5, ⑥,D ∆5 ⑥ } ⑦ } //当前递归结束，需要从地址栈弹出 下次操作的参数为： ∆1, ⑤,A 1
Top=2 ∆1, ⑤,A ∆0, T,vi ∆5 ⑥ } ⑦ } //当前递归结束，需要从地址栈弹出 下次操作的参数为： ∆1, ⑤,A 1 Pop(s,p) 2 Top=1 ∆0, T,vi

30 当前的参数为 ∆1, ⑤,A ∆0, T,vi ∆1 ⑤PreOrderTraverse(T->rchild,Visit);
Top=1 ∆0, T,vi ∆1 ⑤PreOrderTraverse(T->rchild,Visit); ∆6 ⑥ } ⑦ } //当前递归结束，需要从地址栈弹出下次操作的参数为： 转第六 次递归 参数为 A 的 右=C 2 1 Push(s,p) Top=2 ∆6, ⑥,A ∆0, T,vi

31 执行第六次递归（A的右=C） ∆6, ⑥,A ∆0, T,vi
Top=2 ∆6, ⑥,A ∆0, T,vi PreOrderTraverse(BiTree T,int(*Visit)(TElemType)){ ① if(T) // T不空,T=C ② { ③Visit(T->data); //访问C结点 ④PreOrderTraverse(T->lchild,Visit); ∆7 ⑤PreOrderTraverse(T->rchild,Visit); ⑥ } ⑦ } 转第七 次递归 参数为 C的 左=^ 2 1 Push(s,p) Top=3 ∆7, ⑤,C ∆6, ⑥,A ∆0, T,vi

32 执行第七次递归（C的左=^） ∆7, ⑤,C ∆6, ⑥,A
Top=3 ∆7, ⑤,C 执行第七次递归（C的左=^） ∆6, ⑥,A ∆0, T,vi PreOrderTraverse(BiTree T,int(*Visit)(TElemType)){ ① if(T) // T=空, 即（C的左=^） ⑦ } //当前递归结束，需要从地址栈弹出 下次操作的参数为： ∆7, ⑤,C 1 Pop(s,p) Top=2 ∆6, ⑥,A ∆0, T,vi

33 ∆8 ⑥ } ⑦ } ∆6, ⑥,A ∆0, T,vi ∆7 ⑤ PreOrderTraverse(T->rchild,Visit);
Top=2 ∆6, ⑥,A ∆0, T,vi 执行当前参数∆7, ⑤,C ∆7 ⑤ PreOrderTraverse(T->rchild,Visit); ∆8 ⑥ } ⑦ } 转第八 次递归 参数为 C的 右=^ 2 1 Push(s,p) Top=3 ∆8, ⑥,C ∆6, ⑥,A ∆0, T,vi

34 执行第八次递归（C的右=^） ∆8, ⑥,C ∆6, ⑥,A ∆0, T,vi
Top=3 ∆8, ⑥,C ∆6, ⑥,A 执行第八次递归（C的右=^） ∆0, T,vi PreOrderTraverse(BiTree T,int(*Visit)(TElemType)){ ① if(T) // T=空 ⑦ } //当前递归结束，需要从地址栈弹出 下次操作的参数为： ∆8, ⑥,C Pop(s,p) Top=2 ∆6, ⑥,A ∆0, T,vi

35 执行∆8, ⑥,C ⑦ } //当前递归结束，需要从地址栈弹出 ∆8 ⑥ } 下次操作的参数为： Pop(s,p) ∆6, ⑥,A
∆8 ⑥ } ⑦ } //当前递归结束，需要从地址栈弹出 下次操作的参数为： ∆6, ⑥,A Pop(s,p) Top=1 ∆0, T,vi

36 此时，栈为空，并且下次的操作参数正好是主函数调用过程语句的下一返回地址：
执行 ∆6, ⑥,A ∆6 ⑥ } ⑦ } //当前递归结束，需要从地址栈弹出 下次操作的参数为： ∆0, T,vi 此时，栈为空，并且下次的操作参数正好是主函数调用过程语句的下一返回地址： ∆0, T,vi。 Top=0

37 #include <stdio.h> int main() { …; PreOrderTraverse(T,vi);
∆0: Printf…; …; } 返回主函数

38 2、中序的遍历算法 若二叉树为空树，则空操作；否则， （1）中序遍历左子树； （2）访问根结点； （3）中序遍历右子树。

39 2、中根遍历算法的递归描述 void Inorder ( BiTree T,int(*Visit)(TElemType) { // 中序遍历二叉树 if (T) { Inorder(bt->lchild); // 遍历左子树 printf(bt->data); // 访问结点 Inorder(bt->rchild);// 遍历右子树 }

40 3、后序遍历二叉树算法 // 后序递归遍历T,对每个结点调用函数Visit一次且仅一次 void PostOrderTraverse(BiTree T,int(*Visit)(TElemType)) { if(T) // T不空 PostOrderTraverse(T->lchild,Visit); // 先后序遍历左子树 PostOrderTraverse(T->rchild,Visit); // 再后序遍历右子树 Visit(T->data); // 最后访问根结点 }

41 五、二叉树的非递归算法——以中序遍历为例
（1）中根遍历二叉树的非递归方法1 p130算法6.2 // 算法6.2 P130 // 采用二叉链表存储结构，Visit是对数据元素操作的应用函数。 // 中序遍历二叉树T的非递归算法(利用栈)，对每个数据元素调用函数Visit int InOrderTraverse1(BiTree T,int(*Visit)(TElemType)) { SqStack S; BiTree p; InitStack(&S); Push(&S,T); // 根指针进栈

42 while(!StackEmpty(S)){
while(GetTop(S,&p) && p ) Push(&S,p->lchild); // 向左走到尽头 Pop(&S,&p); // 空指针退栈 if(!StackEmpty(S)){ // 访问结点,向右一步 Pop(&S,&p); if( !Visit(p->data)) return 0; Push(&S,p->rchild ); } //if } // while printf("\n"); return 1; }//InOrderTraverse1 接p130算法6.2

43 （2）中根遍历二叉树的非递归方法2 p131算法6.3 A C B D // 算法6.3 P131
// 采用二叉链表存储结构，Visit是对数据元素操作的应用函数。 // 中序遍历二叉树T的非递归算法(利用栈)，对每个数据元素调用函数Visit int InOrderTraverse2(BiTree T,int(*Visit)(TElemType)) { SqStack S; InitStack(&S); p=T; while( p || !StackEmpty(S)) Top=0 T A D B C

44 A C B D T p if(p) { // 根指针进栈,遍历左子树 Push(&S,p); p=p->lchild; } else
{ // 根指针退栈,访问根结点,遍历右子树 Pop(&S,&p); if(!Visit(p->data)) return 0; p=p->rchild; } } //if printf("\n"); return 1; } //InOrderTraverse2 T A D B C p

45 六、遍历算法的应用举例 1、统计二叉树中叶子结点的个数 (先序遍历) 2、求二叉树的深度(后序遍历) 3、复制二叉树(后序遍历)
4、建立二叉树的存储结构

46 算法基本思想 1、统计二叉树中叶子结点的个数 先序(或中序或后序)遍历二叉树，在遍历过程中查找叶子结点，并计数。
由此，需在遍历算法中增添一个“计数”的参数，并将算法中“访问结点”的操作改为：若是叶子，则计数器增1。

47 void CountLeaf (BiTree T, int& count){ if ( T ) {
统计二叉树中叶子结点的个数的算法 void CountLeaf (BiTree T, int& count){ if ( T ) { if ((!T->lchild)&& (!T->rchild)) count++; // 对叶子结点计数 CountLeaf( T->lchild, count); CountLeaf( T->rchild, count); } // if } // CountLeaf A D B C

48 2、求二叉树的深度(后序遍历) 首先分析二叉树的深度和它的左、右子树深度之间的关系。
算法基本思想 首先分析二叉树的深度和它的左、右子树深度之间的关系。 从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加1。由此，需先分别求得左、右子树的深度，算法中“访问结点”的操作为：求得左、右子树深度的最大值，然后加 1 。

49 返回二叉树的深度(后序遍历) int BiTreeDepth(BiTree T) { int i,j; if(!T) return 0;
if(T->lchild) i=BiTreeDepth(T->lchild); //递归求深度 else i=0; if(T->rchild) j=BiTreeDepth(T->rchild); else j=0; return i>j ? i+1 : j+1; }

50 3、复制二叉树(后序遍历) 基本操作为：生成一个结点； T NEWT 根元素 根元素 左子树 右子树 左子树 右子树 左子树 右子树

51 生成一个二叉树的结点 (其数据域为item,左指针域为lptr,右指针域为rptr) 复制二叉树(后序遍历)-（1）
BiTNode *GetTreeNode(TElemType item, BiTNode *lptr , BiTNode *rptr ) { if (!(T = (BiTNode*)malloc(sizeof(BiTNode)))) exit(1); T-> data = item; T-> lchild = lptr; T-> rchild = rptr; return T; }

52 复制二叉树(后序遍历)-（2） BiTNode *CopyTree(BiTNode *T) { if (!T ) return NULL;
(1) if (T->lchild ) newlptr = CopyTree(T->lchild);//复制左子树 else newlptr = NULL; //当前不存在左子树 (2) if (T->rchild ) newrptr = CopyTree(T->rchild);//复制右子树 else newrptr = NULL; //当前不存在右子树 newT = GetTreeNode (T->data, newlptr, newrptr); return newT; } // CopyTree

53 4、建立二叉树的存储结构 不同的定义方法相应有不同的存储结构的建立算法 如何将二叉树存入计算机？ 下面以二叉链表的形式将二叉树存入计算机内。

54 A B C   D E  G   F    A 将二叉树按先序遍历次序输入： B D C F E G 需要考虑的两个问题：
问题1：输入结点 “空指针域”的表示方法如何？ * 用空格字符表示‘无孩子’或指针为空； 问题2：以哪种遍历方式来输入与建立该二叉树？ *按照先序遍历建立二叉树较方便。 A B C G F E D 将二叉树按先序遍历次序输入： A B C   D E  G   F   

55 AB C D 例如: 以空白字符“ ”表示 空树 以字符串“A ”表示只含一个根结点的二叉树 按给定的先序序列建立二叉链表 A A B C
以空白字符“ ”表示 空树 以字符串“A ”表示只含一个根结点的二叉树 A AB C D 以下列字符串“ ”表示 A B C D

56 不同的定义方法相应有不同的存储结构的建立算法
(1)构造二叉链表表示的二叉树T（先序遍历）－1 // 用链表存储结构表示二叉树。 typedef char TElemType; typedef struct BiTNode { TElemType data; struct BiTNode *lchild, *rchild; // 左右孩子指针 }BiTNode, *BiTree; lchild data rchild

57 lchild data rchild (1)构造二叉链表表示的二叉树T（先序遍历）－2
// 算法6.4 P131 ( 有改动), 按先序次序输入二叉树中结点的值，构造二叉链表表示的二叉树T, 变量Nil表示空（子）树。 void CreateBiTree(BiTree *T) { TElemType ch;；scanf("%c",&ch); if(ch==Nil) *T=NULL;// 空 else { *T=(BiTree)malloc(sizeof(BiTNode)); if(!*T) return ; (*T)->data=ch; // 生成根结点 CreateBiTree(&(*T)->lchild); // 构造左子树 CreateBiTree(&(*T)->rchild); // 构造右子树 } //else } lchild data rchild

58 (2) 按给定的表达式建相应二叉树 例如：已知表达式 (a+b)×c – d/e 由其对应的前缀表示式-×+ a b c / d e建树

59 / + - × c d e a b 对应前缀表达式 -×+ a b c / d e的二叉树如下： 该二叉树的特点—— （1）操作数为叶子结点
（2）运算符为分支结点

60 由前缀表示式建树的算法的基本操作—— scanf(&ch); if ( In(ch, 字母集 )) 建叶子结点; else { 建根结点;
递归建左子树; 递归建右子树; } 根据该二叉树的特点分别建立叶子结点、根结点、左右子树 （1）操作数为叶子结点 （2）运算符为分支结点

61 + + + / + a+b (a+b)×c × c a b a b a+b×c (a+b)×c – d/e - × a × c d e b
分析表达式和二叉树的关系—— a+b (a+b)×c × + + c a b a b a+b×c (a+b)×c – d/e - + × / a × + c d e b c a b

62 基本操作—— scanf(&ch); if (In(ch, 字母集 )) { 建叶子结点; 暂存; }
else if (In(ch, 运算符集)) { 和前一个运算符比较优先数; 若当前的优先数“高”，则暂存; 否则建子树; }

63 void CrtExptree(BiTree &T, char exp[] ) {
InitStack(S); Push(S, #); InitStack(PTR); p = exp; ch = *p; while (!(GetTop(S)==# && ch==#)) { if (!IN(ch, OP)) CrtNode( t, ch ); // 建叶子结点并入栈 else { } if ( ch!= # ) { p++; ch = *p;} } // while Pop(PTR, T); } // CrtExptree 建子树… …

64 switch (ch) { case ( : Push(S, ch); break; case ) : Pop(S, c); while (c!= ( ) { CrtSubtree( t, c); // 建二叉树并入栈 Pop(S, c) } break; defult : } // switch … …

65 while(!Gettop(S, c) && ( precede(c,ch))) {
CrtSubtree( t, c); Pop(S, c); } if ( ch!= # ) Push( S, ch); break;

66 建叶子结点的算法为： void CrtNode(BiTree& T,char ch) { T=(BiTNode*)malloc(sizeof(BiTNode)); T->data = char; T->lchild = T->rchild = NULL; Push( PTR, T ); }

67 建子树的算法为： void CrtSubtree (Bitree& T, char c) {
T=(BiTNode*)malloc(sizeof(BiTNode)); T->data = c; Pop(PTR, rc); T->rchild = rc; Pop(PTR, lc); T->lchild = lc; Push(PTR, T); }

68 由二叉树的先序和中序序列建树 仅知二叉树的先序序列“abcdefg” 不能唯一确定一棵二叉树， 如果同时已知二叉树的中序序列“cbdaegf”，则会如何？ 二叉树的先序序列 根 {左子树} {右子树} 二叉树的中序序列 {左子树} 根 {右子树}

69 a a a b c d e f g b c d e f g c c b d a e g f b d e g f 例如: ^ ^ ^ ^ ^
先序序列中序序列 c c b d a e g f b d a e g f a b ^ e ^ c ^ ^ d ^ f ^ ^ g ^

70 … … void CrtBT(BiTree& T, char pre[], char ino[],
int ps, int is, int n ) { // 已知pre[ps..ps+n-1]为二叉树的先序序列， // ins[is..is+n-1]为二叉树的中序序列，本算 // 法由此两个序列构造二叉链表 if (n==0) T=NULL; else { k=Search(ino, pre[ps]); // 在中序序列中查询 if (k== -1) T=NULL; else { } } // } // CrtBT … …

71 T=(BiTNode*)malloc(sizeof(BiTNode)); T->data = pre[ps]; //生成根结点
接上述的else { … … }部分 T=(BiTNode*)malloc(sizeof(BiTNode)); T->data = pre[ps]; //生成根结点 if (k==is) T->Lchild = NULL; else CrtBT(T->Lchild, pre[], ino[], ps+1, is, k-is ); if (k=is+n-1) T->Rchild = NULL; else CrtBT(T->Rchild, pre[], ino[], ps+1+(k-is), k+1, n-(k-is)-1 ); } Return ok; } //CreateBitree

72 线索二叉树 一、何谓线索二叉树？ 二、线索链表的遍历算法 三、如何建立线索链表？

73 一、何谓线索二叉树？ 遍历二叉树的结果是: 求得结点的一个线性序列。 在二叉树的先序、中序或后序遍历序列中两个相邻的结点互称为前驱与后继。
指向前驱或后继结点的指针称为线索。 包含“线索”的存储结构，称作“线索链表” 加上线索的二叉链表表示的二叉树叫线索二叉树。 对二叉树按某种遍历次序使其变为线索二叉树的过程叫线索化。

74 实现：在有n个结点的二叉链表中必定有n+1个空指针域。
对线索链表中结点的约定： 在二叉链表的结点中增加两个标志域： 若该结点的左子树不空，则lchild域指针指向其左子树，且左标志域的值为０,即“指针 Link”； 否则，lchild域指向其“前驱”， 　且左标志域的值为１，即“线索 Thread”。

75 若该结点的右子树不空，则rchild域指针指向其右子树，且右标志域的值为０，即“指针 Link” ；
　且右标志域的值为1，即“线索 Thread” 。

76 线索二叉树： lchild ltag 数据 rtag rchild tag=0 孩子 tag=1 线索
其中: ltag= 0 lchild 域指示结点的左孩子 rtag= 0 rchild 域指示结点的右孩子 ltag= l lchild 域指示结点的前驱 rtag= 1 rchild 域指示结点的后驱 当以二叉链表作为存储结构时,只能找到结点的左右孩子的信息,而不能找到结点的任一序列的前驱与后继信息,这种信息只有在遍历的动态过程中才能得到,为了能保存所需的信息,可增加两个标志域; 对线索链表中结点的约定：在二叉链表的结点中增加两个标志域，并作如下规定：若该结点的左子树不空， 则lchild域的指针指向其左子树， 且左标志域的值为 0“指针 Link” ； 否则，lchild域的指针指向其“前驱”， 且左标志的值为1“线索 Thread” 。 若该结点的右子树不空， 则rchild域的指针指向其右子树， 且右标志域的值为0 “指针 Link”； 否则，rchild域的指针指向其“后继”， 且右标志的值为1“线索 Thread”。如此定义的二叉树的存储结构称作“线索链表”。

77 线索链表的类型描述： typedef enum { Link, Thread } PointerThr;
typedef struct BiThrNod { TElemType data; struct BiThrNode *lchild, *rchild; // 左右指针 PointerThr LTag, RTag; // 左右标志 } BiThrNode, *BiThrTree;

78 ^ 先序序列：ABCDE 先序线索二叉树 ^ lchild LTag data RTag rchild A B D C E T A B C
A B C D E 1 1 1 1 1 1 ^ T 0 A 0 1 B 0 1 C 1 0 D 1 1 E 1 ^

79 A B D C E T 中序序列：BCAED 中序线索二叉树 A B C D E ^ 1 1 ^ 1 1 1 1

80 A B D C E T 后序序列：CBEDA 后序线索二叉树 A B C D E 1 1 ^ 1 1 1 1

81 二、线索链表的遍历算法

82 A B C D E A B D C E T 中序序列：BCAED 中序线索二叉树 1 ^ 头结点：LTag=0, lchild指向根结点。RTag=1, rchild指向遍历序列中最后一个结点。 遍历序列中第一个结点的lchild域和最后一个结点的rchild域都指向头结点。 0 A 0 1 B 0 0 D 1 1 C 1 1 E 1 T 中序序列：BCAED 带头结点的中序线索二叉树

83 线索化链表的遍历算法： 遍历的第一个结点？ 在线索化链表中结点的后继？ for (p=firstNode(T);p;p=succ(p))
Visit(p); 线索化链表的遍历算法： 遍历的第一个结点？ 在线索化链表中结点的后继？

84 { p = p->rchild; Visit(p->data); // 访问后继结点
例1:中序线索化链表的遍历算法的核心 （1） 中序遍历的第一个结点在树的何位置？ 左子树上处于“最左下”（没有左子树）的结点。对应 的语句是： while (p->LTag==Link) p = p->lchild; // 第一个结点 （2）中序线索化链表中结点的后继指的是什么？ 若无右子树，则为后继线索所指结点； 否则为对其右子树进行中序遍历时访问的第一个结点。 while (p->RTag==Thread && p->rchild!=T) { p = p->rchild; Visit(p->data); // 访问后继结点 } p = p->rchild; // p进至其右子树根…

85 void InOrderTraverse_Thr(BiThrTree T,
void (*Visit)(TElemType e)) ① {p = T->lchild; // p指向根结点 ② while (p != T) { // 空树或遍历结束时，p==T ③ while (p->LTag==NULL) p = p->lchild; // 第一个结点 ④ Visit(p->data); ⑤ while ( p->RTag==Thread && p->rchild!=T ) ⑥ { p = p->rchild; Visit(p->data); // 访问后继结点 } ⑦ p = p->rchild; // p进至其右子树根 ⑧ } ⑨ } // InOrderTraverse_Thr

86 ①{ p = T->lchild; // p指向根结点<A>
②{while (p != T) {// 空树或遍历结束时，p==T 头结点：LTag=0, lchild指向根结点。RTag=1, rchild指向遍历序列中最后一个结点。 遍历序列中第一个结点的lchild域和最后一个结点的rchild域都指向头结点。 0 A 0 1 B 0 0 D 1 1 C 1 1 E 1 T 中序序列：BCAED 带头结点的中序线索二叉树 p A

87 typedef enum { Link, Thread } PointerThr;
③ while (p->LTag==Link) p = p->lchild; // 第一个结点=B ④ Visit(p->data); // 访问B typedef enum { Link, Thread } PointerThr; // Link==0:指针，Thread==1:线索 0 A 0 1 B 0 0 D 1 1 C 1 1 E 1 T 中序序列：BCAED 带头结点的中序线索二叉树 p A lchild ltag data rtag rchild

88 typedef enum { Link, Thread } PointerThr;
⑤ while ( p->RTag==Thread && p->rchild!=T ) // 不满足条件， 执行 ⑦ p = p->rchild; // p进至其右子树根 // p=“B的右”= <C> ⑧ } ② while (p != T) { 0 A 0 1 B 0 0 D 1 1 C 1 1 E 1 T 中序序列：BCAED 带头结点的中序线索二叉树 typedef enum { Link, Thread } PointerThr; // Link==0:指针，Thread==1:线索 p A lchild ltag data rtag rchild

89 typedef enum { Link, Thread } PointerThr;
② while (p != T) { //p=<c> Visit(p->data); //访问C ⑤ while ( p->RTag==Thread && p->rchild!=T ) // 满足条件 ⑥ { p = p->rchild; Visit(p->data); // 访问后继A } 0 A 0 1 B 0 0 D 1 1 C 1 1 E 1 T 中序序列：BCAED 带头结点的中序线索二叉树 typedef enum { Link, Thread } PointerThr; // Link==0:指针，Thread==1:线索 p A lchild ltag data rtag rchild

90 typedef enum { Link, Thread } PointerThr;
⑦ p = A->rchild=<D> ; // p进至其右子树根= A->rchild=<D> ⑧ } ② while (p != T) { typedef enum { Link, Thread } PointerThr; // Link==0:指针，Thread==1:线索 0 A 0 1 B 0 0 D 1 1 C 1 1 E 1 T 中序序列：BCAED 带头结点的中序线索二叉树 A p lchild ltag data rtag rchild

91 typedef enum { Link, Thread } PointerThr; // Link==0:指针，Thread==1:线索
⑧ } ② while (p != T) { ② while (p != T) { //p=<D> ③ while (p->LTag==NULL) p = p->lchild; //第一个结点=“ D的左”=E ④ Visit(p->data); //访问E ⑤ while ( p->RTag==Thread && p->rchild!=T ) // 满足条件 0 A 0 1 B 0 0 D 1 1 C 1 1 E 1 T 中序序列：BCAED 带头结点的中序线索二叉树 typedef enum { Link, Thread } PointerThr; // Link==0:指针，Thread==1:线索 A p lchild ltag data rtag rchild

92 typedef enum { Link, Thread } PointerThr; // Link==0:指针，Thread==1:线索
⑤ while ( E->RTag==Thread && E->rchild!=T ) // 满足条件 ⑥ { p = E->rchild=D; Visit(p->data); // 访问后继D } ⑦ p = D->rchild=T; // p进至其右子树根=“ D的右”=T ⑧ } 0 A 0 1 B 0 0 D 1 1 C 1 1 E 1 T 中序序列：BCAED 带头结点的中序线索二叉树 typedef enum { Link, Thread } PointerThr; // Link==0:指针，Thread==1:线索 A p lchild ltag data rtag rchild

93 ⑦ p = D->rchild=T; // p进至其右子树根=“ D的右”=T
⑧ } ② while (p != T) { // 空树或遍历结束时，p==T 0 A 0 1 B 0 0 D 1 1 C 1 1 E 1 T 中序序列：BCAED 带头结点的中序线索二叉树 p A lchild ltag data rtag rchild

94 三、如何建立线索链表？ 在中序遍历过程中修改结点的左，右指针域，以保存当前访问结点的“前驱”和“后继”信息。遍历过程中，指针pre始终指向刚刚访问过的结点，若指针p并始终使其指向当前访问的结点，则pre指向它的前驱。 A B D C E T 中序序列：BCAED 中序线索二叉树 1 ^ pre p

95 按中序线索化二叉树 P->A A B C D E pre thrt A B D C E T ^ p

96 P->A P->B A B C D E pre thrt A B D C E T ^ p

97 P->A P->B A B C D E pre thrt A B D C E T ^ P=NULL

98 P->A A B C D E pre thrt A B D C E T ^ P 1

99 P->A A B C D E P->C thrt A B D C E T ^ 1 pre P

100 P->A A B C D E P->C thrt A B D C E T ^ 1 pre P=NULL

101 P->A A B C D E thrt A B D C E T ^ 1 pre P 1

102 P->A A B C D E thrt A B D C E T ^ 1 pre P=NULL

103 A B C D E thrt A B D C E T ^ P 1 pre 1

104 A B C D E P->D thrt A B D C E T ^ pre 1 P

105 A B C D E P->E P->D thrt A B D C E T ^ pre 1 P

106 A B C D E P->E P->D thrt A B D C E T ^ pre 1 P=NULL

107 A B C D E P->D thrt A B D C E T ^ pre 1 P 1

108 A B C D E P->D thrt A B D C E T ^ 1 pre P=NULL

109 A B C D E thrt A B D C E T ^ 1 P pre 1

110 A B C D E thrt A B D C E T ^ 1 pre 1 P=NULL

111 A B C D E A B D C E thrt 1

112 Status InOrderThreading(BiThrTree &Thrt, BiThrTree T) {
// 中序遍历二叉树T，并将其中序线索化，Thrt指向头结点。 if (!(Thrt = (BiThrTree)malloc(sizeof(BiThrNode)))) exit (OVERFLOW); Thrt->LTag = Link; Thrt->RTag =Thread; // 建头结点 Thrt->rchild = Thrt; // 右指针回指 if (!T) Thrt->lchild = Thrt; // 若二叉树空，则左指针回指 else { Thrt->lchild = T; pre = Thrt; InThreading(T); // 中序遍历进行中序线索化 pre->rchild = Thrt; pre->RTag = Thread; // 最后一个结点线索化 Thrt->rchild = pre; } return OK; } // InOrderThreading

113 pre 1 p 1 void InThreading(BiThrTree p) { if (p) {
InThreading(p->lchild); // 左子树线索化 if (!p->lchild) { p->LTag = Thread; p->lchild = pre; } // 建前驱线索 if (!pre->rchild) { pre->RTag = Thread; pre->rchild = p; } // 建后继线索 pre = p; // 保持pre指向p的前驱 InThreading(p->rchild); // 右子树线索化 } } // InThreading pre 1 p 1