1、2022-3-222022-3-22v 6.1 樹(tree)的(遞歸)定義v 樹是 n(0) 個結點的有限集 T，在非空樹中：v 有且僅有一個特定的結點，稱為樹的根(root)v n1時，其余結點可分為 m(0) 個互不相交的有限集 T1,T2,Tm，其中每一個集合本身又是一棵樹，稱為根的子樹(subtree)樹：非線性數據結構，以分支關系定義的層次結構樹：非線性數據結構，以分支關系定義的層次結構A只有根結點的樹只有根結點的樹2022-3-22ABCDEFGHIJKLM有子樹的樹有子樹的樹根根子樹子樹子樹子樹子樹子樹2022-3-22v 基本術語v 結點(node)：樹的元素v 含數據項及若

2、干指向其子樹的分支v 結點的度(degree)：結點擁有的子樹數v 葉子(leaf)：度為 0 的結點v 樹的度：一棵樹中最大的結點度數2022-3-22v 基本術語(cont.)v 孩子(child)：結點的子樹的根v 雙親(parents)：孩子結點的上層結點v 兄弟(sibling)：同一雙親的孩子v 結點層次(level)：根為第 1 層，根的孩子為第 2 層v 樹的深度/高度(depth)：樹中結點的最大層次數2022-3-22v 基本術語(cont.)v 子孫：一個結點所有子樹中的結點。v 祖先：從根結點到達某結點路徑上的所有結點。v 有序樹/無序樹：如果樹中結點的各子樹從左到右是

3、有次序的，則稱該樹為有序樹；否則稱為無序樹v 森林(forest)：m(0) 棵互不相交的樹的集合2022-3-22ABCDEFGHIJKLM結點結點A的度：的度：3結點結點B的度：的度：2結點結點M的度：的度：0葉子：葉子：K，L，F，G，M，I，J結點結點A的孩子：的孩子：B，C，D結點結點B的孩子：的孩子：E，F結點結點I的雙親：的雙親：D結點結點L的雙親：的雙親：E結點結點B，C，D為兄弟為兄弟結點結點K，L為兄弟為兄弟樹的度：樹的度：3結點結點A的層次：的層次：1結點結點M的層次：的層次：4樹的深度：樹的深度：4結點結點F，G為堂兄弟為堂兄弟結點結點A是結點是結點F，G的祖先的祖先2

4、022-3-22v 6.2 二叉樹v 定義：二叉樹是 n0 個結點的有限集，它或為空樹(n=0)，或由一個根結點和兩棵分別稱為左、右子樹的互不相交的二叉樹構成v 特點：v 每個結點至多有二棵子樹(即不存在度大于 2 的結點)v 二叉樹的子樹有左、右之分，且其次序不能任意顛倒2022-3-22v 6.2 二叉樹v 基本形態：A只有根結點只有根結點的二叉樹的二叉樹 空二叉樹空二叉樹AB右子樹為空右子樹為空AB左子樹為空左子樹為空ABC左、右子樹左、右子樹均非空均非空度為度為2的有序樹的有序樹2022-3-22練習：練習：給出給出 3 個結點個結點A、B和和C構成的所有形態的二叉樹（不構成的所有形態

5、的二叉樹（不考慮結點值的差異）考慮結點值的差異）ABCABCABCABCABC2022-3-22v二叉樹性質 性質1：證明：證明：(歸納法歸納法) i=1時，只有一個根結點，時，只有一個根結點，2i-1=20=1，結論正確，結論正確 假設對所有假設對所有 j(1ji) 命題成立命題成立 即第即第 j 層上至多有層上至多有 2j-1 個結點個結點，則，則第第 i-1 層至多有層至多有 2i-2 個結點個結點 又二叉樹每個結點的度至多為又二叉樹每個結點的度至多為 2 第第 i 層上最大結點數是第層上最大結點數是第 i-1 層的層的 2 倍，即倍，即 22i-2=2i-1 故命題得證故命題得證二叉樹

