數據結構第6章樹和二叉樹(編輯修改稿)

　

【文章內容簡介】 node //定義鏈表結構 { ElemType data。 //定義結點值 struct node *lchild。 //定義左子結點指針 struct node *rchild。 //定義右子結點指針 }BTree。 preorder(BTree *root) //前序遍歷 { if(root!= NULL) //如果不是空結點 { printf(“%c\n”,rootdata)。 //輸出當前結點值 preorder(rootlchild)。 //遞歸前序遍歷左子結點 preorder(rootrchild)。 //遞歸前序遍歷右子結點 } return。 //結束 } 2．遍歷算法 void inorder(BTree *root) //中序遍歷 { if(root!=NULL) //如果不是空結點 { inorder(rootlchild)。 //遞歸中序遍歷左子結點 printf(“%c\n”,rootdata)。 //輸出當前結點值 inorder(rootrchild)。 //遞歸中序遍歷右子結點 } } (3) 后序遍歷的算法實現 void postorder(BTree *root) //后序遍歷 { if(root!=NULL) //如果不是空結點 { postorder(rootlchild)。 //遞歸后序遍歷左子結點 postorder(rootrchild)。 //遞歸后序遍歷右子結點 printf(“%c\n”,rootdata)。 //輸出當前結點值 } } （ 2）中序遍歷的遞歸算法如下（假定結點的元素值為字符型）： void inorder(BiTree bt) { InitStack(s)； Push(s,bt)； while(!StackEmpty(s)) { while(GetTop(s)){ Push(s,GetTop(s)lchild)； p=POP(s)； if(!StackEmpty(s)) { visit(GetTop(s)data)； p=Pop(s)； Push(s, prchild)。}}} } 中序遍歷非遞歸算法 ,s為存儲二叉樹結點指針棧： 操作過程： 根結點先進棧，左結點緊跟根后面進棧 ,右結點在根出棧后入棧； 每個結點都要進一次和出一次棧，并且總是訪問棧頂元素， 因此，算法正確，時間復雜度為 O(n)。 通過上述三種不同的遍歷方式得到三種不同的線性序列，它們的共同的特點是有且僅有一個開始結點和一個終端結點，其余各結點都有且僅有一個前驅結點和一個后繼結點。 從二叉樹的遍歷定義可知，三種遍歷算法的不同之處僅在于訪問根結點和遍歷左右子樹的先后關系 。如果在算法中隱去和遞歸無關的語句 printf()， 則三種遍歷算法是完全相同的。遍歷二叉樹的算法中的基本操作是訪問結點，顯然，不論按那種方式進行遍歷，對含 n個結點的二叉樹，其時間復雜度均為 O(n)。 所含輔助空間為遍歷過程中占的最大容量，即樹的深度。最壞的情況下為 n， 則空間復雜度也為 O(n)。 3． 二叉鏈表的構造 (1) 基本思想 利用遍歷可以實現對結點的一些操作，如求結點的雙親，求結點的孩子等。還可以在遍歷過程中生成結點，建立二叉樹的存儲結構。前面介紹過用棧建立二叉樹，此處介紹一種基于先序遍歷的二叉樹構造方式，即以二叉樹的先序序列為輸入構造二叉鏈表。先序序列中必須加入虛結點以示空指針的位置。 (2) 構造算法（舉例說明） 【 例 64】建立圖 613 (a)所示二叉樹，其輸入的先序序列是：ABD∮G∮∮CE∮∮F∮∮ 。 【 解】假設虛結點輸入時以空格字符表示，相應的構造算法為： void CreateBinTree (BTree **T) { //構造二叉鏈表。 T是指向根指針的指針，故修改 *T就修改了實參 (根指針 )本身 char ch。 if((ch=getchar())==“ ”) *T=NULL。 //讀入空格，將相應指針置空 else //讀入非空格 { *T=(BTree *)malloc(sizeof(BTree))。 //生成結點 (*T)data=ch； CreateBinTree(amp。(*T)lchild)； //構造左子樹 CreateBinTree(amp。(*T)rchild)； //構造右子樹 } } 調用該算法時，應將待建立的二叉鏈表的根指針的地址作為實參 。 線索二叉樹 ⒈ 問題的提出 ：通過遍歷二叉樹可得到結點的一個線性序列，在線性序列中，很容易求得某個結點的直接前驅和后繼。但是在二叉樹上只能找到結點的左孩子、右孩子，結點的前驅和后繼只有在遍歷過程中才能得到，那么，如何保存遍歷二叉樹后動態得到的線性序列，以便快速找到某個結點的直接前驅和后繼？ 2. 分析 ： n個結點有 n1個前驅和 n1個后繼； 一共有 2n個鏈域，其中： n+1個空鏈域， n1個指針域； 因此 , 可以用空鏈域來存放結點的前驅和后繼。 線索二叉樹就是利用 n+1個 空鏈域 來存放結點的 前驅和后繼 結點的信息。 3. 線索二叉樹 ： 有效利用二叉鏈表中空的存儲空間，指定原有的孩子指針為空的域來存放指向前驅和后繼的信息，這樣的指針被稱為 “ 線索 ” 。加線索的過程稱為線索化，由此得到的二叉樹稱作 線索二叉樹 。 ⑴ 結點結構 在二叉鏈表中增加 ltag 和 rtag 兩個標志域 若結點有左子樹，則左鏈域 lchild指示其左孩子（ ltag= 0）； 否則，令左鏈域指示其前驅（ ltag=1）； 若結點有右子樹，則右鏈域 rchild指示其右孩子（ rtag= 0）； 否則，令右鏈域指示其后繼（ rtag= 1）； l t a g l c h i l d d a t a r c h i l d r t a g 中序、先序和后序線索二叉樹中所有實線均相同，所有結點的標志位取值也完全相同，只是當標志位取 1時，不同的線索二叉樹將用不同的虛線表示。 按中序遍歷得到的線索二叉樹稱為 中序線索二叉樹 ； 按先序遍歷得到的線索二叉樹稱為 先序線索二叉樹 ； 按后序遍歷得到的線索二叉樹稱為 后序線索二叉樹 ； （ 2）整體結構 增設一個頭結點，令其 lchild指向二叉樹的根結點， ltag=0、rtag=1； 并將該結點作為遍歷訪問的第一個結點的前驅和最后一個結點的后繼； 最后用頭指針指示該頭結點。 0 A 00 10 B 1 0 C 01 D 0 1 E 1 1 F 11 G 10 A 00 10 B 1 0 C 01 D 0 1 E 1 1 F 11 G 1( a ) 中 序 線 索 樹 ( b ) 先 序 線 索 樹r o o t r o o t0 A 00 10 B 1 0 C 01 D 0 1 E 1 1 F 11 G 1( c ) 后 序 線 索 樹r o o t圖 614 線索二叉樹 線索二叉樹的存儲結點可描述如下： struct node { ElemenType data。 //數據域 int ltag。 //左標志域 int rtag。 //右標志域 struct node *lchild。 //左指針域 struct node *rchild。 //右指針域 }BTree。 同樣，線索二叉樹根據遍歷規則的不同，可分為前序線索二叉樹、中序線索二叉樹、后序線索二叉樹。 建立中序線索二叉樹的算法 ： void thread(BTree **current,BTree **pre) { if(*current!=NULL) { thread(amp。(*current)lchild, pre)。 //左子樹線索化 if((*current)lchild==NULL){ (*current)lchild=*pre。 //建立當前結點的前驅線索 (*current)ltag=1。 } if((*pre)rchild==NULL) { (*pre)rchild=*current。 //建立前驅結點的后繼線索 (*pre)rtag=1。 } *pre=*current。 thread(amp。(*current)rchild,pre)。 //右子樹線索化 } } BTree *creathread(BTree *b) //中序線索化二叉樹 { BTree *pre,*root,*current。 root=(BTree *)malloc(sizeof(BTree))。 //創建根結點 rootdata=’r’。 //值 ’ r’表示根結點 rootltag=1。rootrtag=0。 if(b==NULL)。 //空二叉樹 { rootlchild=root。 rootrchild=root。 } else else { current=rootlchild=b。 rootltag=0。 pre=root。 //pre是前驅結點，供加線索用 thread(amp。current,amp。pre)。 //中序遍歷線索化二叉樹 prerchild=root。 //最后處理，加入指向根結點的線索 prertag=1。 rootrchild=pre。 //根結點右線索化 rootrtag=1。 } return root； } 樹和森林的遍歷 1．樹的遍歷 所謂樹的遍歷，就是按照某種順序依次訪問樹中各個結點，并使得每個結點只被訪問一次。也就是把非線性結構的樹結點變成線性序列的一種方式 。 樹的遍歷可以按深度優先遍歷，也可以按照廣度優先（按層次）遍歷。深度優先遍歷通常有兩種方式： 前序 遍歷和 后序 遍歷。 (1) 前序遍歷的遞歸定義： 若樹 T非空，則： 訪問根結點 R； 按照從左到右的順序依次前序遍歷根 結點 R的各子樹 T1，T2， … ， Tk。 (2) 后序遍歷的遞歸定義： 若樹 T非空，則： 按照從左到右的順序依次后序遍歷根 T的各子樹 Tl， T2， … ， Tk； 訪問根結點 R。 (3) 廣度優先（按層）遍歷 廣度優先（按層次）遍歷定義為：先訪問第一層結點（即樹根結點），再從左至右訪問第二層結點，依次按層訪問 …… ，直到樹中結點全部被訪問為止。對圖 66 (a)中的樹進行按層次遍歷得到樹的廣度優先遍歷序列為： ABCDEFG。 說明： ① 前序遍歷一棵樹恰好等價于前序遍歷該樹所對應的二叉樹。（ 將介紹二叉樹） ② 后序遍歷樹恰好等價于中序遍歷該樹所對應的二叉樹。 樹的先序遍歷算法描述如下： void Preorder(Btree *root) //先根遍歷 k叉樹 { if (roo