数据结构树和二叉树遍历二叉树和线索二叉树.pptx
树和森林第第6 6章章 树树和和二叉树二叉树树的基本概念二叉树遍历二叉树和线索二叉树赫夫曼树及其应用第1页/共52页v提出问题6.3 遍历遍历二叉树和线索二叉树二叉树和线索二叉树 在二叉树的一些应用中，常要求在树中查找具有某种特征的结点，或者对树中全部结点逐一进行某种处理。这就提出了遍历二叉树的问题。第2页/共52页v遍历是任何类型均有的操作6.3 遍历遍历二叉树和线索二叉树二叉树和线索二叉树 对线性结构而言，只有一条搜索路径(因为每个结点均只有一个后继)；而二叉树是非线性结构，每个结点有两个后继，则存在如何遍历，即按什么样的搜索路径遍历的问题。第3页/共52页v遍历二叉树6.3 遍历遍历二叉树和线索二叉树二叉树和线索二叉树 对二叉树而言，是由三个基本单元组成：根结点、左子树和右子树。因此，若能遍历这三部分，便是遍历了整个二叉树。考虑：一共有多少种遍历 二叉树的方案？第4页/共52页v遍历二叉树6.3 遍历遍历二叉树和线索二叉树二叉树和线索二叉树 假如以 L、D、R 分别表示遍历二叉树的左子树、访问根结点、遍历右子树，则有 D L R、L D R、L R D D R L、R D L、R L D 先序 中序 后序 六种遍历方案选择第5页/共52页v先左后右的遍历算法6.3 遍历遍历二叉树和线索二叉树二叉树和线索二叉树 先（根）序遍历算法 DLR 中（根）序遍历算法 LDR 后（根）序遍历算法 LRD第6页/共52页v先（根）序遍历算法6.3 遍历遍历二叉树和线索二叉树二叉树和线索二叉树若二叉树为空树，则空操作；否则(1)访问根结点；(2)先序遍历左子树；(3)先序遍历右子树。void PreOrderTraverse(BiTree bt)if(bt)printf(%c,bt-data);/*输出根结点数据域的值*/PreOrderTraverse(bt-lchild);/*先序遍历左子树*/PreOrderTraverse(bt-rchild);/*先序遍历右子树*/第7页/共52页v中（根）序遍历算法6.3 遍历遍历二叉树和线索二叉树二叉树和线索二叉树若二叉树为空树，则空操作；否则(1)中序遍历左子树；(2)访问根结点；(3)中序遍历右子树。void InOrderTraverse(BiTree bt)if(bt)InOrderTraverse(bt-lchild);/*中序遍历左子树*/printf(%c,bt-data);/*输出根结点数据域的值*/InOrderTraverse(bt-rchild);/*中序遍历右子树*/第8页/共52页v后（根）序遍历算法6.3 遍历遍历二叉树和线索二叉树二叉树和线索二叉树若二叉树为空树，则空操作；否则(1)后序遍历左子树；(2)后序遍历右子树；(3)访问根结点。void PostOrderTraverse(BiTree bt)if(bt)PostOrderTraverse(bt-lchild);/*后序遍历左子树*/PostOrderTraverse(bt-rchild);/*后序遍历右子树*/printf(%c,bt-data);/*输出根结点数据域的值*/第9页/共52页v例16.3 遍历遍历二叉树和线索二叉树二叉树和线索二叉树先序遍历的结果是：中序遍历的结果是：后序遍历的结果是：A B CD EA B D E CD B E A CD E B C A口诀：DLR先序遍历，即先根再左再右LDR中序遍历，即先左再根再右LRD后序遍历，即先左再右再根第10页/共52页v例2：用二叉树表示算术表达式6.3 遍历遍历二叉树和线索二叉树二叉树和线索二叉树+*A*/EDCB先序遍历+*/A B C D E前缀表示中序遍历A/B*C*D+E中缀表示后序遍历A B/C*D*E+后缀表示层序遍历+*E*D/C A B第11页/共52页v例36.3 遍历遍历二叉树和线索二叉树二叉树和线索二叉树 假设一棵二叉树的先序序列为 E B A D C F H G I K J，中序序列为 A B C D E F G H I J K。画出该二叉树。第12页/共52页v遍历算法的递归实现6.3 遍历遍历二叉树和线索二叉树二叉树和线索二叉树回忆1：二叉树结点的数据类型定义：typedef struct node*tree_pointer;typedef struct node int data;tree_pointer left_child,right_child;node;回忆2：递归求解 n!long int fact(n)/求n!long s;if(n1)s=n*fact(n-1);else f=1;return(f);第13页/共52页v先序遍历二叉树的递归算法6.3 遍历遍历二叉树和线索二叉树二叉树和线索二叉树Status PreOrderTraverse(BiTree T,Status(*Visit)(TElemType e)/二叉链表存储结构，visit是对数据元素操作的应用函数/先序遍历二叉树T的递归算法，对每个数据元素调用visit if(T)if(Visit(T-data)if(PreOrderTraverse(T-lchild,Visit)if(PreOrderTraverser(T-rchild,Visit)return OK;return ERROR;else return OK;PreOrderTraverse第14页/共52页ACBD主主程程序序Pre(T)Pre(T R);Pre(T R);TAVisit(A);Pre(T L);TDVisit(D);Pre(T L);TCVisit(C);Pre(T L);TBVisit(B);Pre(T L);返回返回TPre(T R);返回返回T返回返回T返回返回T返回返回TPre(T R);得到的遍历次序为：A B D CPreOrderTraverse(BiTree T,Status(*Visit)(TElemType e)if(T)if(Visit(T-data)if(PreOrderTraverse(T-lchild,Visit)if(PreOrderTraverser(T-rchild,Visit)return OK;return ERROR;else return OK;第15页/共52页v中序遍历二叉树的递归算法6.3 遍历遍历二叉树和线索二叉树二叉树和线索二叉树Status InOrderTraverse(BiTree T,Status(*Visit)(TElemType e)if(T)if(InOrderTraverse(T-lchild,Visit)if(Visit(T-data)if(InOrderTraverse(T-rchild,Visit)return OK;return ERROR;else return OK;/InOrderTraverse第16页/共52页v后序遍历二叉树的递归算法6.3 遍历遍历二叉树和线索二叉树二叉树和线索二叉树Status PostOrderTraverse(BiTree T,Status(*Visit)(TElemType e)if(T)if(PostOrderTraverse(T-lchild,Visit)if(PostOrderTraverse(T-rchild,Visit)if(Visit(T-data)return OK;return ERROR;else return OK;/PostOrderTraverse第17页/共52页v遍历的分析6.3 遍历遍历二叉树和线索二叉树二叉树和线索二叉树1.从前面的三种遍历算法可以知道：如果将print语句抹去，从递归的角度看，这三种算法是完全相同的，或者说这三种遍历算法的访问路径是相同的，只是访问结点的时机不同。从虚线的起点到终点，每个结点经过3次AFEDCBG第1次经过时访问先序遍历第2次经过时访问中序遍历第3次经过时访问后序遍历2.二叉树遍历的时间效率和空间效率时间效率:O O(n n)/每个结点只访问一次空间效率:O O(n n)/栈占用的最大辅助空间第18页/共52页v中序遍历二叉树的非递归算法一6.3 遍历遍历二叉树和线索二叉树二叉树和线索二叉树Staus InOrderTrav(BiTree T,Status(*Visit)(TElemType e)/中序遍历二叉树T的非递归算法，对每个数据元素调用函数visit.InitStack(S);Push(S,T);/根指针进栈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 error;Push(S,p-rchild);/if/whileReturn ok;/InOrderTraverseACBED第19页/共52页v中序遍历二叉树的非递归算法二6.3 遍历遍历二叉树和线索二叉树二叉树和线索二叉树Status InOrderTrv(BiTree T,Status(*Visit)(TElemType e)/采用二叉链表存储结构，Visit是对数据元素操作的应用函数/中序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit。InitStack(S);p=T;while(p|!StackEmpty(S)if(p)Push(&S,p);p=p-lchild;else Pop(&S,&p);if(!Visit(p-data)return ERROR；p=p-rchild;/else /while return OK;/InOrderTrv/根指针进栈，遍历左子树/根指针退栈，访问根结点，遍历右子树 ACBED第20页/共52页v遍历算法的应用举例6.3 遍历遍历二叉树和线索二叉树二叉树和线索二叉树 “遍历”是二叉树各种操作的基础，可以在遍历过程中对结点进行各种操作，如：对于一棵已知树求结点的双亲，求结点的孩子结点，判定结点所在的层次等。第21页/共52页v例1：统计二叉树中叶子结点的个数6.3 遍历遍历二叉树和线索二叉树二叉树和线索二叉树Status CountLeaf(BiTree T,int&count)if(T)if(T-lchild=NULL)&(T-rchild=NULL)count+;return OK;CountLeaf(T-lchild,count);/统计左子树中叶子结点个数 CountLeaf(T-rchild,count);/统计右子树中叶子结点个数 else return ERROR;第22页/共52页v例2：求二叉树的深度6.3 遍历遍历二叉树和线索二叉树二叉树和线索二叉树int Depth(BiTree T)if(!T)depthval=0;else depthLeft=Depth(T-lchild);depthRight=Depth(T-rchild);depthval=1+max(depthLeft,depthRight);return depthval;第23页/共52页v例3：按先序序列建立二叉树的二叉链表6.3 遍历遍历二叉树和线索二叉树二叉树和线索二叉树已知先序序列：A B C 0 0 D E 0 G 0 0 F 0 0 0（其中0表示空格字符,空指针）建立相应的二叉链表ABCDEFG第24页/共52页v例3：按先序序列建立二叉树的二叉链表6.3 遍历遍历二叉树和线索二叉树二叉树和线索二叉树Status CreateBiTree(BiTree&T)/按先序序列输入二叉树中结点的值，空格字符表示空树 Scanf(&ch)if(ch=)T=NULL;else if(!(T=(BiTNode*)malloc(sizeof(BiTNode)exit(OVERFLOW);T-data=ch;/构造根结点 CreateBiTree(T-lchild);/构造左子树 CreateBiTree(T-rchild);/构造右子树 Return OK第25页/共52页v线索二叉树6.3 遍历遍历二叉树和线索二叉树二叉树和线索二叉树AEBCDFGHK第26页/共52页v线索二叉树6.3 遍历遍历二叉树和线索二叉树二叉树和线索二叉树lchildDaterchildA B EC F D G H K 第27页/共52页v线索二叉树6.3 遍历遍历二叉树和线索二叉树二叉树和线索二叉树普通二叉树只能找到结点的左右孩子信息，而该结点的直接前驱和直接后继只能在遍历过程中获得。若将遍历后对应的有关前驱和后继预存起来，则从第一个结点开始就能很快“顺藤摸瓜”而遍历整个树了。第28页/共52页v线索二叉树6.3 遍历遍历二叉树和线索二叉树二叉树和线索二叉树例如中序遍历结果：B D C A E H G K F，实际上已将二叉树转为线性排列，显然具有唯一前驱和唯一后继。第29页/共52页v线索二叉树6.3 遍历遍历二叉树和线索二叉树二叉树和线索二叉树A B EC F D G H K 第30页/共52页v线索二叉树6.3 遍历遍历二叉树和线索二叉树二叉树和线索二叉树两种解决方法：增加两个域：fwd和bwd；存放前驱指针存放后继指针如何预存这类信息？(唯一前驱和唯一后继)利用空链域（n+1个空链域）第31页/共52页v线索二叉树6.3 遍历遍历二叉树和线索二叉树二叉树和线索二叉树问：用二叉链表法（l_child,r_child）存储包含n个结点的二叉树，结点的指针区域中会有多少个空指针？分析：用二叉链表存储包含n个结点的二叉树，结点必有2n个链域（见二叉链表数据类型说明）。除根结点外，二叉树中每一个结点有且仅有一个双亲（直接前驱），所以只会有n1个结点的链域存放指针，指向非空子女结点（即直接后继）。所以，空指针数目2n(n1)n+1个第32页/共52页v线索二叉树6.3 遍历遍历二叉树和线索二叉树二叉树和线索二叉树思考：二叉链表空间效率这么低，能否利用这些空闲区存放有用的信息或线索？我们可以用它来存放当前结点的直接前驱和后继等线索，以加快查找速度。第33页/共52页规定：1）若结点有左子树，则lchild指向其左孩子；否则，lchild指向其直接前驱(即线索)；2）若结点有右子树，则rchild指向其右孩子；否则，rchild指向其直接后继(即线索)。为区别两种不同情况，特增加两个标志域（各1bit）lchilddatarchild约定:当Tag域为0时,表示正常情况;当Tag域为1时,表示线索情况.右孩子或后继左孩子或前驱LTagRTag第34页/共52页v二叉树二叉线索存储表示6.3 遍历遍历二叉树和线索二叉树二叉树和线索二叉树typedef enum Link,Thread PointerThr;/Link=0:指针，Thread=1:线索typedef struct BiThrNode TElemType data;Struct BiThrNode*lchild,*rchild;/左右孩子指针 PointerThr LTag,RTag;/左右标志 BiThrNode,*BiThrTree;第35页/共52页v有关线索二叉树的几个术语6.3 遍历遍历二叉树和线索二叉树二叉树和线索二叉树 线索：指向结点前驱和后继的指针线索二叉树：加上线索的二叉树 线索链表：用含Tag的结点样式所构成的二叉链表 线索化：对二叉树以某种次序遍历使其变为线索二叉树的过程讨论：增加了前驱和后继等线索有什么好处？能方便找出当前结点的前驱和后继，不用堆栈也能遍历整个树。第36页/共52页ABCGEIDHFNILNIL解：该二叉树中序遍历结果为:H,D,I,B,E,A,F,C,G所以添加线索应当按如下路径进行：例1：画出以下二叉树对应的中序线索二叉树。第37页/共52页例2：【2000年计算机系考研题】给定如图所示二叉树T，请画出与其对应的中序线索二叉树。2825405560330854解:因为中序遍历序列是：55 40 25 60 28 08 33 54对应线索树应当按此规律连线，即在原二叉树中添加虚线NILNIL第38页/共52页AEBCDFGHK例3：画出以下二叉树对应的中序线索二叉树。解：该二叉树中序遍历结果为:B,D,C,A,E,H,G,K,F所以添加线索应当按如下路径进行：NILNIL第39页/共52页v线索二叉树的生成6.3 遍历遍历二叉树和线索二叉树二叉树和线索二叉树线索化过程就是在遍历过程中修改空指针的过程：将空的 lchild 改为结点的直接前驱；将空的 rchild 改为结点的直接后继。非空指针呢？仍然指向孩子结点（称为“正常情况”）第40页/共52页AEBCDFGHK例3：画出以下二叉树对应的中序线索二叉树。解：该二叉树中序遍历结果为:B,D,C,A,E,H,G,K,F所以添加线索应当按如下路径进行：NILNIL悬空？悬空？为避免悬空态，应增设一个头结点第41页/共52页01对应的中序线索二叉树存储结构如图所示该二叉树中序遍历结果为:B,D,C,A,E,H,G,K,Froot0A01B01E00C10F11D10G01H11K1第42页/共52页v如何在线索树中找结点的后继6.3 遍历遍历二叉树和线索二叉树二叉树和线索二叉树结合中序线索树 若其右标志为“1”，右链是线索，右链直接指示结点后继；若其右标志为“0”，右链是指针，其后继为右子树中最左下的结点。1234567第43页/共52页v如何在线索树中找结点的前驱6.3 遍历遍历二叉树和线索二叉树二叉树和线索二叉树结合中序线索树 若其左标志为“1”，左链为线索，左链直接指示其前驱；若其左标志为“0”，左链是指针，否则左子树中最右下的结点为其前驱。1234567第44页/共52页线索链表的中序遍历算法Status IOTraver_T(BiThrTree T,Status(*Visit)(TElemType e)/T指向头结点，头结点的左链lchild指向根结点，中序遍历/二叉线索树T的非递归算法，对每个数据元素调用函数Visit。p=T-lchild;/p指向根结点 while(p!=T)/空树或遍历结束时，p=T while(p-LTag=Link)p=p-lchild;if(!Visit(p-data)return ERROR;/访问其左子树为空的结点 while(p-RTag=Thread&p-rchild!=T)p=p-rchild;Visit(p-data);/访问后继结点 p=p-rchild;return OK;/IOTraver_T第45页/共52页线索二叉树的生成算法（算法6.6,见教材P134）目的：在依某种顺序遍历二叉树时修改空指针，添加前驱或后继注解：为方便添加结点的前驱或后继，需要设置两个指针：p指针当前结点之指针；pre指针前驱结点之指针。技巧：当结点p的左/右域为空时，只改写它的左域（装入前驱pre），而其右域（后继）留给下一结点来填写。或者说，当前结点的指针p应当送到前驱结点的空右域中。若p-lchildNULL,则p-Ltag=1;p-lchildpre;/p的前驱结点指针pre存入左空域若pre-rchildNULL,则pre-Rtag1;pre-rchild=p;/p存入其前驱结点pre的右空域第46页/共52页D0pre指针0C当前结点前驱结点p指针1 1第47页/共52页v线索二叉树6.3 遍历遍历二叉树和线索二叉树二叉树和线索二叉树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第48页/共52页01该二叉树中序遍历结果为:B,D,C,A,E,H,G,K,Froot0A01B01E00C10F11D10G01H11K1p指针第49页/共52页v线索二叉树6.3 遍历遍历二叉树和线索二叉树二叉树和线索二叉树Status InorderThreading(BiThrTree&Thrt,BiThrTree T)/中序遍历二叉树T,并将其中序线索化,Thrt 指向头结点.if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrnode)exit (OVERFLOW);Thrt-LTag=Link;Thrt-RTag=Thead;/建头结点 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第50页/共52页第51页/共52页感谢您的观看！第52页/共52页