6、的第二叉樹的第 i(1) 層上至多有層上至多有 2i-1 個結點個結點2022-3-22v 二叉樹性質 性質2：證明：由性質證明：由性質1，可得深度為，可得深度為k 的二叉樹最大結點數是的二叉樹最大結點數是1-22)(111 -kkikiii層最大結點數第深度為深度為 k(1) 的二叉樹至多有的二叉樹至多有 2k-1 個結點個結點2022-3-22 性質3：任何一棵二叉樹 T，如果其葉子數為 n0，度為 2 的結點數為 n2，則 n0=n2+1證明：設證明：設 n1 為二叉樹為二叉樹 T 中度為中度為 1 的結點數的結點數 因為：二叉樹中所有結點的度均小于或等于因為：二叉樹中所有結點的度均小于

7、或等于2 所以所以二叉樹的二叉樹的結點總數結點總數 n=n0+n1+n2 又又：除根結點外，其余結點都只有一個分支進入除根結點外，其余結點都只有一個分支進入 設設 B 為分支總數，則為分支總數，則 n=B+1 又：分支又：分支只能只能由度為由度為 1 和和 2 的結點射出，的結點射出，即即 B=n1+2n2 于是，于是，n=B+1=n1+2n2+1=n0+n1+n2 故：故：n0=n2+1v 二叉樹性質2022-3-22v 二叉樹特殊形式 滿二叉樹：深度為 k 且有 2k-1 個結點的二叉樹 特點：每層上的結點數都是最大值 完全二叉樹：深度為 k、有 n 個結點的完全二叉樹當且僅當，其每一個結

8、點都與深度為 k 的滿二叉樹中編號從 1 至 n 的結點一一對應 特點 葉子結點只可能在層次最大的兩層上出現 對任一結點，若其右分支下子孫的最大層次為 l，則其左分支下子孫的最大層次必為 l 或 l+12022-3-22證明：設二叉樹深度為證明：設二叉樹深度為 k，根據性質，根據性質 2 和完全二叉樹的定義，和完全二叉樹的定義，前前 k-1 層都是滿的，最后一層可以滿，也可以不滿，則：層都是滿的，最后一層可以滿，也可以不滿，則： 2k-11n2k1 即：即： 2k-1n+12k k1log2(n+1)k log2 (n+1)klog2(n+1)+1 因因 k 為整數，所以為整數，所以 k= 1

9、log2n 性質4：有 n 個結點的完全二叉樹深度1log2n2022-3-22證明：設二叉樹深度為證明：設二叉樹深度為 k，根據性質，根據性質 2 和完全二叉樹的定義，和完全二叉樹的定義，前前 k-1 層都是滿的，最后一層可以滿，也可以不滿，則：層都是滿的，最后一層可以滿，也可以不滿，則： 2k-1n2k 則：則：k1log2nk 即：即：log2nklog2n+1 因因 k 為整數，故為整數，故 k= 性質4：有 n 個結點的完全二叉樹深度1log2n1log2n2022-3-221231145891213671014151231145891267101234567123456哪個是完全二

10、叉樹？哪個是完全二叉樹？2022-3-22 性質5：對有 n 個結點的完全二叉樹按層編號，則對任一結點 i(1in)，有： (1) 若 i=1，則結點 i 是二叉樹的根，無雙親；若 i1，則其雙親編號i/2 (2) 若 2in，則結點 i 無左孩子；如果 2in，則其左孩子編號2i (3) 若 2i+1n，則結點 i 無右孩子；如果2i+1n，則其右孩子編號2i+12022-3-22 理想平衡二叉樹理想平衡二叉樹 / 理想平衡樹理想平衡樹 / 理想二叉樹理想二叉樹在一棵二叉樹中，若除最后一層外，其余層都是滿的，在一棵二叉樹中，若除最后一層外，其余層都是滿的，而最后一層上的結點可以任意分布而最后

11、一層上的結點可以任意分布顯然！理想平衡樹包括滿二叉樹和完全二叉樹顯然！理想平衡樹包括滿二叉樹和完全二叉樹2022-3-22練習：練習：任意一個有任意一個有 n 個結點的二叉樹，已知它有個結點的二叉樹，已知它有 m 個葉子，個葉子，請證明非葉結點中有請證明非葉結點中有 m-1 個結點的度為個結點的度為 2、其余度為、其余度為 1證明：設度為證明：設度為 1 的結點有的結點有 n1 個，度為個，度為 2 的有的有 n2 個個 則總結點則總結點 nn1n2m 又：又：nB1，B為分支數為分支數 且：且：Bn12n2 則：則：nn12n21 又：又：n1n2mn12n21 n2m12022-3-22練

12、習：練習：已知二叉樹有已知二叉樹有 50 個葉子結點，則該二叉樹的總結點數個葉子結點，則該二叉樹的總結點數至少應有多少個？至少應有多少個？解：設度為解：設度為 0、1、2 的結點數為的結點數為 n0、n1、n2，結點總數為，結點總數為 n n0=50，因有，因有 n0 = n2 + 1，則，則 n2=49 又結點總數又結點總數 n = n0+n1+n2，將上面結果代入得：，將上面結果代入得： n = 50 + n1 + 49，即，即 n=n1+99 由上式可知，當由上式可知，當 n1=0 時時n 最少，則最少，則 n 至少有至少有 99 個結點個結點2022-3-22v 二叉樹的存儲結構v 順

13、序存儲結構v 按滿二叉樹結點的層次編號，依次存放二叉樹的數據元素v 特點：v 結點間關系蘊含在其存儲位置中v 浪費空間，適于存滿二叉樹和完全二叉樹12345671 2 3 4 5 0 0 0 0 6 7 0 1 2 3 4 5 6 7 8 9 102022-3-22練習：練習： 假設二叉樹的存儲結構如下，畫出對應的二叉樹假設二叉樹的存儲結構如下，畫出對應的二叉樹25 15 36 10 20 32 48 4 11 18 0 1 2 3 4 5 6 7 8 9 I D P C F M E H N0 1 2 3 4 5 6 7 8 9 10 11 12 2022-3-22#define MAX_TR

14、EE_SIZE 100typedef TElemType SqBiTree MAX_TREE_SIZE;SqBiTree bt;二叉樹順序存儲結構的類型定義：二叉樹順序存儲結構的類型定義：注：下標為注：下標為 0 的元素存儲的元素存儲根結點根結點2022-3-22v 結點v 數據域：數據本身v 左指針：左孩子結點v 右指針：右孩子結點v 二叉鏈表v 由如上結點鏈接而成v 二叉樹v BiTNode bt; /二叉樹根結點v BiTree T; /指向二叉樹根結點的指針v 二叉樹的鏈式存儲結構（二叉鏈表）typedef struct BiTNode BTElemType data ; struct

15、 BiTNode *lchild, *rchild; BiTNode , *BiTree ;lchild data rchild 2022-3-22v 二叉樹的鏈式存儲結構（二叉鏈表）示例ABCDEFG AB C D E F GT (指向根結點的指針指向根結點的指針)2022-3-22v 二叉樹的鏈式存儲結構（二叉鏈表）示例 AB C D E F GT2022-3-22靜態靜態二叉鏈表：數組存儲結點及父子關系二叉鏈表：數組存儲結點及父子關系#define MAX_TREE_SIZE 100 /存儲結點最大個數存儲結點最大個數0123456789992022-3-22靜態靜態二叉鏈表：數組存儲結

16、點及父子關系二叉鏈表：數組存儲結點及父子關系#define MAX_TREE_SIZE 100 /存儲結點最大個數存儲結點最大個數/結點結點struct SBiTreeNode TElemType data; /數據數據 int left , right ; /左、右孩子對應數組元素左、右孩子對應數組元素下標下標 ;012345678999dataleftright2022-3-22靜態靜態二叉鏈表：數組存儲結點及父子關系二叉鏈表：數組存儲結點及父子關系#define MAX_TREE_SIZE 100 /存儲結點最大個數存儲結點最大個數struct SBiTreeNode /結點結點 TEl

17、emType data; /數據數據 int left , right ; /左、右孩子對應數組元素左、右孩子對應數組元素下標下標 ;typedef SBiTreeNode SBiTree MAX_TREE_SIZE ; /靜態二叉鏈表靜態二叉鏈表999876543210dataleftrightSBiTree2022-3-22靜態靜態二叉鏈表：數組存儲結點及父子關系二叉鏈表：數組存儲結點及父子關系012345678999ABDCEHFGI12450700000306089000dataleftrighttypedef SBiTreeNode SBiTree MAX_TREE_SIZE ; /

18、靜態二叉鏈表靜態二叉鏈表*注意：元素注意：元素 0 不放數據，其不放數據，其左左(下標下標)指針指針指向指向根結點根結點元素元素 指針為指針為 0 表示：空表示：空SBiTree根結點根結點練習：練習：畫出以上數組所示二叉樹。畫出以上數組所示二叉樹。2022-3-22二叉樹基本操作二叉樹基本操作 I (P127)v輔助：初始化 / 銷毀 / 清空 / 空樹判定vInitBiTree / DestoryBiTree / ClearBiTree / BiTreeEmptyv數據值：取值 / 賦值vValue / Assignv導航：取根/父/左子/右子/左兄弟/右兄弟結點vRoot/Parent/

19、LeftChild/RightChild/LeftSibling/RightSiblingv結點：插/刪子結點vInsertChild / DeleteChild2022-3-22v 計數：樹高度 / 結點數 / 葉子數v Depth / Count / LeafCountv 創建 / 輸出v CreateBiTree / PrintBiTreev 遍歷：前序 / 中序 / 后序 / 層序v PreOrderTraverse / InOrderTraverse / PostOrderTraverse / LevelOrderTraverse2022-3-22(1) 二叉樹高度：二叉樹高度：De

20、pth(T) Depth(T) = 0，T = NULLT (指向根結點的指針指向根結點的指針)Depth( T )：樹高度：樹高度/深度，最大結點層次深度，最大結點層次T (空樹空樹)2022-3-22(1) 二叉樹高度：二叉樹高度：Depth(T) Depth (T) = Max ( Depth (T-lchild ) , Depth (T-rchild ) ) + 1T (非空樹，非空樹，T 指向根結點指向根結點)lchild rchildDepth(T-lchild)Depth(T-rchild)2022-3-22Depth(T)0 ，TNULL Max ( Depth(T-lchil

21、d) , Depth(T-rchild) ) + 1，TNULLint BiTreeDepth( BiTree *T ) if ( T = NULL) /空樹，高度空樹，高度=0 return 0; else /非空樹非空樹 lDepth = BTHeight( T-lchild ); /左子樹高度左子樹高度 rDepth = BTHeight( T-rchild ); /右子樹高度右子樹高度 if (lDepth rDepth ) return lDepth + 1; /左子樹更高左子樹更高 else return rDepth + 1; /右子樹更高右子樹更高2022-3-22(2) 二叉

22、樹結點總數：二叉樹結點總數：Count(T)Count(T)=0 ，TNULL Count(T-lchild) + Count(T-rchild) + 1，TNULLT (非空樹，非空樹，T 指向根結點指向根結點)lchild rchildCount(T-lchild)Count(T-rchild)2022-3-22Count(T)=0 , T=NULL Count(T-lchild) + Count(T-rchild) + 1, TNULLint Count( BiTree T) if ( T = NULL) /空樹空樹 return 0; else /非空樹非空樹 lCount = Cou

23、nt( T-lchild ); /左子樹結點數左子樹結點數 rCount = Count( T-rchild ); /右子樹結點數右子樹結點數 return ( lCount + rCount +1); 2022-3-22(3) 二叉樹葉子數：二叉樹葉子數：LeafCount(T)LeafCount(T)0 , T = NULL LeafCount(T-lchild)+LeafCount(T-rchild), 其它其它1 , T 為葉子為葉子T (非空樹，非空樹，T 指向根結點指向根結點)lchild rchildLeafCount(T-lchild)LeafCount(T-rchild)20

24、22-3-22LeafCount(T)0 , T = NULL LeafCount(T-lchild)+LeafCount(T-rchild), 其它其它1 , T 為葉子為葉子int LeafCount( BiTree T ) if ( T = NULL ) /空樹空樹 return 0; else if( T-lchild = NULL & T-rchild = NULL) /葉子葉子 return 1; else /非葉子結點非葉子結點 lCount = LeafCount( T-lchild); rCount = LeafCount( T-rchild); return (lC

25、ount + rCount); 2022-3-22(4) 用括號表示法描述二叉樹：根用括號表示法描述二叉樹：根 ( 左子樹左子樹, 右子樹右子樹 )Ex1. 空樹空樹空串空串Ex2. 葉子（左右子樹均為空）葉子（左右子樹均為空）AEx3. 只有左子樹只有左子樹A(B)Ex4. 左右子樹均非空左右子樹均非空A( B , C) AB C2022-3-22(4) 用括號表示法描述二叉樹：根用括號表示法描述二叉樹：根 ( 左子樹左子樹, 右子樹右子樹 )Ex1. 空樹空樹空串空串Ex2. 葉子（左右子樹均為空）葉子（左右子樹均為空）AEx3. 只有左子樹只有左子樹A(B)Ex4. 左右子樹均非空左右子

26、樹均非空A( B , C)Ex5. 只有右子樹只有右子樹A( , C) A C2022-3-22練習：練習：用括號表示法描述左圖的二叉樹用括號表示法描述左圖的二叉樹 AB C D E F GTA( B( C, D( E( ,G), F) )先序遍歷結果序列先序遍歷結果序列的另類表示法！的另類表示法！2022-3-22 AB C D E F GT(4) 用括號表示法輸出二叉樹：用括號表示法輸出二叉樹：PrintBiTree(T) 若樹不空則執行若樹不空則執行 ，否則停止，否則停止 輸出樹的根結點值輸出樹的根結點值(字符字符) 若根結點有孩子則執行若根結點有孩子則執行 ，否則停止，否則停止 輸出左

27、括號：輸出左括號：( 遞歸遞歸處理左子樹，完成后返回處理左子樹，完成后返回 若存在右孩子則輸出逗號：若存在右孩子則輸出逗號：, 遞歸遞歸處理右子樹，完成后返回處理右子樹，完成后返回 輸出右括號：輸出右括號：) 結束結束2022-3-22(4) 用括號表示法輸出二叉樹：用括號表示法輸出二叉樹：PrintBiTree(T)void PrintBiTree ( BiTree T) / T 是指向根的指針是指向根的指針 if ( T != NULL) /若樹不空則執行，否則停止若樹不空則執行，否則停止 2022-3-22(4) 用括號表示法輸出二叉樹：用括號表示法輸出二叉樹：PrintBiTree(T

28、)void PrintBiTree ( BiTree T) / T 是指向根的指針是指向根的指針 if ( T != NULL) /若樹不空則執行，否則停止若樹不空則執行，否則停止 coutdata; /輸出根結點的值輸出根結點的值 /若根結點有孩子則執行，否則停止若根結點有孩子則執行，否則停止 if ( T-lchild != NULL | T-rchild != NULL) 2022-3-22(4) 用括號表示法輸出二叉樹：用括號表示法輸出二叉樹：PrintBiTree(T)void PrintBiTree ( BiTree T) / T 是指向根的指針是指向根的指針 if ( T !=

29、NULL) /若樹不空則執行，否則停止若樹不空則執行，否則停止 coutdata; /輸出根結點的值輸出根結點的值 /若根結點有孩子則執行，否則停止若根結點有孩子則執行，否則停止 if ( T-lchild != NULL | T-rchild != NULL) coutlchild ); /遞歸處理左子樹遞歸處理左子樹 2022-3-22(4) 用括號表示法輸出二叉樹：用括號表示法輸出二叉樹：PrintBiTree(T)void PrintBiTree ( BiTree T) / T 是指向根的指針是指向根的指針 if ( T != NULL) /若樹不空則執行，否則停止若樹不空則執行，否則

30、停止 coutdata; /輸出根結點的值輸出根結點的值 /若根結點有孩子則執行，否則停止若根結點有孩子則執行，否則停止 if ( T-lchild != NULL | T-rchild != NULL) coutlchild ); /遞歸處理左子樹遞歸處理左子樹 if (T-rchild != NULL) cout,; /輸出逗號輸出逗號 2022-3-22(4) 用括號表示法輸出二叉樹：用括號表示法輸出二叉樹：PrintBiTree(T)void PrintBiTree ( BiTree T) / T 是指向根的指針是指向根的指針 if ( T != NULL) /若樹不空則執行，否則停止

