《中序遍历和线索化二叉树.ppt》由会员分享，可在线阅读，更多相关《中序遍历和线索化二叉树.ppt（24页珍藏版）》请在三一办公上搜索。
1、6.3遍历二叉树和线索二叉树,6.3.1遍历二叉树 如果按某条搜索路径巡访树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。,先序遍历二叉树的操作定义为：,若二叉树为空，则空操作；否则（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。A B C D F E G,先序遍历二叉树的递归算法,Status PreOrderTraverse(BiTree T,Status(*Visit)(TElemType e)if(T)if(Visit(T-data)if(PreOrderTraverse(T-lchild,Visit)if(PreOrderTraverse(T-rchild,V
2、isit)return OK;return ERROR;else return OK;/PreOrderTraverse,中序遍历二叉树的操作定义为：,若二叉树为空，则空操作；否则（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。C B D F A G E,中序遍历二叉树示例,中序遍历二叉树得:a+b*(c-d)-e/f,中序遍历二叉树的递归算法,Status InOrderTraverse(BiTree T,Status(*Visit)(TElemType e)if(T)if(InOrderTraverse(T-lchild,Visit)if(Visit(T-data)if(In
3、OrderTraverse(T-rchild,Visit)return OK;return ERROR;else return OK;/InOrderTraverse,后序遍历二叉树的操作定义为：,若二叉树为空，则空操作；否则（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。C F D B G E A,后序遍历二叉树的递归算法,Status PostOrderTraverse(BiTree T,Status(*Visit)(TElemType e)if(T)if(PostOrderTraverse(T-lchild,Visit)if(PostOrderTraverse(T-rchi
4、ld,Visit)if(Visit(T-data)return OK;return ERROR;else return OK;/PostOrderTraverse,中序遍历二叉树的非递归算法,Status InOrderTraverse(BiTree T,Status(*Visit)(TElemType e)InitStack(S);Push(S,T);while(!StackEmpty(S)while(GetTop(S,p)/InOrderTraverse,中序遍历二叉树的非递归算法示意图,C B D F A G E,例：已知结点的先序序列和中序序列，求整棵二叉树。,先序序列：A B C D
5、 E F G中序序列：C B E D A F G,构造二叉链表表示的二叉树的递归算法,Status CreateBiTree(BiTree/CreateBiTree,构造二叉链表,按下列次序输入字符:ABCDEGF(其中表示空格字符)可建立如右图的二叉链表.,6.3.2 线索二叉树,遍历是非线性结构的线性化操作保留遍历过程的顺序信息-线索二叉树的表示:若结点有左子树，则其LCHILD域指示其左孩子，否则令LCHILD域指示其前驱；若结点有右子树，则其RCHILD域指示其右孩子，否则令RCHILD域指示其后继。,线索二叉树结点的结构:,0 lchild域指示其左孩子ltag=1 lchild域指
6、示其前驱 0 rchild域指示其右孩子rtag=1 rchild域指示其后继线索二叉树线索化线索链表线索,中序线索二叉树,NIL,NIL,中序线索二叉树中查找结点的后继和前驱:,如何在中序线索二叉树中找结点的后继：rtag=1时，rchild所指的结点即为后继；rtag=0时，其后继为遍历其右子树时的第一个结点（最左下结点）。如结点“*”的后继是“c”。如何在中序线索二叉树中找结点的前驱：ltag=1时，lchild所指的结点即为前驱；ltag=0时，其前驱为遍历其左子树时的最后一个结点（最右下结点）。如根结点“-”的前驱是“d”。,中序线索二叉树,/二叉树的二叉线索存储表示typedef
7、enum Link,Thread PointerTag;/Link=0:指针,Thread=1:线索typedef struct BiThrNode TElemType data;struct BiThrNode*lchild,*rchild;/左右孩子指针 PointerTag LTag,RTag;/左右标志BiThrNode,*BiThrTree;,中序遍历二叉树T，并将其中序线索化:(为了记下遍历过程中访问结点的先后次序，附设一个全程指针pre),Status InOrderThreading(BiThrTree/InOrderThreading,中序遍历进行中序线索化,void InT
8、hreading(BiThrTree p)/一个全程指针pre 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,例如:将下列二叉链表改为中序线索链表,1 2 3 4 5 6 7 8 9 10 11 12 13 14,上例树的形态,12345678910111213
9、14,中序遍历二叉线索树T的非递归算法:,Status InOrderTraverse_Thr(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;/p寻找最左下结点 if(!Visit(p-data)return ERROR;/访问其左子树为空的结点 while(p-RTag=Thread/InOrderTraverse_Thr,实验与习题,理论习题 6.12-6.16,6.23实验算法题:6.37,
