数据结构第6章树和二叉树2遍历二叉树和线索二叉树.pptx

《数据结构第6章树和二叉树2遍历二叉树和线索二叉树.pptx》由会员分享，可在线阅读，更多相关《数据结构第6章树和二叉树2遍历二叉树和线索二叉树.pptx（52页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、武汉科技大学Wuhan University of Science and Technology张 凯计算机学院 软件工程系2011年3月12日树和森林第第6 6章章 树树和和二叉树二叉树树的基本概念二叉树遍历二叉树和线索二叉树赫夫曼树及其应用v提出提出问题问题6.3 遍历遍历二叉树和线索二叉树二叉树和线索二叉树 在二叉树的一些应用中，常要求在树中查找具有某种特征的结点，或者对树中全部结点逐一进行某种处理。这就提出了遍历二叉树的问题。v遍历遍历是是任何类型均有的操作任何类型均有的操作6.3 遍历遍历二叉树和线索二叉树二叉树和线索二叉树 对线性结构而言，只有一条搜索路径(因为每个结点均只有一个后

2、继)；而二叉树是非线性结构，每个结点有两个后继，则存在如何遍历，即按什么样的搜索路径遍历的问题。v遍历遍历二叉树二叉树6.3 遍历遍历二叉树和线索二叉树二叉树和线索二叉树 对二叉树而言，是由三个基本单元组成：根结点、左子树和右子树。因此，若能遍历这三部分，便是遍历了整个二叉树。考虑：一共有多少种遍历 二叉树的方案？v遍历遍历二叉树二叉树6.3 遍历遍历二叉树和线索二叉树二叉树和线索二叉树 假如以 L、D、R 分别表示遍历二叉树的左子树、访问根结点、遍历右子树，则有 D L R、L D R、L R D D R L、R D L、R L D 先序 中序 后序 六种遍历方案选择v先先左后右的遍历算法左

3、后右的遍历算法6.3 遍历遍历二叉树和线索二叉树二叉树和线索二叉树 先（根）序遍历算法 DLR 中（根）序遍历算法 LDR 后（根）序遍历算法 LRDv先先（根）序遍历算法（根）序遍历算法6.3 遍历遍历二叉树和线索二叉树二叉树和线索二叉树若二叉树为空树，则空操作；否则(1)访问根结点；(2)先序遍历左子树；(3)先序遍历右子树。void PreOrderTraverse(BiTree bt)if(bt)printf(%c,bt-data);/*输出根结点数据域的值*/PreOrderTraverse(bt-lchild);/*先序遍历左子树*/PreOrderTraverse(bt-rchi

4、ld);/*先序遍历右子树*/v中中（根）序遍历算法（根）序遍历算法6.3 遍历遍历二叉树和线索二叉树二叉树和线索二叉树若二叉树为空树，则空操作；否则(1)中序遍历左子树；(2)访问根结点；(3)中序遍历右子树。void InOrderTraverse(BiTree bt)if(bt)InOrderTraverse(bt-lchild);/*中序遍历左子树*/printf(%c,bt-data);/*输出根结点数据域的值*/InOrderTraverse(bt-rchild);/*中序遍历右子树*/v后后（根）序遍历算法（根）序遍历算法6.3 遍历遍历二叉树和线索二叉树二叉树和线索二叉树若二叉

5、树为空树，则空操作；否则(1)后序遍历左子树；(2)后序遍历右子树；(3)访问根结点。void PostOrderTraverse(BiTree bt)if(bt)PostOrderTraverse(bt-lchild);/*后序遍历左子树*/PostOrderTraverse(bt-rchild);/*后序遍历右子树*/printf(%c,bt-data);/*输出根结点数据域的值*/v例例16.3 遍历遍历二叉树和线索二叉树二叉树和线索二叉树先序遍历的结果是：中序遍历的结果是：后序遍历的结果是：A B CD EA B D E CD B E A CD E B C A口诀：DLR先序遍历，即先

6、根再左再右LDR中序遍历，即先左再根再右LRD后序遍历，即先左再右再根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 Bv例例36.3 遍历遍历二叉树和线索二叉树二叉树和线索二叉树 假设一棵二叉树的先序序列为 E B A D C F H G I K J，中序序列为 A B C D E F G H I J K。画出该二叉树。v遍历算法遍历算法的的递归实现递归实现6.3 遍历遍历二叉树