31、若樹不空則執行，否則停止 coutdata; /輸出根結點的值輸出根結點的值 /若根結點有孩子則執行，否則停止若根結點有孩子則執行，否則停止 if ( T-lchild != NULL | T-rchild != NULL) coutlchild ); /遞歸處理左子樹遞歸處理左子樹 if (T-rchild != NULL) coutrchild ); /遞歸處理右子樹遞歸處理右子樹 coutdata = ch; /保存數據保存數據 p-lchild = NULL; /初始化左右指針初始化左右指針 p-rchild = NULL; /end switch(5) 用括號表示法創建二叉樹：用括號

32、表示法創建二叉樹：2022-3-22BiTree CreateBiTree(char * str) default: /其它字符其它字符(即數據即數據) /新結點與棧頂結點鏈接新結點與棧頂結點鏈接 if ( bt = NULL ) /空樹，新結點是根空樹，新結點是根 bt = p; else if ( k = 1 ) /新結點是棧頂結點的左孩子新結點是棧頂結點的左孩子 st top - lchild = p ; else if ( k = 2 ) /新結點是棧頂結點的右孩子新結點是棧頂結點的右孩子 st top - rchild = p; /end switch(5) 用括號表示法創建二叉樹：

33、用括號表示法創建二叉樹：2022-3-22v 6.3 遍歷二叉樹v 樹的遍歷v 遍歷按某條路徑訪問二叉樹的每個結點，使每個結點被訪問一次且僅被訪問一次v 常用方法v 先根（序）遍歷：訪問根結點；依次先根遍歷根的每棵子樹v 后根（序）遍歷：依次后根遍歷每棵子樹；訪問根結點v 層次遍歷：訪問第一層結點；依次遍歷第二層，第n層結點2022-3-22v二叉樹遍歷v先序：訪問根結點；先序遍歷左子樹、右子樹v中序：中序遍歷左子樹；訪問根結點；中序遍歷右子樹v后序：后序遍歷左、右子樹；訪問根結點v層次：從上到下、從左到右訪問各層結點DLRLDR、LRD、DLRRDL、RLD、DRL2022-3-22ADBC

