数据结构语言课件习题语言版树和二叉树

1、6.3遍历二叉树和线索二叉树6.3.1遍历二叉树 如果按某条搜索路径巡访树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。ABCDGEF先序遍历二叉树的操作定义为： 若二叉树为空，则空操作；否则 （1）访问根结点； （2）先序遍历左子树； （3）先序遍历右子树。 A B C D F E GABCDGEF先序遍历二叉树的递归算法Status PreOrderTraverse(BiTree T, Status(* Visit)(TElemType e) if (T) if (Visit(T-data) if (PreOrderTraverse(T-lchild,Visit) if (Pre

2、OrderTraverse(T-rchild,Visit) return OK; return ERROR; else return OK;/PreOrderTraverse中序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则 （1）中序遍历左子树； （2）访问根结点； （3）中序遍历右子树。 C B D F A G EABCDGEF中序遍历二叉树示例中序遍历二叉树得:a+b*(c-d)-e/f-+a*e/-fbdc中序遍历二叉树的递归算法Status InOrderTraverse(BiTree T, Status(* Visit)(TElemType e) if (T) if (InO

3、rderTraverse(T-lchild,Visit) if (Visit(T-data) if (InOrderTraverse(T-rchild,Visit) return OK; return ERROR; else return OK;/InOrderTraverse后序遍历二叉树的操作定义为： 若二叉树为空，则空操作；否则 （1）后序遍历左子树； （2）后序遍历右子树； （3）访问根结点。 C F D B G E AABCDGEF后序遍历二叉树的递归算法Status PostOrderTraverse(BiTree T, Status(* Visit)(TElemType e) i

4、f (T) if (PostOrderTraverse(T-lchild,Visit) if (PostOrderTraverse(T-rchild,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) &

5、p)Push(S,p-lchild); Pop(S, p); if (!StackEmpty(S) Pop(S,p); if (!Visite(p-data) return ERROR; Push(S,p-rchild); return OK;/InOrderTraverse中序遍历二叉树的非递归算法示意图C B D F A G EABCDGEFABCNULLSGetTopdata = ch ; CreateBiTree(T-lchild); CreateBiTree(T-rchild); return OK;/CreateBiTree构造二叉链表ABCDGEF按下列次序输入字符:ABCDEG

6、F(其中表示空格字符)可建立如右图的二叉链表.6.3.2 线索二叉树遍历是非线性结构的线性化操作保留遍历过程的顺序信息 - 线索二叉树的表示:若结点有左子树，则其LCHILD域指示其左孩子，否则令LCHILD域指示其前驱；若结点有右子树，则其RCHILD域指示其右孩子，否则令RCHILD域指示其后继。线索二叉树结点的结构: 0 lchild域指示其左孩子ltag = 1 lchild域指示其前驱 0 rchild域指示其右孩子rtag = 1 rchild域指示其后继线索二叉树线索化线索链表线索datalchildrchildrtagltag中序线索二叉树-+a*e/-fbdcNILNILb*

7、11 + /f00 e 中序线索二叉树中查找结点的后继和前驱:如何在中序线索二叉树中找结点的后继： rtag = 1时，rchild所指的结点即为后继； rtag = 0时，其后继为遍历其右子树时的第一个结点（最左下结点）。如结点 “*”的后继是“c” 。如何在中序线索二叉树中找结点的前驱：ltag = 1时，lchild所指的结点即为前驱；ltag = 0时，其前驱为遍历其左子树时的最后一个结点（最右下结点）。如根结点 “-”的前驱是“d” 。中序线索二叉树/ 二叉树的二叉线索存储表示typedef enum Link,Thread PointerTag; /Link=0:指针,Thread

8、=1:线索typedef struct BiThrNode TElemType data; struct BiThrNode *lchild,*rchild; /左右孩子指针 PointerTag LTag,RTag; /左右标志BiThrNode, *BiThrTree;中序遍历二叉树T，并将其中序线索化:(为了记下遍历过程中访问结点的先后次序，附设一个全程指针pre)Status InOrderThreading(BiThrTree &Thrt, BiThrTree T) / Thrt指向头结点。 if (!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode)

9、 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; /最后一个结点线索化 Thrt-rchild=pre; return OK;/InOrderThreading中序遍历进行中序线索化void InThreading(Bi

10、ThrTree 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上例树的形态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)