7、和线索二叉树二叉树和线索二叉树回忆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);v先先序遍历二叉树的递归算法序遍历二叉树的递归算法6.3 遍历遍历二叉树和线索二叉树二叉树和线索二叉树Status PreOrderTraverse(BiTree T,Stat

8、us(*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;PreOrderTraverseACBD主主程程序序Pre(T)Pre(T R);Pre(T R);TAVisit(A);Pre(T L);TDVisit(D);Pre(T L)

9、;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;v中中序遍历二叉树的递归算法序遍历

10、二叉树的递归算法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;/InOrderTraversev后序后序遍历二叉树的递归算法遍历二叉树的递归算法6.3 遍历遍历二叉树和线索二叉树二叉树和线索二叉树Status PostOr

11、derTraverse(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;/PostOrderTraversev遍遍历的分析的分析6.3 遍历遍历二叉树和线索二叉树二叉树和线索二叉树1.从前面的三种遍历算法可以知道：如果将print语句抹去，从递归的角度看，这三种算法是完全相同的，或者说这三种遍历算法的访问路径是相

12、同的，只是访问结点的时机不同。从虚线的起点到终点，每个结点经过3次AFEDCBG第1次经过时访问先序遍历第2次经过时访问中序遍历第3次经过时访问后序遍历2.二叉树遍历的时间效率和空间效率时间效率:O O(n n)/每个结点只访问一次空间效率:O O(n n)/栈占用的最大辅助空间v中中序遍序遍历二叉二叉树的非的非递归算法一算法一6.3 遍历遍历二叉树和线索二叉树二叉树和线索二叉树Staus InOrderTrav(BiTree T,Status(*Visit)(TElemType e)/中序遍历二叉树T的非递归算法，对每个数据元素调用函数visit.InitStack(S);Push(S,T)

13、;/根指针进栈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;/InOrderTraverseACBEDv中中序遍序遍历二叉二叉树的非的非递归算法二算法二6.3 遍历遍历二叉树和线索二叉树二叉树和线索二叉树Status InOrderTrv(BiTree T,Status(*Vi

14、sit)(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/根指针进栈，遍历左子树/根指针退栈，访问根结点，遍历右子树 ACBEDv遍遍历算法的算法的应用用举例例6.3 遍历遍历二叉树

15、和线索二叉树二叉树和线索二叉树 “遍历”是二叉树各种操作的基础，可以在遍历过程中对结点进行各种操作，如：对于一棵已知树求结点的双亲，求结点的孩子结点，判定结点所在的层次等。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);/统计右

16、子树中叶子结点个数 else return ERROR;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;v例例3：按先序序列建立二叉：按先序序列建立二叉树的二叉的二叉链表表6.3 遍历遍历二叉树和线索二叉树二叉树和线索二叉树已知先序序列：A B C 0 0 D E

17、 0 G 0 0 F 0 0 0（其中0表示空格字符,空指针）建立相应的二叉链表ABCDEFGv例例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);/构造左子树 CreateBi

18、Tree(T-rchild);/构造右子树 Return OKv线索索二叉二叉树6.3 遍历遍历二叉树和线索二叉树二叉树和线索二叉树AEBCDFGHKv线索索二叉二叉树6.3 遍历遍历二叉树和线索二叉树二叉树和线索二叉树lchildDaterchildA B EC F D G H K v线索索二叉二叉树6.3 遍历遍历二叉树和线索二叉树二叉树和线索二叉树普通二叉树只能找到结点的左右孩子信息，而该结点的直接前驱和直接后继只能在遍历过程中获得。若将遍历后对应的有关前驱和后继预存起来，则从第一个结点开始就能很快“顺藤摸瓜”而遍历整个树了。v线索索二叉二叉树6.3 遍历遍历二叉树和线索二叉树二叉树和线

19、索二叉树例如中序遍历结果：B D C A E H G K F，实际上已将二叉树转为线性排列，显然具有唯一前驱和唯一后继。v线索索二叉二叉树6.3 遍历遍历二叉树和线索二叉树二叉树和线索二叉树A B EC F D G H K v线索索二叉二叉树6.3 遍历遍历二叉树和线索二叉树二叉树和线索二叉树两种解决方法：增加两个域：fwd和bwd；存放前驱指针存放后继指针如何预存这类信息？(唯一前驱和唯一后继)利用空链域（n+1个空链域）v线索索二叉二叉树6.3 遍历遍历二叉树和线索二叉树二叉树和线索二叉树问：用二叉链表法（l_child,r_child）存储包含n个结点的二叉树，结点的指针区域中会有多少个

20、空指针？分析：用二叉链表存储包含n个结点的二叉树，结点必有2n个链域（见二叉链表数据类型说明）。除根结点外，二叉树中每一个结点有且仅有一个双亲（直接前驱），所以只会有n1个结点的链域存放指针，指向非空子女结点（即直接后继）。所以，空指针数目2n(n1)n+1个v线索索二叉二叉树6.3 遍历遍历二叉树和线索二叉树二叉树和线索二叉树思考：二叉链表空间效率这么低，能否利用这些空闲区存放有用的信息或线索？我们可以用它来存放当前结点的直接前驱和后继等线索，以加快查找速度。规定：1）若结点有左子树，则lchild指向其左孩子；否则，lchild指向其直接前驱(即线索)；2）若结点有右子树，则rchild指

21、向其右孩子；否则，rchild指向其直接后继(即线索)。为区别两种不同情况，特增加两个标志域（各1bit）lchilddatarchild约定:当Tag域为0时,表示正常情况;当Tag域为1时,表示线索情况.右孩子或后继左孩子或前驱LTagRTagv二叉二叉树二叉二叉线索存索存储表示表示6.3 遍历遍历二叉树和线索二叉树二叉树和线索二叉树typedef enum Link,Thread PointerThr;/Link=0:指针，Thread=1:线索typedef struct BiThrNode TElemType data;Struct BiThrNode*lchild,*rchild;

22、/左右孩子指针 PointerThr LTag,RTag;/左右标志 BiThrNode,*BiThrTree;v有关有关线索二叉索二叉树的几个的几个术语6.3 遍历遍历二叉树和线索二叉树二叉树和线索二叉树 线索：指向结点前驱和后继的指针线索二叉树：加上线索的二叉树 线索链表：用含Tag的结点样式所构成的二叉链表 线索化：对二叉树以某种次序遍历使其变为线索二叉树的过程讨论：增加了前驱和后继等线索有什么好处？能方便找出当前结点的前驱和后继，不用堆栈也能遍历整个树。ABCGEIDHFNILNIL解：该二叉树中序遍历结果为:H,D,I,B,E,A,F,C,G所以添加线索应当按如下路径进行：例1：画出

23、以下二叉树对应的中序线索二叉树。例2：【2000年计算机系考研题】给定如图所示二叉树T，请画出与其对应的中序线索二叉树。2825405560330854解:因为中序遍历序列是：55 40 25 60 28 08 33 54对应线索树应当按此规律连线，即在原二叉树中添加虚线NILNILAEBCDFGHK例3：画出以下二叉树对应的中序线索二叉树。解：该二叉树中序遍历结果为:B,D,C,A,E,H,G,K,F所以添加线索应当按如下路径进行：NILNILv线索索二叉二叉树的生成的生成6.3 遍历遍历二叉树和线索二叉树二叉树和线索二叉树线索化过程就是在遍历过程中修改空指针的过程：将空的 lchild 改

24、为结点的直接前驱；将空的 rchild 改为结点的直接后继。非空指针呢？仍然指向孩子结点（称为“正常情况”）AEBCDFGHK例3：画出以下二叉树对应的中序线索二叉树。解：该二叉树中序遍历结果为:B,D,C,A,E,H,G,K,F所以添加线索应当按如下路径进行：NILNIL悬空？悬空？为避免悬空态，应增设一个头结点01对应的中序线索二叉树存储结构如图所示该二叉树中序遍历结果为:B,D,C,A,E,H,G,K,Froot0A01B01E00C10F11D10G01H11K1v如何如何在在线索索树中找中找结点的后点的后继6.3 遍历遍历二叉树和线索二叉树二叉树和线索二叉树结合中序线索树 若其右标志

25、为“1”，右链是线索，右链直接指示结点后继；若其右标志为“0”，右链是指针，其后继为右子树中最左下的结点。1234567v如何如何在在线索索树中找中找结点的前点的前驱6.3 遍历遍历二叉树和线索二叉树二叉树和线索二叉树结合中序线索树 若其左标志为“1”，左链为线索，左链直接指示其前驱；若其左标志为“0”，左链是指针，否则左子树中最右下的结点为其前驱。1234567线索链表的中序遍历算法Status IOTraver_T(BiThrTree T,Status(*Visit)(TElemType e)/T指向头结点，头结点的左链lchild指向根结点，中序遍历/二叉线索树T的非递归算法，对每个数据

26、元素调用函数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线索二叉树的生成算法（算法6.6,见教材P134）目的：在依某种顺序遍历二叉树时修改空指针，添加前驱或后继注解：为方便添加结点的前驱或后继，需要设置两

27、个指针：p指针当前结点之指针；pre指针前驱结点之指针。技巧：当结点p的左/右域为空时，只改写它的左域（装入前驱pre），而其右域（后继）留给下一结点来填写。或者说，当前结点的指针p应当送到前驱结点的空右域中。若p-lchildNULL,则p-Ltag=1;p-lchildpre;/p的前驱结点指针pre存入左空域若pre-rchildNULL,则pre-Rtag1;pre-rchild=p;/p存入其前驱结点pre的右空域D0pre指针0C当前结点前驱结点p指针1 1v线索索二叉二叉树6.3 遍历遍历二叉树和线索二叉树二叉树和线索二叉树void InThreading(BiThrTree p

28、)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);/右子树线索化 /InThreading01该二叉树中序遍历结果为:B,D,C,A,E,H,G,K,Froot0A01B01E00C10F11D10G01H11K1p指针v线索索二叉二叉树6.3 遍历遍历二叉树和线索二叉树二叉树和线索二叉树Status

29、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武汉科技大学Wuhan University of Science and Technology