34、D L RAD L RD L RBDCD L R先序遍歷序列：先序遍歷序列：A B D C先序遍歷先序遍歷:2022-3-22ADBCL D RBL D RL D RADCL D R中序遍歷序列：中序遍歷序列：B D A C中序遍歷中序遍歷:2022-3-22ADBC L R DL R DL R DADCL R D后序遍歷序列：后序遍歷序列： D B C A后序遍歷后序遍歷:B2022-3-22-+/a*b-efcd先序遍歷先序遍歷：中序遍歷：中序遍歷：后序遍歷：后序遍歷：- + a * b - c d / e f-+a*b-cd/ef-+a*b-c d/e f2022-3-22二叉樹遍歷（遞

35、歸）算法/二叉鏈表定義二叉鏈表定義typedef int TElemType ; typedef struct BiTNode TElemType data; struct BiTNode *lchild, *rchild; BiNode , *BiTree ;lchild data rchild 2022-3-22先序遍歷（遞歸）算法int PreOrderTraverse ( BiTree T ) if ( T != NULL) /遍歷指針不空，指向某子樹根結點遍歷指針不空，指向某子樹根結點 printf ( “%dt” , T-data ); /根根 PreOrderTraverse (

36、 T-lchild ); /左左 PreOrderTraverse ( T-rchild ); /右右 2022-3-22主程序主程序pre( T )返回返回返回返回pre(T R);返回返回返回返回pre(T R);ACBDTBprintf(B);pre(T L);BTAprintf(A);pre(T L);ATDprintf(D);pre(T L);DTCprintf(C);pre(T L);C返回返回T左是空返回左是空返回pre(T R);T左是空返回左是空返回T右是空返回右是空返回T左是空返回左是空返回T右是空返回右是空返回pre(T R);先序序列：先序序列：A B D Cint P

