數(shù)據(jù)結(jié)構(gòu)語言課件習(xí)題語言版樹和二叉樹

1、6.3遍歷二叉樹和線索二叉樹6.3.1遍歷二叉樹 如果按某條搜索路徑巡訪樹中每個(gè)結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)均被訪問一次，而且僅被訪問一次。ABCDGEF先序遍歷二叉樹的操作定義為： 若二叉樹為空，則空操作；否則 （1）訪問根結(jié)點(diǎn)； （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）訪問根結(jié)點(diǎn)； （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）訪問根結(jié)點(diǎn)。 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構(gòu)造二叉鏈表ABCDGEF按下列次序輸入字符:ABCDEG

6、F(其中表示空格字符)可建立如右圖的二叉鏈表.6.3.2 線索二叉樹遍歷是非線性結(jié)構(gòu)的線性化操作保留遍歷過程的順序信息 - 線索二叉樹的表示:若結(jié)點(diǎn)有左子樹，則其LCHILD域指示其左孩子，否則令LCHILD域指示其前驅(qū)；若結(jié)點(diǎn)有右子樹，則其RCHILD域指示其右孩子，否則令RCHILD域指示其后繼。線索二叉樹結(jié)點(diǎn)的結(jié)構(gòu): 0 lchild域指示其左孩子ltag = 1 lchild域指示其前驅(qū) 0 rchild域指示其右孩子rtag = 1 rchild域指示其后繼線索二叉樹線索化線索鏈表線索datalchildrchildrtagltag中序線索二叉樹-+a*e/-fbdcNILNILb*

7、11 + /f00 e 中序線索二叉樹中查找結(jié)點(diǎn)的后繼和前驅(qū):如何在中序線索二叉樹中找結(jié)點(diǎn)的后繼： rtag = 1時(shí)，rchild所指的結(jié)點(diǎn)即為后繼； rtag = 0時(shí)，其后繼為遍歷其右子樹時(shí)的第一個(gè)結(jié)點(diǎn)（最左下結(jié)點(diǎn)）。如結(jié)點(diǎn) “*”的后繼是“c” 。如何在中序線索二叉樹中找結(jié)點(diǎn)的前驅(qū)：ltag = 1時(shí)，lchild所指的結(jié)點(diǎn)即為前驅(qū)；ltag = 0時(shí)，其前驅(qū)為遍歷其左子樹時(shí)的最后一個(gè)結(jié)點(diǎn)（最右下結(jié)點(diǎn)）。如根結(jié)點(diǎn) “-”的前驅(qū)是“d” 。中序線索二叉樹/ 二叉樹的二叉線索存儲(chǔ)表示typedef enum Link,Thread PointerTag; /Link=0:指針,Thread

8、=1:線索typedef struct BiThrNode TElemType data; struct BiThrNode *lchild,*rchild; /左右孩子指針 PointerTag LTag,RTag; /左右標(biāo)志BiThrNode, *BiThrTree;中序遍歷二叉樹T，并將其中序線索化:(為了記下遍歷過程中訪問結(jié)點(diǎn)的先后次序，附設(shè)一個(gè)全程指針pre)Status InOrderThreading(BiThrTree &Thrt, BiThrTree T) / Thrt指向頭結(jié)點(diǎn)。 if (!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode)

9、 exit (OVERFLOW); Thrt-LTag=Link; Thrt-RTag=Thread; /建頭結(jié)點(diǎn) Thrt-rchild=Thrt; /右指針回指 if (!T)Thrt-lchild=Thrt; /若二叉樹空，則左指針回指 else Thrt-lchild=T; pre=Thrt; InThreading(T); /中序遍歷進(jìn)行中序線索化 pre-rchild=Thrt; pre-RTag=Thread; /最后一個(gè)結(jié)點(diǎn)線索化 Thrt-rchild=pre; return OK;/InOrderThreading中序遍歷進(jìn)行中序線索化void InThreading(Bi

10、ThrTree p) / 一個(gè)全程指針pre if (p) InThreading(p-lchild); /左子樹線索化 if (!p-lchild) p-LTag=Thread;p-lchild=pre; /前驅(qū)線索 if (!pre-rchild) pre-RTag=Thread; pre-rchild=p; /后繼線索 pre=p; /保持pre指向p的前驅(qū) InThreading(p-rchild); /右子樹線索化 /InThreading例如:將下列二叉鏈表改為中序線索鏈表1 2 3 4 5 6 7 8 9 10 11 12 13 14上例樹的形態(tài)Thrt10 1234567891011121314ABDEFCHIGKJMNL中序遍歷二叉線索樹T的非遞歸算法:Status InOrderTraverse_Thr(BiThrTree T, Status(*Visit)(TElemType e) / T指向頭結(jié)點(diǎn)，頭結(jié)點(diǎn)的左鏈lchild 指向根結(jié)點(diǎn)， /可參見線索化算法。中序遍歷二叉線索樹T的非遞歸算法， / 對(duì)每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)Visit. p=T-lchild; /p指向根結(jié)點(diǎn) while(p!=T) /空樹或遍歷結(jié)束時(shí)，p=T while(p-LTag=Link)p=p-lchild;/p尋找最左下結(jié)點(diǎn) if (!Visit(p-data)