第六章 树和二叉树

主要内容 1、树的定义和基本术语 2、二叉树 3、遍历二叉树和线索二叉树 4、树和森林 5**、树和等价问题 6、赫夫曼树及其与树的应用 7**、回溯法与树的遍历 8**、树的计数

先序遍历(D L R): 若二叉树为空，则空操作否则 访问根结点，按先序遍历左子树，按先序遍历右子树。 6.3、遍历二叉树和线索二叉树 树的遍历就是按某种次序访问树中的结点，要求每个结点访问一次且仅访问一次。 （遍历定义及遍历算法 按先左后右的原则，一般使用三种遍历： 先序遍历(D L R): 若二叉树为空，则空操作否则 访问根结点，按先序遍历左子树，按先序遍历右子树。 中序遍历(L D R):若二叉树为空，则空操作否则 按中序遍历左子树，访问根结点，按中序遍历右子树。 后序遍历(L R D):若二叉树为空，则空操作否则 按后序遍历左子树，按后序遍历右子树，访问根结点。 二叉树为空时，执行空操作，即空二叉树已遍历完。

（2）遍历算法 D L R 先序遍历：D L R 中序遍历：L D R 后序遍历：L R D ABDC D L R A D L R BDAC DBCA B > D L R C > > A C B D > > T1 T3 D 以先序遍历D L R为例演示遍历过程 T2

遍历二叉树 R 1、遍历二叉树：设 D 代表根节点，L 代表左子树，R 代表右子树。 a. 先序：如果二叉树为空，则操作为空：否则访问根结点；先序遍历左子树； 先序遍历右子树。记为：DLR。 b. 中序： 如果二叉树为空，则操作为空：否则中序遍历左子树；访问根结点； 中序遍历右子树。记为：LDR。 c. 后序： 如果二叉树为空，则操作为空：否则后序遍历左子树；后序遍历右子 树；访问根结点。记为：LRD。 先序：A、L、B、E、 C、D、W、X B C D E L A X W R B C D E L A X W 中序：B、L、E、A、 C、W、X、D 后序：B、E、L、X、 W、D、C、A

遍历二叉树 A A 先序：A、L、B、E、C、D、W、X L C 中序：B、L、E、A、C、W、X、D L C 1、遍历二叉树：续 a. 先序分析：结点的左儿子、左孙子、左后代、…… 将连续输出。结点的右儿子将在结点的左 子树全部输出之后才输出。 b. 中序分析：最先输出的结点是根结点的最左的左后代。将二叉树中的结点投影到水平轴线上，则得到 中序遍历的序列。 c. 后序分析：根结点（或子树的根结点）将在它的左、右子树的结点输出之后。因此，根结点（或子树 的根结点）在中序序列中的序号等于它的左右子树的结点个数 ＋左右子树中的最先被访问 的结点的序号。注意，结点、右父亲、右祖父、…… 将连续输出。 A A 先序：A、L、B、E、C、D、W、X L C 中序：B、L、E、A、C、W、X、D L C 后序：B、E、L、X、W、D、C、A B E D D B E W W X X B L E A C W X D