37、reOrderTraverse ( BiTree T ) if ( T != NULL) printf ( “%dt” , T-data ); PreOrderTraverse ( T-lchild ); PreOrderTraverse ( T-rchild ); 2022-3-22/ 中序遍歷中序遍歷int InOrderTraverse ( BiTree T ) if ( T != NULL) InOrderTraverse ( T-lchild ); /左左 printf ( “%dt” , T-data ); /根根 InOrderTraverse ( T-rchild ); /右右

38、 2022-3-22/ 后序遍歷后序遍歷int PostOrderTraverse ( BiTree T ) if ( T != NULL) PostOrderTraverse ( T-lchild ); /左左 PostOrderTraverse ( T-rchild ); /右右 printf ( “%dt” , T-data ); /根根 2022-3-22說明：說明：對于先序、中序、后序遍歷序列中：對于先序、中序、后序遍歷序列中： 由由先序先序和和中序中序遍歷結果遍歷結果可以唯一可以唯一確定一棵二叉樹。確定一棵二叉樹。 由由后序后序和和中序中序遍歷結果遍歷結果可以唯一可以唯一確定一棵二

39、叉樹。確定一棵二叉樹。 由由先序先序和和后序后序遍歷結果遍歷結果不能唯一不能唯一確定一棵二叉樹。確定一棵二叉樹。若二叉樹的先序、中序序列相同，則該二叉樹的形態為：若二叉樹的先序、中序序列相同，則該二叉樹的形態為： 空樹、只有根結點、右單支空樹、只有根結點、右單支若二叉樹的后序、中序序列相同，則該二叉樹的形態為：若二叉樹的后序、中序序列相同，則該二叉樹的形態為： 空樹、只有根結點、左單支空樹、只有根結點、左單支若二叉樹的先序、后序序列相同，則該二叉樹的形態為：若二叉樹的先序、后序序列相同，則該二叉樹的形態為： 空樹、只有根結點空樹、只有根結點2022-3-22例：例：二叉樹的先序、中序遍歷結果如

