【文章內(nèi)容簡(jiǎn)介】 DLR C F D G 先序遍歷結(jié)果 : A B C D E F G T 若二叉樹(shù)為空樹(shù)，則空操作；否則， （ 1）中序遍歷左子樹(shù)； （ 2）訪問(wèn)根結(jié)點(diǎn)； （ 3）中序遍歷右子樹(shù)。 中（根）序的遍歷算法： 第一節(jié) 遍歷二叉樹(shù) A B C D G E F C B D F A G E 算法的遞歸描述 Status InOrderTraverse(BiTree T, Status(* Visit)(TElemType e)){ if (T){ if (InOrderTraverse(Tlchild,Visit)) if (Visit(Tdata)) if (InOrderTraverse(Trchild,Visit)) return OK。 return ERROR。 }else return OK。 }//InOrderTraverse 第一節(jié) 遍歷二叉樹(shù) A B C D E F G L D R T L D R L D R A B E L D R L D R LDR LDR C F D G 中序遍歷結(jié)果 : B D C A G F E T 若二叉樹(shù)為空樹(shù)，則空操作；否則， （ 1）后序遍歷左子樹(shù)； （ 2）后序遍歷右子樹(shù)； （ 3）訪問(wèn)根結(jié)點(diǎn)。 后（根）序的遍歷算法： 第一節(jié) 遍歷二叉樹(shù) A B C D G E F C F D B G E A 算法的遞歸描述 Status PostOrderTraverse(BiTree T, Status(* Visit)(TElemType e)) { if (T){ if (PostOrderTraverse(Tlchild,Visit)) if (PostOrderTraverse(Trchild,Visit)) if (Visit(Tdata)) return OK。 return ERROR。 }else return OK。 }//PostOrderTraverse 第一節(jié) 遍歷二叉樹(shù) A B C D E F G H K 例如 : 先序 序列 : A B C D E F G H K 中序 序列 : B D C A H G K F E 后序 序列 : D C B H K G F E A 第一節(jié) 遍歷二叉樹(shù) 例： 已知結(jié)點(diǎn)的先序序列和中序序列，求整棵二叉樹(shù)。 ? 先序序列： A B C D E F G ? 中序序列： C B E D A F G A C B E D F G A B C D E F G A B C F D E G 第一節(jié) 遍歷二叉樹(shù) 構(gòu)造二叉鏈表表示的二叉樹(shù)的遞歸算法 Status CreateBiTree(BiTree amp。T) { scanf(“%c”,amp。ch)。 if (ch==??) T=NULL。 else { if (!(T=(BiTNode *) malloc(sizeof (BiTNode)))) exit(OVERFLOW)。 Tdata = ch 。 CreateBiTree(Tlchild)。 CreateBiTree(Trchild)。 } return OK。 }//CreateBiTree 第一節(jié) 遍歷二叉樹(shù) lchild data rchild T ch 構(gòu)造二叉鏈表 A B C D G E F 按下列次序輸入字符 : ABC DE G F (其中 表示空格字符 ) 可建立如右圖的二叉鏈表 . 第一節(jié) 遍歷二叉樹(shù) ? 遍歷是非線性結(jié)構(gòu)的線性化操作保留遍歷過(guò)程的順序信息。 ? 線索二叉樹(shù)的表示 : ? 若結(jié)點(diǎn)有左子樹(shù) ， 則其 LCHILD域指示其左孩子 ，否則令 LCHILD域指示其前驅(qū)； ? 若結(jié)點(diǎn)有右子樹(shù) ， 則其 RCHILD域指示其右孩子 ，否則令 RCHILD域指示其后繼 。 第二節(jié) 線索二叉樹(shù) 線索二叉樹(shù)結(jié)點(diǎn)的結(jié)構(gòu) : 0 lchild域指示其左孩子 ? ltag ={ 1 lchild域指示其前驅(qū) 0 rchild域指示其右孩子 ? rtag ={ 1 rchild域指示其后繼 ? 線索二叉樹(shù) ? 線索化 ? 線索鏈表 ? 線索 data lchild rchild rtag ltag 第二節(jié) 線索二叉樹(shù) 中序線索二叉樹(shù) + a * e / f b d c NIL NIL b * 1 1 + / f 0 0 e 第二節(jié) 線索二叉樹(shù) data lchild rchild rtag ltag a+b*cde/f 中序線索二叉樹(shù) + a * e / f b d c NIL NIL 第二節(jié) 線索二叉樹(shù) a+b*cde/f 中序線索二叉樹(shù)中查找結(jié)點(diǎn)的后繼和前驅(qū) : ? 如何在中序線索二叉樹(shù)中找結(jié)點(diǎn)的后繼： – rtag = 1時(shí) ， rchild所指的結(jié)點(diǎn)即為后繼； – rtag =0時(shí) ， 其后繼為遍歷其右子樹(shù)時(shí)的第一個(gè)結(jié)點(diǎn)（ 最左下結(jié)點(diǎn) ） 。 – 如結(jié)點(diǎn) “ *” 的后繼是 “ c” 。 ? 如何在中序線索二叉樹(shù)中找結(jié)點(diǎn)的前驅(qū)： – ltag = 1時(shí) ， lchild所指的結(jié)點(diǎn)即為前驅(qū)； – ltag = 0時(shí) ， 其前驅(qū)為遍歷其左子樹(shù)時(shí)的最后一個(gè)結(jié)點(diǎn) （ 最右下結(jié)點(diǎn) ） 。 – 如根結(jié)點(diǎn) “ ”的前驅(qū)是 “ d” 。 第二節(jié) 線索二叉樹(shù) 例如 : 將下列二叉鏈表改為中序線索鏈表 Info A B C D E F G H I J K L M NLtagLchild 2 4 6 0 7 0 10 0 12 13 0 0 0 0RtagRchild 3 5 0 0 8 9 11 0 0 0 14 0 0 01 2 3 4 5 6 7 8 9 10 11 12 13 14 第二節(jié) 線索二叉樹(shù) 0 0 0 1 0 1 0 1 0 0 1 1 1 1 5 上例樹(shù)的形態(tài) Info Ltag Lchild Rtag RchildA 0 2 0 3B 0 4 0 5C 0 6 1 ThrtD 1 Thrt 1 2E 0 7 0 8F 1 1 0 9G 0 10 0 11H 1 5 1 1I 0 12 1 3J 0 13 1 7K 1 7 0 14L 1 6 1 9M 1 2 1 10N 1 11 1 5Thrt 1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 A B D E F C H I G K J M N L 中序線索二叉樹(shù) // 二叉樹(shù)的二叉線索存儲(chǔ)表示 typedef enum {Link,Thread} PointerTag。 //Link==0:指針 ,Thread==1:線索 typedef struct BiThrNode { TElemType data。 struct BiThrNode *lchild,*rchild。 //左右孩子指針 PointerTag LTag,RTag。 //左右標(biāo)志 }BiThrNode, *BiThrTree。 第二節(jié) 線索二叉樹(shù) 中序遍歷二叉樹(shù) T，并將其中序線索化 : (為了記下遍歷過(guò)程中訪問(wèn)結(jié)點(diǎn)的先后次序，附設(shè)一個(gè)全程指針 pre) Status InOrderThreading(BiThrTree amp。Thrt, BiThrTree T) { // Thrt指向頭結(jié)點(diǎn)。 if (!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode)))) exit (OVERFLOW)。 ThrtLTag=Link。 ThrtRTag=Thread。 //建頭結(jié)點(diǎn) Thrtrchild=Thrt。 //右指針回指 if (!T)Thrtlchild=Thrt。 //若二叉樹(shù)空，則左指針回指 else{ Thrtlchild=T。 pre=Thrt。 InThreading(T)。 //中序遍歷進(jìn)行中序線索化 prerchild=Thrt。 preRTag=Thread。 //最后一個(gè)結(jié)點(diǎn)線索化 Thrtrchild=pre。 } return OK。 }//InOrderThreading 第二節(jié) 線索二叉樹(shù) 中序遍歷進(jìn)行中序線索化 void InThreading(BiThrTree p){ // 一個(gè)全程指針 pre if (p){ InThreading(plchild)。 //左子樹(shù)線索化 if (!plchild){ pLTag=Thread。plchild=pre。} //前驅(qū)線索 if (!prerchild){ preRTag=Thread。 prerchild=p。} //后繼線索 pre=p。 //保持 pre指向 p的前驅(qū) InThreading(prchild)。 //右子樹(shù)線索化 }