【正文】 般的二叉樹，我們必須按照完全二叉樹的形式來存儲，就會造成空間的浪費。 strct Node * LChild。 證明： 分支數(shù)目 B=n1，即非空的鏈域有 n1個，故空鏈域有 2n(n1)=n+1個。 二叉樹的基本結構由 根結點 、 左子樹 和 右子樹組成 RChild Data LChild Data LChild RChild 如圖示 二叉樹的遍歷 用 L、 D、 R分別表示 遍歷左子樹 、 訪問根結點 、 遍歷右子樹 ，那么對二叉樹的遍歷順序就可以有： (1)訪問根，遍歷左子樹，遍歷右子樹 (記做 DLR)。 (5)遍歷右子樹，訪問根，遍歷左子樹 (記做 RDL)。 注意：先序、中序、后序遍歷是遞歸定義的，即在其子樹中亦按上述規(guī)律進行遍歷。 對于如下圖的二叉樹，其先序、中序、后序遍歷的序列為： 先序遍歷： A、 B、 D、 F、 G、 C、 E、 H 。 /*訪問根結點 */ PreOrder(root LChild)。 /*訪問根結點 */ InOrder(root RChild)。 /*訪問根結點 */ } } 以中序遍歷為例來說明中序遍歷二叉樹的遞歸過程 A B D C E B D Ф Ф Ф 第一次經過 第二次經過 第三次經過 遍歷算法應用 【 算法描述 】 void PreOrder(BiTree root) /* 先序遍歷輸出二叉樹結點 , root為指向二叉樹根結點的指針 */ { if (root!=NULL) { printf (root data)。下面給出采用前序遍歷實現(xiàn)的算法。 root RChild==NULL) printf (root data)。 【 算法描述 】 /* LeafCount為保存葉子結點數(shù)目的全局變量 ,調用之前初始化值為 0 */ void leaf(BiTree root) { if(root!=NULL) { leaf(rootLChild)。 root RChild==NULL) LeafCount++。 else if ((rootLChild==NULL)amp。 return LeafCount。 if(ch==39。 (*bt)data=ch。((*bt)RChild))。 /* 求右子樹的深度 */ max=hlhr?hl:hr。 【 算法思想 】 二叉樹的高度（深度）為二叉樹中結點層次的最大值。 /*如果該結點層次值大于 depth， 更新 depth的值 */ PreTreeDepth(btLchild, h+1)。 旋轉 。這些操作應在訪問根結點時實現(xiàn)。 } for(int i=0。 /*按逆中序輸出結點 ， 用層深決定的左右位置 */ 思考：對二叉樹實現(xiàn)左右子樹交換，是否可采用先序、中序、后序中的任何一種算法實現(xiàn)，請簡要說明原因。 【 算法思想 】 （ 1）針對左遞歸，寫出遞歸進層的三件事 （ 2）接著寫出左遞歸返回時應執(zhí)行的語句：訪問根結點 （ 3）接著針對右遞歸，寫出遞歸進層的三件事 （ 4）針對遞歸退層，寫出遞歸退層的三件事（左、右遞歸公用） void inorder(BiTree root)。 if(topm)。 /* 給下層參數(shù)賦值 */ goto L1。 s[top1]=p。 } L3: if(top!=0) { addr=s[top]。 } } 可以看到，直接按定義得到的上述算法結構并不好，為使程序合理組織，需去掉 goto語句，用循環(huán)句代替 if與 goto，此時返回斷點已無保留的必要，棧區(qū)只需保留本層參數(shù)。 （ 3） 走右子樹。 top=top+1。 top=top1。 (2)否則退棧并訪問，然后走右子樹。 while(p!=NULL || !IsEmpty(S)) { if (p!=NULL) /* 根指針進棧 ， 遍歷左子樹 */ { Push(amp。S,amp。 } } } 遞歸算法的時間復雜度分析： 對有 n個結點二叉樹 ， 該算法每循環(huán)一次 ， p指向一個結點或空 （ 無左孩子或無右孩子的結點的空鏈域 ） ，因此指向空的次數(shù)為 n+1， n為結點個數(shù) ， 故循環(huán)次數(shù)為 n+(n+1)=2n+1,從而算法的復雜度為 O(n)。 隨著函數(shù)遞歸調用 ， 運行棧繼續(xù)增長 ， 直到函數(shù)執(zhí)行完 ， 才徹底釋放占用的?？臻g 。 int top=0。 if(top=Stack_Size) OverFlow()。 if((pRChild==NULL) ||(pRChild==q)) /* 無右孩子 ， 或右孩子已遍歷過 */ { visit(pdata)。 } else p=pRChild。 在有 n個結點的二叉鏈表中共有 2n個鏈域，但只有 n1個有用非空鏈域，其余 n+1個鏈域是空的。 線索鏈表： 以這種結構組成的二叉鏈表作為二叉樹的存儲結構，叫做 線索鏈表 。 （ 2）加線索操作就是訪問結點操作。 rootLChile=pre。 preRtag=1。qRtag==0。 } 下面是對同一棵二叉樹的遍歷方法不同得到的不同線索樹。 qLtag==0 。 If(!p) return (NULL)。 P=InFirst(Bt)。 我們主要以 中序線索二叉樹 為例，說明線索二叉樹的插入和刪除運算。 ① 若結點 p的右孩子為空，則插入結點 r的過程很簡單。這時還需要 修改原來 p的右子樹中 “ 最左下端 ” 結點的左指針域 ，使它由原來的指向結點 p變?yōu)橹赶蚪Y點 r。 /* r成為 p的右孩子 */ rLChild=p。 /* 查找 p結點的右子樹的 “ 最左下端 ” 結點 */ rRChild=pRChild。 pRChild=r。即在結點的前序序列中，第一個結點必是根 D；而另一方面，由于中序遍歷是先遍歷左子樹 L，然后訪問根 D，最后遍歷右子樹 R，則根結點 D將中序序列分割成兩部分：在 D之前是左子樹結點的中序序列，在 D之后是右子樹結點的中序序列。 樹、森林和二叉樹的關系 樹的存儲結構 樹、森林與二叉樹的相互轉換 樹與森林遍歷 樹的存儲結構 樹的主要存儲方法有： 1. 雙親表示法： 用一組 連續(xù)的空間來存儲樹中的結點，在保存每個結點的同時附設一個指示器來指示其雙親結點在表中的位置，其結點的結構如下： 數(shù)據 雙親 Data Parent 1 2 4 5 6 3 7 1 6 1 5 1 4 0 3 0 2 1 1 Parent Data 5 4 3 2 1 0 結點序號 樹的雙親表示法如下圖： 雙親表示法的優(yōu)點： 利用了 樹中每個結點（根結點除外）只有一個雙親結點的性質，使得查找某個結點的雙親結點非常容易。 }TNode。 2. 孩子表示法： 通常是把每個結點的孩子結點排列起來，構成一個單鏈表，稱為孩子鏈表。 /*指向下一個孩子結點的指針 */ }ChildNode。 typedef struct /* 樹的定義 */ { DataNode nodes[MAX]。 ● 1 ∧ ● 2 ● ∧ 4 ● ∧ 5 ● ∧ 6 ∧ ∧ 7 ∧ ● 3 ∧ 孩子兄弟表示法的存儲結構： typedef struct CSNode { DataType data。 樹、森林與二叉樹的相互轉換 1. 樹轉換為二叉樹 我們約定樹中 每一個結點的孩子結點按從左到右的次序順序編號，也就是說，把樹作為有序樹看待。 A F H E G C B D A F H E G C B D A F H E G C B D 結論： 從轉換過程可看出： 樹中的任意一個結點都對應于二叉樹中的一個結點。 樹與二叉樹的對應關系及轉換方法 A C B D E A C B D E 對應 A ∧ B ∧ A E ∧ ∧ D ∧ ∧ D ∧ ∧ E ∧ ∧ C B ∧ A ∧ A ∧ C B ∧ E ∧ ∧ D ∧ ∧ 解 釋 解 釋 存 儲 存 儲 2. 森林轉換為二叉樹 森林轉換為二叉樹的方法為： （ 1）將森林中的每棵樹轉換成相應的二叉樹。 。 D A B C E F G H I J D A B C E F G H I J H I J G 用遞歸的方法描述其轉換過程為： 若 B是一棵二叉樹， T是 B的根結點， L是 B的左子樹， R為 B的右子樹，且 B對應的森林 F（ B）中含有的 n棵樹為 T1,T2, … ,Tn，則有： （ 1） B為空，則 F（ B）為空的森林（ n＝ 0）。 A B E C D F G H 如圖中樹的先根遍歷序列為： ABECFHGD。 樹的遍歷結果與由樹轉化成的二叉樹有如下對應關系： 樹的先根遍歷 轉化二叉樹的前序遍歷 樹的后根遍歷 轉化二叉樹的中序遍歷 void RootFirst(CSTree root) { if (root!=NULL) { Visit(root data)。 } } } 方法一 void RootFirst(CSTree root) { if (root!=NULL) { Visit (root data)。 ②先序遍歷第一棵樹的根結點的子樹森林。 ③中序 遍歷除去第一棵樹之后剩余的樹構成的森林。 哈夫曼樹及其應用 哈夫曼樹 哈夫曼編碼 1. 哈夫曼樹的 基本概念： 路徑 ：指從一個結點到另一個結點之間的分支序列。 樹的帶權路徑長度 ：為樹中所有葉子結點的帶權路徑長度之和，通常記為： 其中 n為葉子結點的個數(shù)， wi為第 i個葉子結點的權值， li為第 i個葉子結點的路徑長度。 (a) WPL=2 2＋ 2 3+2 4+2 7=32 2 3 4 7 4 2 3 7 (b) WPL=1 2＋ 2 3+3 4+3 7=41 3 7 4 2 (c) WPL=1 7＋ 2 4+3 3+3 2=30 2. 構造哈夫曼樹 哈夫曼樹 又叫 最優(yōu)二叉樹 ，它是由 n個帶權葉子結點構成的所有二叉樹中 帶權路徑長度 WPL最短 的二叉樹。 (4)重復（ 2）、（ 3）操作，直到森林中只含有一棵二叉樹為止，此時得到的這棵二叉樹就是哈夫曼樹。由于每個結點同時還包含其雙親信息和孩子結點的信息，所以構成一個靜態(tài)三叉鏈表。 /* 結點的權值 */ int parent 。 /* HuffmanTree是一個結構數(shù)組類型， 0號單元不用。i++) ht[i] ={ w[i],0,0,0}。i++) ht[i] ={0,0,0,0}。 /* 在 ht[1] ~ ht[i1] 的范圍內選擇兩個 parent為 0且 weight最小的結點 ， 其序號分別賦值給 s s2返回 */ ht [i].weight= ht [s1].weight+ ht [s2].weight。 ht [i].RChild=s2。利用哈夫曼樹，我們可以得到平均長度最短的編碼。 (2)哈夫曼編碼： 對一棵具有 n個葉子的哈夫曼樹，若對樹中的每個左分支賦予 0，右分支賦予 1，則從根到每個葉子的通路上，各分支的賦值分別構成一個二進制串，該二進制串就稱為哈夫曼編碼。 定理 62 哈夫曼編碼是最優(yōu)前綴碼