40、下，畫出該二叉樹二叉樹的先序、中序遍歷結果如下，畫出該二叉樹 先序：先序：ABCDEFG 中序：中序：CBDEAFGABFCDEG2022-3-222、一個二叉樹的先序、中序和后序分別如下，其中一部分未顯示、一個二叉樹的先序、中序和后序分別如下，其中一部分未顯示出來，試求出空格處的內容，并畫出該二叉樹。出來，試求出空格處的內容，并畫出該二叉樹。 先序：先序：_B_F_ICEH_G 中序：中序：D_KFIA_EJC_ 后序：后序：_K_FBHJ_G_A答答: ABDFKICEHJG DBKFIAHEJCG DKIFBHJEGCA練習：練習：1、二叉樹的后序、中序周游結果如下，畫出該二叉樹。、二叉

41、樹的后序、中序周游結果如下，畫出該二叉樹。 后序：后序：43268751 （每位數字代表一個結點）（每位數字代表一個結點） 中序：中序：243165782022-3-22ABCDEFG按先序遍歷序列，建立二叉鏈表按先序遍歷序列，建立二叉鏈表A B C 0 0 D E 0 G 0 0 F 0 0 0 (0 表示空表示空) 2022-3-22BiTree createbt ( ) BiTree *bt; char ch; scanf(“%c”, &ch); /讀入讀入 1 個字符個字符 if ( ch =0) /空空 bt = NULL; else bt = (BiTree) malloc

