【正文】 teBiTree(amp。 第一節(jié) 二叉樹的定義 ? BiTreeEmpty(T)。 操作結(jié)果：返回 T 的根。 初始條件：二叉樹 T 存在， e 是 T 中某個結(jié)點。 初始條件：二叉樹 T 存在， e 是 T 中某個結(jié)點。 初始條件：二叉樹 T 存在 ,visit 是對結(jié)點操作的應用函數(shù)。 初始條件：二叉樹 T存在， visit 是對結(jié)點操作的應用函數(shù)。T)。 第一節(jié) 二叉樹的定義 ? InsertChild(amp。 操作結(jié)果：根據(jù) LR 為 0 或 1，刪除 T 中 p 所指結(jié)點的左或右子樹。 第二節(jié) 二叉樹的性質(zhì) ? 性質(zhì) 4 ： 具有 n 個結(jié)點的完全二叉樹的深度為 ? log2 n? +1 第二節(jié) 二叉樹的性質(zhì) 假設 n=4, ? log2 n ? +1= ? log2 4 ? +1=3 1 2 3 4 假設 n=7, ? log2 n ? +1= ? log2 7 ? +1=4 1 2 3 4 5 6 7 8 ? 性質(zhì) 5 若對含 n 個結(jié)點的完全二叉樹從上到下且從左至右進行 1 至 n 的編號，則對完全二叉樹中任意一個編號為 i 的結(jié)點（ 性質(zhì) 1可由性質(zhì) 2， 3推出，證明略 ）： (1) 若 i=1，則該結(jié)點是二叉樹的根，無雙親， 否則，編號為 ?i/2? 的結(jié)點為其 雙親 結(jié)點； (2) 若 2in，則該結(jié)點無左孩子， 否則，編號為 2i 的結(jié)點為其 左孩子 結(jié)點； (3) 若 2i+1n，則該結(jié)點無右孩子結(jié)點， 否則，編號為 2i+1 的結(jié)點為其 右孩子 結(jié)點 。 // 左右孩子指針 struct TriTNode *parent。 中（根）序的遍歷算法： 第一節(jié) 遍歷二叉樹 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。 ? 先序序列： 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é) 遍歷二叉樹 構(gòu)造二叉鏈表表示的二叉樹的遞歸算法 Status CreateBiTree(BiTree amp。 } return OK。 //Link==0:指針 ,Thread==1:線索 typedef struct BiThrNode { TElemType data。 ThrtRTag=Thread。 //最后一個結(jié)點線索化 Thrtrchild=pre。 //保持 pre指向 p的前驅(qū) InThreading(prchild)。 第一節(jié) 樹的存儲結(jié)構(gòu) R A D E F C B G K H 0 1 2 3 4 5 6 7 8 9 數(shù)組下標 : * 便于涉及孩子的操作；求雙親不方便； * 采用同構(gòu)的結(jié)點，空間浪費。 //結(jié)點數(shù) }PTree。 typedef struct { TElemType data。 }CSNode, *CSTree。 R A D E B C F G H K 二、后根遍歷： （ 1）依次后根遍歷每棵子樹。 ? (3) 在 F中刪除這兩棵樹 ,同時將新得到的二叉樹加入 F中 。若現(xiàn)在電文為：ABACCDA，則應發(fā)送二進制序列： 00010010101100，總長度為 14位。稱為赫夫曼編碼。HC /*HF編碼表 */, int *w /*各字符的權(quán)值 數(shù)組 */,){ if(n=1) return。 HT[s2].parent=i； //填寫雙親結(jié)點編號 HTIi].1child=s1； HT[j].rchild=s2； HT[i].weight=T[s1].weight+T[s2].weight； } // end for //從葉子到根逆向求每個字符的赫夫曼編碼 HC=(Huffmancode)malloc((n+1)*sizeof(char *))。 HC[i]=(char * )malloc((nstart)*sizeof(char))。 層次遍歷 是按另一種搜索策略進行的遍歷。 7. 了解 最優(yōu)樹的特性 ，掌握 建立最優(yōu)樹和赫夫曼編碼 的方法。實現(xiàn)二叉樹遍歷的具體算法與所采用的存儲結(jié)構(gòu)有關(guān)。c=f,f=HT[f].parent if(HT[f].lchild==c cd[start]=“0”。i=m。 //動態(tài)分配數(shù)組存儲 赫夫曼編碼表 第二節(jié) 赫夫曼編碼 Weight parent lchild rchild 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 5 29 7 8 14 23 3 11 0 1 2 3 4 5 6 7 W 5 29 8 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 14 23 3 11 9991 78 10 10 3 415 11 11 12 819 14 14 12 13 13 15 15 529 42 58 100 210 11 614 12 13 HC 0 cd 0 1 2 3 4 5 6 7 1 2 3 4 5 6 7 8 0 0 1 1 ↑ start 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 求赫夫曼編碼過程的實例 : HT數(shù)組 求哈夫曼編碼的算法 : void HuffmanCoding(HuffmanTree amp。 但隨之帶來了一個問題，接收方接到這段電文后無 法進行譯碼，因為無法斷定前面 4個 0是 4個 A， 1個 B加 2個 A，還是 2個 B，即譯碼不唯一，因此這種編碼方法 不可使用。 第二節(jié) 赫夫曼編碼 等長編碼：每個字符的編碼 長度相同 。 k=1 第一節(jié) 赫夫曼樹及其應用 a b c d 7 5 2 4 WPL=7x3+5x3+2x1+4x2 = 46 例：下面兩棵二叉樹的四個葉子結(jié)點 a,b,c,d的權(quán)值為 4 c d a b 7 5 2 4 (a)WPL=7x2+5x2+2x2+4x2 = 36 (b)WPL=7x1+5x2+2x2+4x2 = 35 第一節(jié) 赫夫曼樹及其應用 a b c d 7 5 2 4 最優(yōu)二叉樹的定義 ? 假設有 n個權(quán)值 {ω 1, ω 2, … , ω n}， 試構(gòu)造一棵有 n個葉子結(jié)點 的二叉樹 ， 每個葉子結(jié)點帶權(quán)為 ω i, 則其中： 帶權(quán)路徑長度 WPL最小的二叉樹稱做最優(yōu)二叉樹 ， 或赫夫曼樹 第一節(jié) 赫夫曼樹及其應用 例下面三棵二叉樹的四個葉子結(jié)點 a,b,c,d的權(quán)值為 4 a b c d 7 5 2 4 a b c d 7 5 2 4 c d a b 7 5 2 4 (a)WPL=7x2+5x2+2x2+4x2 = 36 (b)WPL=7x3+5x3+2x1+4x2 = 46 (c)WPL=7x1+5x2+2x2+4x2 = 35 第一節(jié) 赫夫曼樹及其應用 (a)WPL=10x4+30x4+40x3+15x2+5x1=315 10 中 90 差 及格 5 15 40 良 優(yōu) 30 60 70 80 N N N N Y Y Y Y 10 70 90 差 中 5 40 15 良 優(yōu) 30 60 及格 80 N N N N Y Y Y Y 第一節(jié) 赫夫曼樹及其應用 (b)WPL=5x3+15x3+40x2+30x2+10x2=220 構(gòu)造赫夫曼樹的算法思想 ? (1) 根據(jù)給定的 n個權(quán)值 {w1,w2, … ,wn}構(gòu)成 n棵二叉樹的集合 F={T1,T2, … ,Tn}， 其中每棵二叉樹 Ti中只有一個帶權(quán)為 Wi的根結(jié)點 ,其左右子樹均空 。={T2,T3, … ，Tm}是由 B的右子樹 RB轉(zhuǎn)換而成的森林 。 第一節(jié) 樹的存儲結(jié)構(gòu) 三、孩子兄弟表示法 樹的二叉樹表示法 (二叉鏈表示法 ) ? //樹的二叉鏈表 (孩子兄弟 )存儲表示 typedef struct CSNode { ELemType data。 struct CTNode *next。 typedef struct{ PTNode nodes[MAX_TREE_SIZE]。