《中序遍历和线索化二叉树》由会员分享，可在线阅读，更多相关《中序遍历和线索化二叉树（24页珍藏版）》请在金锄头文库上搜索。
1、6.3遍历二叉树和线索二叉树b6.3.1遍历二叉树b 如果按某条搜索路径巡访树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。ABCDGEF先序遍历二叉树的操作定义为：b 若二叉树为空，则空操作；否则b （1）访问根结点；b （2）先序遍历左子树；b （3）先序遍历右子树。b A B C D F E GABCDGEF先序遍历二叉树的递归算法bStatus PreOrderTraverse(BiTree T, Status(* Visit)(TElemType e)b if (T)b if (Visit(T-data)b if (PreOrderTraverse(T-lchild,Vis
2、it)b if (PreOrderTraverse(T-rchild,Visit) b return OK;b return ERROR;b else return OK;b/PreOrderTraverse中序遍历二叉树的操作定义为：b若二叉树为空，则空操作；否则b （1）中序遍历左子树；b （2）访问根结点；b （3）中序遍历右子树。b C B D F A G EABCDGEF中序遍历二叉树示例b中序遍历二叉树得:ba+b*(c-d)-e/f-+a*e/-fbdc中序遍历二叉树的递归算法bStatus InOrderTraverse(BiTree T, Status(* Visit)(TE
3、lemType e) if (T) if (InOrderTraverse(T-lchild,Visit) if (Visit(T-data) if (InOrderTraverse(T-rchild,Visit)b return OK; return ERROR; else return OK;/InOrderTraverse后序遍历二叉树的操作定义为：b 若二叉树为空，则空操作；否则b （1）后序遍历左子树；b （2）后序遍历右子树；b （3）访问根结点。b C F D B G E AABCDGEF后序遍历二叉树的递归算法bStatus PostOrderTraverse(BiTree T
4、, 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中序遍历二叉树的非递归算法bStatus InOrderTraverse(BiTree T, Status(* Visit) (TElemType e) InitStack(S); Push(S,T);b while(!
5、StackEmpty(S)b while(GetTop(S,p) & p)Push(S,p-lchild); Pop(S, p); if (!StackEmpty(S) Pop(S,p); if (!Visite(p-data) return ERROR;b Push(S,p-rchild); return OK;/InOrderTraverse中序遍历二叉树的非递归算法示意图bC B D F A G EABCDGEFABCNULLSGetTopdata = ch ;b CreateBiTree(T-lchild);b CreateBiTree(T-rchild);b b return OK;
6、/CreateBiTree构造二叉链表ABCDGEF按下列次序输入字符:ABCDEGF(其中表示空格字符)可建立如右图的二叉链表.6.3.2 线索二叉树b遍 历 是 非 线 性 结 构 的 线 性 化 操 作保留遍历过程的顺序信息 - b线索二叉树的表示:b若结点有左子树，则其LCHILD域指示其左孩子，否则令LCHILD域指示其前驱；b若结点有右子树，则其RCHILD域指示其右孩子，否则令RCHILD域指示其后继。线索二叉树结点的结构:b 0 lchild域指示其左孩子bltag =b 1 lchild域指示其前驱b 0 rchild域指示其右孩子brtag =b 1 rchild域指示其后
7、继b线索二叉树b线索化b线索链表b线索datalchildrchildrtagltag中序线索二叉树-+a*e/-fbdcNILNILb*11 + /f00 e 中序线索二叉树中查找结点的后继和前驱:b如何在中序线索二叉树中找结点的后继： rtag = 1时，rchild所指的结点即为后继； rtag = 0时，其后继为遍历其右子树时的第一个结点（最左下结点）。如结点 “*”的后继是“c” 。b如何在中序线索二叉树中找结点的前驱：ltag = 1时，lchild所指的结点即为前驱；ltag = 0时，其前驱为遍历其左子树时的最后一个结点（最右下结点）。如根结点 “-”的前驱是“d” 。中序线索
8、二叉树/ 二叉树的二叉线索存储表示typedef 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 &Thrt, B
9、iThrTree 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; /最后一个结点线索化 Thr
10、t-rchild=pre; return OK;/InOrderThreading中序遍历进行中序线索化void InThreading(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例如
11、:将下列二叉链表改为中序线索链表1 2 3 4 5 6 7 8 9 10 11 12 13 14上例树的形态Thrt10 1234567891011121314ABDEFCHIGKJMNL中序遍历二叉线索树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&p-rchild!=T) p=p-rchild; Visit(p-data); /访问后继结点 p=p-rchild; return OK;/InOrderTraverse_Thr实验与习题bb理论习题 6.12-6.16,6.23b实验算法题: 6.37