42、 ( sizeof ( BiNode ); bt-data = ch; bt-lchild = createbt (); /遞歸讀入左子樹遞歸讀入左子樹 bt-rchild = createbt (); /遞歸讀入右子樹遞歸讀入右子樹 按先序遍歷序列，遞歸建立二叉鏈表算法按先序遍歷序列，遞歸建立二叉鏈表算法2022-3-22v 6.3.2 線索二叉樹v 定義：v 二叉樹遍歷序列中兩個相鄰結點互稱為前驅與后繼v 指向前驅或后繼結點的指針稱為線索v 加上線索的二叉樹叫線索二叉樹v 按遍歷序列使二叉樹變為線索二叉樹的過程叫線索化2022-3-22v 6.3.2 線索二叉樹v 實現v n 個結點的二叉

43、鏈表中，必有 n+1 個空鏈域v 擴展二叉鏈表結點：標志域 LTag、RTagv LTag： 表示 lchild 指針的含義，0左孩子；1前驅v RTag： 表示 rchild 指針的含義，0右孩子；1后繼 lchild LTag data RTag rchild2022-3-22ABCDE A B D C ET先序序列：先序序列：ABCDE先序線索二叉樹先序線索二叉樹00001111 11v Ex.1 先序線索二叉樹2022-3-22ABCDE A B D C ET中序序列：中序序列：BCAED中序線索二叉樹中序線索二叉樹0000111111v Ex.2 中序線索二叉樹2022-3-22 A

44、 B D C ET后序序列：后序序列：CBEDA后序線索二叉樹后序線索二叉樹0000111111v Ex.3 后序線索二叉樹ABCDE2022-3-226.3.2 線索二叉樹v 二叉樹線索化的目的v 遍歷時，不再需要棧2022-3-226.4 樹和森林v 樹 vs. 二叉樹v 相同點：層次結構、唯一根結點v 差異點：樹結點允許 2 個以上的子結點；二叉樹結點最多 2 個子結點v 森林v 不相交的樹集合2022-3-226.4.1 樹的存儲結構v 雙親表示法v 孩子表示法v 多重鏈表v 孩子鏈表v 孩子兄弟表示法2022-3-226.4.1 樹的存儲結構 雙親表示法：子結點保存父結點位置信息v

45、數據域：存放結點本身信息v 雙親域：指示雙親結點在數組中位置v 6.4 樹和森林/結點結構結點結構typedef struct PTNode TElemType data; int parent; PTNode;dataparent數據域數據域雙親域雙親域2022-3-226.4.1 樹的存儲結構 雙親表示法v 6.4 樹和森林/ 雙親表示的樹結構雙親表示的樹結構typedef struct PTNode nodesMAX_TREE_SIZE; int r, n; PTree;012MAX_TREE_SIZEdataparent結點數組結點數組根結點位置根結點位置結點個數結點個數2022-3-

46、22abcdefhgiacdefghib0122355516012345789dataparent如何找孩子結點如何找孩子結點如何找兄弟結點如何找兄弟結點v雙親表示法示例19根結點放在根結點放在位置位置 1結點數結點數92022-3-22 孩子表示法(多重鏈表)v 每個結點有多個指針域，分別指向其子樹的根v 結點同構： 結點指針個數相等 樹的度 Ddata child1 child2 . childDdata degree child1 child2 . childd6.4.1 樹的存儲結構v 結點不同構：結點指針個數不等 結點的度 d結點的度結點的度 d樹的度樹的度 D2022-3-22ab

47、cdefhgi 2 3 4 5 9 7 8 6如何找雙親結點如何找雙親結點孩子表示法示例6012345789acdefghibdata firstchild192022-3-22/表頭數組元素結點表頭數組元素結點typedef struct TElemType data; int parent; ChildPtr firstchild; /孩子孩子鏈表頭指針鏈表頭指針 CTBox ;父結點在數組中的位置父結點在數組中的位置帶雙親的孩子鏈表parent：指示父結點位置firstchild：孩子鏈表頭指針6.4.1 樹的存儲結構2022-3-22abcdefhgi612345789acdefghi

48、bdata 2 3 4 5 9 7 8 6012235551parent firstchild帶雙親的孩子鏈表法示例2022-3-22孩子兄弟表示法(二叉鏈表)v左指針 自己的第 1 個孩子結點v右指針 自己的下一個兄弟typedef struct CSNode TElemType data; struct CSNode *firstchild, /第一個孩子第一個孩子 *nextsibling; /下一個兄弟下一個兄弟 CSNode, *CSTree;6.4.1 樹的存儲結構2022-3-22 孩子兄弟表示法示例abcdefhgi a b c d e f g h i 問題：破壞了樹的層次關系

49、2022-3-22 孩子兄弟表示法的另類解釋！abcdefhgi a b c d e f g h i二叉鏈表即可表示樹二叉鏈表即可表示樹也可表示二叉樹也可表示二叉樹abcdefhgi2022-3-22abcdefhgi a b c d e f g h i二叉鏈表即可表示樹，也可表示二叉樹二叉鏈表即可表示樹，也可表示二叉樹樹與二叉樹之間可以一一對應！樹與二叉樹之間可以一一對應！可以相互轉換可以相互轉換abcdefhgi2022-3-22v 將樹轉換成二叉樹v 加線v 兄弟之間加連線v 抹線v 除左孩子外，去除與其余孩子之間的連線v 旋轉v 以根結點為軸心，整樹順時針旋轉 456.4.2 森林與二

50、叉樹的轉換2022-3-22v 樹轉換成二叉樹示例v 加線、抹線、旋轉ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI轉換得到的二叉樹其右子樹一定為空轉換得到的二叉樹其右子樹一定為空加線加線抹線抹線旋轉旋轉2022-3-22v 二叉樹轉換成樹v 加線v 若結點 p 是其父結點的左孩子，則將 p 的右孩子，右孩子的右孩子，沿分支找到的所有右孩子，都與p 的父結點連線v 抹線v 抹掉原二叉樹中父結點與右孩子之間的連線v 調整v 將結點按層次排列，形成樹結構2022-3-22v 二叉樹轉換成樹示例v 加線、抹線、調整ABCDEFGHIABCDEFGHIABC

51、DEFGHIABCDEFGHIABCDEFGHI加線加線抹線抹線調整調整2022-3-22v 森林轉換成二叉樹v （樹）轉換v 各棵樹分別轉換成二叉樹v （根）連線v 每棵樹根結點用線相連v 旋轉v 第一棵樹根結點為二叉樹根v 以根結點為軸順時針旋轉，構成二叉樹型結構6.4.2 森林與二叉樹的轉換2022-3-22v 森林轉換成二叉樹示例ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ樹轉換樹轉換根連線根連線旋轉旋轉2022-3-22v 二叉樹轉換成樹或森林v 加線v 若結點是左孩子，則將該結點的右孩子、右孩子的右孩子，都與該結點的父結點連線v 抹線v 抹去原二

52、叉樹中所有父結點與右孩子之間的連線v 還原v 整理上兩步的結果，使之結構層次分明6.4.2 森林與二叉樹的轉換2022-3-22v 二叉樹轉換成樹或森林v 加線、抹線、還原ABCDEFGHIJABCDEFGHIJ加線加線抹線抹線調整調整ABCDEFGHIJABCDEFGHIJABCDEFGHIJ2022-3-22v 6.6 赫夫曼樹及其應用葉結點到根的路徑長度葉結點權值其中：記作：kknkkklwlwWPL1v Huffman樹v 設有 n 個權值 w1,w2,wnv 構造有 n 個葉結點的二叉樹，其葉子結點的權值wiv WPL 最小的二叉樹叫 Huffman 樹結點帶權路徑長度結點帶權路徑長

53、度：根到該結點的路徑長度與該結點權值的乘積樹帶權路徑長度樹帶權路徑長度：所有葉結點的帶權路徑長度之和2022-3-22例例 有有4個結點，權值分別為個結點，權值分別為7，5，2，4，構造有，構造有4個葉子結點的二叉樹個葉子結點的二叉樹abcd7524WPL=7*2+5*2+2*2+4*2=36dcab2475WPL=7*3+5*3+2*1+4*2=46abcd7524WPL=7*1+5*2+2*3+4*3=35樹的帶權路徑樹的帶權路徑長度最短長度最短2022-3-22v Huffman 樹的構造v 給定 n 個權值 w1,w2,wn1 初始化：構造 n 棵只有根結點的二叉樹，權值為 wj2 迭

54、代選擇(貪心)：森林中選取 2 棵根結點權值最小的樹作左右子樹，構造一棵新二叉樹v 新二叉樹根結點權值 左右子樹根結點權值和3 重復步驟2，直到只剩一棵樹時，算法結束2022-3-22練習：練習：w = 5, 29, 7, 8, 14, 23, 3, 11 51429 7823 3111429 7823 1135887151429233581111358191429238715113581929 23148715292914871529113581923422022-3-22291487152911358192342113581923422914871529581135819234229148

55、7152958100WPL=？271Huffman 樹可樹可以不唯一！以不唯一！練習：練習：w = 5, 29, 7, 8, 14, 23, 3, 11 2022-3-22v Huffman 樹的應用：Huffman 編碼v 數據通信，壓縮電文用的二進制編碼v Ex. 設要傳送的字符串ABACCDA(定長定長)編碼：編碼：A00 B01 C10 D1100010010101100 14位位若采用不等長編碼，讓若采用不等長編碼，讓出現次數較多的字符盡可能用短編碼出現次數較多的字符盡可能用短編碼則轉換的二進制字符串便可能減少則轉換的二進制字符串便可能減少2022-3-22若編碼為：若編碼為： A0

56、 B00 C1 D-01 關鍵：關鍵：不等長編碼方案中，必須使任一字符的編碼不等長編碼方案中，必須使任一字符的編碼都不是另一個字符的編碼的前綴，即都不是另一個字符的編碼的前綴，即前綴編碼前綴編碼 ABACCDA 000011010 9位位但：但： 0000AAAA ABA BB重碼重碼2022-3-22編碼方案 ：A0B110C10D1110110010101110前綴編碼前綴編碼二叉樹二叉樹ACBD000111規定：規定：左分支用左分支用“0”表示表示右分支用右分支用“1”表示表示前綴編碼前綴編碼要傳送的字符串ABACCDA2022-3-22譯碼：從根出發，逐個接收字符，遇“0”向左、遇“1

57、”向右，到達葉子、譯出一個字符0 1 1 0 0 1 0 1 0 1 1 1 0ACBD000111A前綴編碼前綴編碼BA CCDA2022-3-22練習練習v 電文由字母 S, W, P, U, C, T, E, D 組成，字母出現頻率(%)為 5, 25, 3, 6, 10, 11, 36, 4v 畫出 Huffman 樹，給出 Huffman 編碼v 求出平均碼長v 給出電文 swpucsse 的對應編碼串v 給出編碼串 0001011001011 的對應電文2022-3-22v字母字母 S, W, P, U, C, T, E, D , 頻率頻率 5, 25, 3, 6, 10, 11,

58、 36, 4 v 畫出畫出 Huffman 樹，給出樹，給出 Huffman 編碼編碼10061393625221771011114365PDCTSUWE00000001111111 S WPUCTED 0110 10 0000 0111 001 010 11 0001 2022-3-22v字母字母 S, W, P, U, C, T, E, D , 頻率頻率 5, 25, 3, 6, 10, 11, 36, 4 v 求出平均碼長求出平均碼長(4522543463103112364 4)/1002.572022-3-22v字母字母 S, W, P, U, C, T, E, D , 頻率頻率 5,

59、 25, 3, 6, 10, 11, 36, 4 v 給出電文給出電文 swpucsse 的對應編碼串的對應編碼串v 0110 10 0000 0111 001 0110 0110 11 S WPUCTED 0110 10 0000 0111 001 010 11 0001 2022-3-22v字母字母 S, W, P, U, C, T, E, D , 頻率頻率 5, 25, 3, 6, 10, 11, 36, 4 v 給出編碼串給出編碼串 0001011001011 的對應電文的對應電文v DSTE10061393625221771011114365PDCTSUWE0000000111111

60、12022-3-22typedef struct unsigned int weight; unsigned int parent , lchild , rchild ; HTNode , *HuffmanTree ;下標weightparentlchildrchild123456789101112131415例例 w=5, 29, 7, 8, 14, 23, 3, 112022-3-22int Huffman( HuffmanTree HT, int *w , int n ) for( i = 1 ; i 2*n ;i+) / 初始化初始化 HTi.parent = HTi.lchild = HTi.rchild = 0