A B C > > > D > > Void PreOderTraverse(BiTree T){ printf(A); pre(T L); A Void PreOderTraverse(BiTree T){ if(T! =NULL){ printf (T->data); PreOrderTraverse(T->lchild); PreOrderTraverser(T->rchild); } }/*先序遍历*/ pre(T R); T B printf(B); pre(T L); T C printf(C); pre(T L); B C T > 左是空返回 pre(T R); T > 左是空返回 T > 右是空返回 T D printf(D); pre(T L); D 返回 T > 左是空返回 T > 右是空返回 主程序 Pre( T ) 返回 pre(T R); 返回 返回 pre(T R); 返回

中序遍历二叉树的递归算法： void inOrderTraverse(BiTree T) { if(T!=NULL) { inOrderTraverse(T->lchild); printf(T->data); inOrderTraverse(T->rchild); } 后序遍历二叉树的递归算法： void PostOrderTraverse(BiTree T) { if(T!=NULL) { PostOrderTraverse(T->lchild); PostOrderTraverse(T->rchild); printf(T->data); }

练习 1 3 2 5 4 8 6 7 按照先序，中序，后序遍历如图 所示二叉树，写出遍历结果序列 先序：12467358 中序：26471583 后序：67428531

 （3）遍历二叉树的应用 1) 建立一棵二叉树 (在遍历过程生成结点，建立二叉树的存储结构，用链式存储结构） A D B C BiTree CreatBiTree() { BiTree T; scanf(&ch); if(ch= = ) T=NULL; else{ T=(BiTNode)malloc(sizeof((BiTNode)); T->data=ch; /*生成根结点*/ T->lchild= CreatBiTree( ); /*构造左子树*/ T->rchild= CreatBiTree(); /*构造右子树*/ } return (T) ;} 按先序遍历 A B D C A B Φ D Φ Φ C Φ Φ

ch=B T B creat(T L) T ch=Φ B ch=A T A creat(T L) T= Λ, Creat(T) 返回 T D Λ || = creat(T R) ch=D T D creat(T L) = || Φ creat(T R) T C Λ ch=Φ – + ch=C T C creat(T L) – + 返回 返回 D = T ch=Φ Λ creat(T R) T C Λ ch=Φ + creat(T R) A B Λ D C – + A B Λ D C A B Λ D || = A B Λ D B Φ A A B Φ Λ A T 返回 返回

typedef struct node{ int data； struct node *L，*R； }NODE； 例.试以二叉链表作为存储结构，将二叉树中所有结点的左右子树进行交换。 void change(NODE *T) {NODE *m; if(T!=NULL) { m=T->L T->L=T->R; T->R=m; change(T->L); change(T->R);} } A B C D A C B D A C B D

a b c g typedef struct BiTNode{ int data;   typedef struct BiTNode{ int data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; int preprn(BiTtree T) { if((T->lchild!=NULL)&&（T->rchild!=NULL）) { printf(T->data); preprn(T->lchild); preprn(T->rchild); } else return OK; 阅读程序并回答问题： （1）    程序执行了什么功能？ （2）    针对右面的图，写出程序的运行结果。 a b c d e f g i h a b c g

遍历二叉树的非递归算法 1、根结点进栈 2、结点出栈，被访问 3、结点的右、左儿子（非空）进栈 4、反复执行 2、3 ，至栈空为止。 1、遍历二叉树：续 先序的程序实现： 1、根结点进栈 2、结点出栈，被访问 3、结点的右、左儿子（非空）进栈 4、反复执行 2、3 ，至栈空为止。 e.g: 先序：A、L、B、E、C、D A L C D B E D出栈访问 后，栈空结 束 C、L 进栈 E、B 进栈 D进栈 A进栈 A出栈访问 L出栈访问 B出栈访问 E出栈访问 C出栈访问 <B> <L> <E> <E> <A> <C> <C> <C> <C> <C> <D>

先序遍历的非递归实现 void NRPreOrder（BiTree bt） {/*非递归先序遍历二叉树*/ BiTree stack[MAXNODE], p; int top;//栈顶指针 if (bt==NULL) return; top=0; p=bt; while(!(p==NULL&&top==0)) { while(p!=NULL) { Visite(p->data); /*访问结点的数据域*/ if (top<MAXNODE-1) /*将当前指针p压栈*/ { stack[top]=p; top++;} else { printf(“栈溢出”)； return；} p=p->lchild； /*指针指向p的左孩子*/ } if (top<=0) return; /*栈空时结束*/ else{ top--; p=stack[top]; /*从栈中弹出栈顶元素*/ p=p->rchild; /*指针指向p的右孩子结点*/

遍历二叉树的非递归算法 1、结点（初始时是根结点）进栈，沿左指针查找左儿子。 2、若有左儿子，返回第一步。 1、中序遍历二叉树实现： 1、结点（初始时是根结点）进栈，沿左指针查找左儿子。 2、若有左儿子，返回第一步。 3、若无左儿子，判栈空？空则结束。非空，栈顶结点出栈 访问。转向右子树，返回1。 e.g: A initstack(s);push(s,t); // t 是根结点 while (!stackempty(s)) { while (Gettop(s,p)) && p ) // 有值且非空时 push(s, p->lchild)； // null 值可能进栈 pop (s,p); // 空指针退栈 if (!stackempty(s)) // 访问结点，向右一步 { pop(s, p); visit( p->data); push(s,p->rchild); } L C D B E W 中序：B、L、E、 A、C、W、 X、D X

中序遍历的非递归算法 中序遍历的非递归算法 void InOrderTraverse(BiTree T){ //采用二叉链表存储结构，Visit是对数据元素操作的应用函数。 //中序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit。 InitStack(S)； P = T； While(P || !Sempty(S)){ While(P) { Push(S,P)； P = P->lchild； //向左走到尽头 }//While If(!Sempty(S)){ Pop(S,P)； Visit(P->data)； P = P->rchild； //访问结点，向右一步 }//if }//InOrderTraverse

遍历二叉树的非递归算法 node数组 Lchild dada rchild … initstack(s); p = t; // t 是根结点 后序遍历非递归的算法实现： 1、结点（初始时是根结点）进栈（正值），沿左指针查找左子树。 2、左子树处理完毕，退栈。若为正值转 3 ，否则转 4。 3、负值进栈处理右子树，转向 1 4、处理根结点（应恢复正值），返回 2 5、反复 1 到 5 ，至栈空为止。 node数组 Lchild dada rchild 0123 24 A 3 L 5 C 6 … initstack(s); p = t; // t 是根结点 do { while ( p != 0 ) // 有值且非空时 { push(s, p)；p = node[p].lchild; } if (!stackempty(s)) { pop(s, p); if ( p > 0 ) { push(s, -p)；p = node[p].rchild; }; else { p=-p; visit( node[p].data ); p = 0;} } } while (p != 0 !! ( !stackempty(s) ) e.g: A L C D B E W 后序：B、E、L、X、 W、D、C、A X

后序遍历非递归的算法实现 后序遍历与先序遍历和中序遍历不同，在后序遍历过程中，结点在第一次出栈后，还需再次入栈，也就是说，结点要入两次栈，出两次栈，而访问结点是在第二次出栈时访问。因此，为了区别同一个结点指针的两次出栈，设置一标志flag，若flag=1 第一次出栈，结点不能访问;flag=2 第二次出栈，结点可以访问；当结点指针进、出栈时，其标志flag也同时进、出栈。因此，可将栈中元素的数据类型定义为指针和标志flag合并的结构体类型 typedef struct { BiTree link; int flag; }stacktype; 在算法中，一维数组stack[MAXNODE] 用于实现栈的结构，指针变量p指向当前 要处理的结点， 整型变量top用来表示当前栈顶的位置， 整型变量sign为结点p的标志量。

void NRPostOrder(BiTree bt) { stacktype stack[MAXNODE]; BiTree p; int top,sign; if (bt==NULL) return; top=0 /*栈顶位置初始化*/ p=bt; while (!(p==NULL && top==0)) { if (p!=NULL) /*结点第一次进栈*/ { top++; stack[top].link=p; stack[top].flag=1; p=p->lchild; /*找该结点的左孩子*/ } else { p=stack[top].link; sign=stack[top].flag; top--; if (sign==1) /*结点第二次进栈*/ {top++; stack[top].link=p; stack[top].flag=2; /*标记第二次出栈*/ p=p->rchild; else { Visite(p->data); /*访问该结点数据域值*/ p=NULL; } } }}

二叉树的重建 1、二叉树的确定 先序（后序） ＋ 中序 唯一确定一棵二叉树, 但是先序+后序则不能确定一棵树 e.g: 先序: A、B、D、E、F、C 中序: D、B、E、F、A、C 先序: A、B、D、E、F、C 中序: D、B、E、F、A、C 确定过程: 1、 定根 A 2、在中序序列中找到 A 3、中序序列中的 A 的左部为 A 的左子树 上的所有结点， A 的右部为 A 的右子 树中的所有结点。 4、根据 A 的左子树的所有结点的先序序 列确定 A 的左子树的根节点，它是 A 的左儿子。 5、根据 A 的右子树的所有结点的先序序 列确定 A 的右子树的根节点，它是 A 的右儿子。 6、 在左、右子树中反复以上过程。至所有 结点处理完毕。结束 先序: A、B、D、E、F、C 中序: D、B、E、F、A、C A B C 先序: B、D、E、F 中序: D、B、E、F D E 先序: E、F 中序: E、F F

建树的递归算法的思想 ： 先根据先序序列的第一个元素建立根结点；然后在中序序列中找到该元素，确定根结点的左、右子树的中序序列；再在先序序列中确定左、右子树的先序序列；最后由左子树的先序序列与中序序列建立左子树，由右子树的先序序列与中序序列建立右子树 。 下面给出用C语言描述的该算法。假设二叉树的先序序列和中序序列分别存放 在一维数组preod[ ]与inod[ ]中，并假设二叉树各结点的数据值均不相同 void ReBiTree（char preod[ ],char inod[ ],int n,BiTree root） /*n为二叉树的结点个数，root为二叉树根结点的存储地址*/ { if (n≤0) root=NULL; else PreInOd(preod,inod,1,n,1,n,&root); } void PreInOd（char preod[ ],char inod[ ],int i,j,k,h,BiTree *t） {* t=(BiTNode *)malloc(sizeof(BiTNode)); *t->data=preod[i]; m=k; while (inod[m]!=preod[i]) m++; if (m==k) *t->lchild=NULL else PreInOd(preod,inod,i+1,i+m-k,k,m-1,&t->lchild); if (m==h) *t->rchild=NULL else PreInOd(preod,inod,i+m-k+1,j,m+1,h,&t->rchild); }//数组preod和inod的元素类型可根据实际需要来设定，这里设为字符型

练习：已知一棵二叉树的先序序列与中序序列分别为： A B C D E F G H I B C A E D G H F I 试恢复该二叉树

6.3.2 线索二叉树 (Threaded Binary Tree) 对二叉树遍历的过程实质上是对一个非线性结构进行线性化的操作. 以二叉链表为存储结构时,结点的左右孩子可以直接找到,但不能直接找到结点的前驱和后继,而结点的前驱和后继只有在遍历二叉树的过程中才能得到. 用二叉链表表示的二叉树中,n个结点的二叉树有n+1个空链域，可利用这些空链域存储结点的前驱或后继。

LTag=0, LChild域指示结点的左孩子 LTag=1, LChild域指示结点的前驱 RTag=0, RChild域指示结点的右孩子 data LTag RTag 结点结构 LTag=0, LChild域指示结点的左孩子 LTag=1, LChild域指示结点的前驱 RTag=0, RChild域指示结点的右孩子 RTag=1, RChild为域结点的后继

以这种结点结构构成的二叉链表作为二叉树的存储结构，叫做线性链表。 线索：指向结点前驱和后继的指针。 线索二叉树：加上线索的二叉树 线索化： 对二叉树以某种次序遍历使其变为线索二叉树 的过程

线索二叉树 1.线索化二叉树 线索二叉树

在二叉树的结点的标准形式中，增加两个标志域，用于区别是否是穿线。如下所 示： 1、线索二叉树： 中序穿线树（中序线索二叉树）的实现： 在二叉树的结点的标准形式中，增加两个标志域，用于区别是否是穿线。如下所 示： 其中 data 为数据域，ltag = 0 时，lchild 域指向本结点的左儿子 ltag = 1 时，lchild 域指向本结点的按中序遍历序列的前驱结点 ltag = 0 时，rchild 域指向本结点的右儿子 ltag = 1 时，rchild 域指向本结点的按中序遍历序列的后继结点 Lchild ltag data rtag rchild e.g: n = 6 的二叉树 无前驱结点 无后继结点 A A 中序线索二叉树 L C L C D D B E B E

新增头结点 中序线索链表 A 表示 L C D B E 1、线索二叉树： 中序线树中的结点的数据结构： 1 无前驱结点 无后继结点 A L 1 无前驱结点 无后继结点 A 中序线索链表 表示 L C A D B E L 1 1 C 1 B 1 1 E 1 1 D 1

L A E B L C A D B E D 1、线索二叉树： 在中序线索二叉树上进行中序遍历、不用堆栈的的算法及程序要点： 1、最先输出最左的结点 2、结点无右后继，则该结点的中序的后继结点，由右儿子的指针域给出。但要注意以下情况： 3、结点有右儿子，则该结点的中序的后继结点，是它的右子树中的最左的结点。 4、最先输出的结点无前驱结点，最后输出的结点无后继结点。 无前驱结点 无后继结点 L A E B L C A D B E 指向当前结点 D 指向后继结点

中序线索二叉树方法： 1：中序遍历树 2：然后对每一个结点进行判定。如果该结点无左孩子，则加上前驱线索，若无右孩子，则加上后继线索。如果该结点有左右孩子，则不添加线索。

在中序线索二叉树上进行中序遍历、不用堆栈的程序实现//link=0,thread=1 1、线索二叉树： 在中序线索二叉树上进行中序遍历、不用堆栈的程序实现//link=0,thread=1 B D E L A Status inorderTraverse_Thr(BiThrTree T, status( * Visit ) (TElemType e ) ) { p = T-> lchild; while ( P != T ) { while ( p->Ltag == Link ) p = p->lchild; Visit ( p-> data); while ( p->rtag == Thread && p->rchild != T ) { p = p->rchild ; Visit ( p-> data) ;} p = p->rchild ; } return OK; 指向当前结点 指向后继结点

1 2 3 4 7 8 6 5 练习 分别画出如图所示的二叉树进行 先序，中序，后序线索化以后的 线索二叉树

线索二叉树的操作 1．建立一棵中序线索二叉树 下面以中序线索二叉树为例，讨论线索二叉树的建立、线索二叉树的遍历以及在线索二叉树上查找前驱结点、查找后继结点、插入结点和删除结点等操作的实现算法 1．建立一棵中序线索二叉树 建立线索二叉树，或者说对二叉树线索化，实质上就是遍历一棵二叉树。在遍历过程中，访问结点的操作是检查当前结点的左、右指针域是否为空，如果为空，将它们改为指向前驱结点或后继结点的线索。为实现这一过程，设指针pre始终指向刚刚访问过的结点，即若指针p指向当前结点，则pre指向它的前驱，以便增设线索。 另外，在对一棵二叉树加线索时，必须首先申请一个头结点，建立头结点与二叉树的根结点的指向关系，对二叉树线索化后，还需建立最后一个结点与头结点之间的线索。

下面是建立中序线索二叉树的递归算法，其中pre为全局变量 int InOrderThr(BiThrTree *head,BiThrTree T) {/*中序遍历二叉树T，并将其中序线索化，*head指向头结点。*/ if (!(*head =(BiThrNodeType*)malloc(sizeof(BiThrNodeType)))) return 0; (*head)->ltag=0; (*head)->rtag=1; /*建立头结点*/ (*head)->rchild=*head; /*右指针回指*/ if (!T) (*head)->lchild =*head; /*若二叉树为空，则左指针回指*/ else { (*head)->lchild=T; pre= head; InThreading(T); /*中序遍历进行中序线索化*/ pre->rchild=*head; pre->rtag=1; /*最后一个结点线索化*/ (*head)->rchild=pre; } return 1;

中序遍历进行中序线索化 函数 void InTreading(BiThrTree p) {/*中序遍历进行中序线索化*/ if (p) { InThreading(p->lchild); /*左子树线索化*/ if (!p->lchild) /*前驱线索*/ { p->ltag=1; p->lchild=pre; } if (!pre->rchild) /*后继线索*/ { pre->rtag=1; pre->rchild=p; pre=p; InThreading(p->rchild); /*右子树线索化*/

2．在中序线索二叉树上查找任意结点的中序前驱结点 对于中序线索二叉树上的任一结点，寻找其中序的前驱结点，有以下两种情况： （1）如果该结点的左标志为1，那么其左指针域所指向的结点便是它的前驱结点； （2）如果该结点的左标志为0，表明该结点有左孩子，根据中序遍历的定义，它的前驱结点是以该结点的左孩子为根结点的子树的最右结点，即沿着其左子树的右指针链向下查找，当某结点的右标志为1时，它就是所要找的前驱结点

在中序线索二叉树上寻找结点p的中序前驱结点的算法如下 BiThrTree InPreNode（BiThrTree p） {/*在中序线索二叉树上寻找结点p的中序前驱结点*/ BiThrTree pre; pre=p->lchild; if (p->ltag!=1) while (pre->rtag==0) pre=pre->rchild; return(pre); }

3 在中序线索二叉树上查找任意结点的中序后继结点 对于中序线索二叉树上的任一结点，寻找其中序的后继结点，有以下两种情况： （1）如果该结点的右标志为1，那么其右指针域所指向的结点便是它的后继结点； （2）如果该结点的右标志为0，表明该结点有右孩子，根据中序遍历的定义，它的前驱结点是以该结点的右孩子为根结点的子树的最左结点，即沿着其右子树的左指针链向下查找，当某结点的左标志为1时，它就是所要找的后继结点。

在中序线索二叉树上寻找结点p的中序后继结点的算法如下 BiThrTree InPostNode（BiThrTree p） {/*在中序线索二叉树上寻找结点p的中序后继结点*/ BiThrTree post; post=p->rchild; if (p->rtag!=1) while (post->rtag==0) post=post->lchild; return(post); } 以上给出的仅是在中序线索二叉树中寻找某结点的前驱结点和后继结点的算法。 在先序线索二叉树中寻找结点的后继结点以及在后序线索二叉树中寻找结点的 前驱结点可以采用同样的方法分析和实现。在此就不再讨论了

A B C D E F L G H I J M 作业 K 1 如图所示的二叉树 的（a）画出其顺序存储和二叉链表 结点，指出该二叉树的深度 (c)分别写出该二叉树的先序，中序， 后序遍历序列。 2 编写一个算法统计二叉树 中叶子结点的个数 3）已知一棵二叉树的前序遍历的 结果是ABECDFGHIJ, 中序遍历 的结果是EBCDAFHIGJ, 试画出这棵二叉树。 K