【正文】 data。 ChildPtr firstchild。 （ 2）訪問樹的根結(jié)點； D E A B G H K F C R R A D E F C B G K H 第三節(jié) 樹和森林的遍歷 森林的兩種遍歷方法： 一 、 先序遍歷森林： 若森林非空 ， 則 （ 1） 訪問森林中第一棵樹的根結(jié)點； （ 2） 先序遍歷第一棵樹的根結(jié)點的子樹森林； （ 3） 先序遍歷除去第一棵樹之后的森林 。當(dāng)接收方接收到這段電文后，將按兩位一段進行譯碼。 m=2*n1 /*HF樹所需空間總數(shù) */ 。 strcpy(Hc[i]， amp。 6. 學(xué)會編寫 實現(xiàn)樹的各種操作 的算法。f!=0。 。下面我們介紹兩種編碼的方式。 ? F中除 T1之外其余樹組成的森林 F39。 第一節(jié) 樹的存儲結(jié)構(gòu) 孩子鏈表存儲表示（鏈?zhǔn)酱鎯Γ? typedef struct CTNode{ //孩子結(jié)點 int child。 typedef struct{ PTNode nodes[MAX_TREE_SIZE]。 InThreading(T)。 ? 如何在中序線索二叉樹中找結(jié)點的前驅(qū)： – ltag = 1時 ， lchild所指的結(jié)點即為前驅(qū)； – ltag = 0時 ， 其前驅(qū)為遍歷其左子樹時的最后一個結(jié)點 （ 最右下結(jié)點 ） 。 return ERROR。 // 左右孩子指針 } BiTNode, *BiTree。 DeleteChild(amp。 操作結(jié)果： 層序遍歷 T，對每個結(jié)點調(diào)用函數(shù) visit 一次且僅一次。 操作結(jié)果：返回 e 的 右兄弟 。 初始條件：二叉樹 T 存在， e 是 T 中某個結(jié)點。T)。它與樹形結(jié)構(gòu)的區(qū)別是： ? （ 1）每個結(jié)點最多有兩棵子樹； ? （ 2）子樹有左右之分。 操作結(jié)果：結(jié)點 cur_e 賦值為 value。 操作結(jié)果：返回 cur_e 的值。 操作結(jié)果：按 definition 構(gòu)造樹 T。 結(jié)點的層次（ level）： 根為第一層，依次類推。樹 T1， T2， … ， Tm稱為這個根結(jié)點的子樹。 數(shù)據(jù)關(guān)系 ： 若 D 為空集，則稱為 空樹 ； 若 D 中僅含一個數(shù)據(jù)元素，則關(guān)系 R為空集； 否則 R={H}， (1) 在 D中存在唯一的稱為 根 的數(shù)據(jù)元素 root，它在關(guān)系 H下無前驅(qū)； (2) 當(dāng) n1時，其余數(shù)據(jù)元素可分為 m(m0) 個互不相交的 (非空 )有限集 T1,T2,…,Tm, 其中每一個子集本身又是一棵符合本定義的樹，稱為根 root 的 子樹 ，每一棵子樹的根 xi 都是根 root 的后繼，即 root,xi H,i=1,2,…,m 。 初始條件：樹 T存在。 操作結(jié)果：若 cur_e 有右兄弟，則返回它的 右兄弟 ，否則返回 空 。 操作結(jié)果： 插入 c 為 T 中 p 所指結(jié)點的第 i 棵子樹。T)。 Root(T)。若 e 無右孩子，則返回 空 。一旦 visit() 失敗，則操作失敗。 初始條件：二叉樹 T 存在， e 是 T 中某個結(jié)點。 （ 2） 在滿二叉樹的最下一層上，從最右邊開始連續(xù)刪去若干結(jié)點后得到的二叉樹仍然是一棵完全二叉樹。 }else return OK。 CreateBiTree(Tlchild)。 if (!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode)))) exit (OVERFLOW)。 prerchild=p。 typedef struct{ PTNode nodes[MAX_TREE_SIZE]。 第一節(jié) 樹的存儲結(jié)構(gòu) 三、孩子兄弟表示法 樹的二叉樹表示法 (二叉鏈表示法 ) ? //樹的二叉鏈表 (孩子兄弟 )存儲表示 typedef struct CSNode { ELemType data。 k=1 第一節(jié) 赫夫曼樹及其應(yīng)用 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é) 赫夫曼樹及其應(yīng)用 a b c d 7 5 2 4 最優(yōu)二叉樹的定義 ? 假設(shè)有 n個權(quán)值 {ω 1, ω 2, … , ω n}， 試構(gòu)造一棵有 n個葉子結(jié)點 的二叉樹 ， 每個葉子結(jié)點帶權(quán)為 ω i, 則其中： 帶權(quán)路徑長度 WPL最小的二叉樹稱做最優(yōu)二叉樹 ， 或赫夫曼樹 第一節(jié) 赫夫曼樹及其應(yīng)用 例下面三棵二叉樹的四個葉子結(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é) 赫夫曼樹及其應(yīng)用 (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é) 赫夫曼樹及其應(yīng)用 (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é)點 ,其左右子樹均空 。 但隨之帶來了一個問題，接收方接到這段電文后無 法進行譯碼，因為無法斷定前面 4個 0是 4個 A， 1個 B加 2個 A，還是 2個 B，即譯碼不唯一，因此這種編碼方法 不可使用。i=m。實現(xiàn)二叉樹遍歷的具體算法與所采用的存儲結(jié)構(gòu)有關(guān)。 層次遍歷 是按另一種搜索策略進行的遍歷。 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 *))。稱為赫夫曼編碼。 ? (3) 在 F中刪除這兩棵樹 ,同時將新得到的二叉樹加入 F中 。 }CSNode, *CSTree。 //結(jié)點數(shù) }PTree。 //保持 pre指向 p的前驅(qū) InThreading(prchild)。 ThrtRTag=Thread。 } return OK。 中（根）序的遍歷算法： 第一節(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。 第二節(jié) 二叉樹的性質(zhì) ? 性質(zhì) 4 ： 具有 n 個結(jié)點的完全二叉樹的深度為 ? log2 n? +1 第二節(jié) 二叉樹的性質(zhì) 假設(shè) n=4, ? log2 n ? +1= ? log2 4 ? +1=3 1 2 3 4 假設(shè) 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é)點 。 第一節(jié) 二叉樹的定義 ? InsertChild(amp。 初始條件：二叉樹 T存在， visit 是對結(jié)點操作的應(yīng)用函數(shù)。 初始條件：二叉樹 T 存在， e 是 T 中某個結(jié)點。 操作結(jié)果：返回 T 的根。 CreateBiTree(amp。T, amp。 初始條件：樹 T存在， visit 是對結(jié)點操作的應(yīng)用函數(shù)。 Root(T)。T)。 2) 嵌套集合表示法 (b) 3) 凹入表示法 (c) 4) 廣義表表示法 (d) （ a） （ b） （ d） （ c） 第一節(jié) 樹的定義 對比 樹型結(jié)構(gòu) 和 線性結(jié)構(gòu)的結(jié)構(gòu)特點 第一節(jié) 樹的定義 線性結(jié)構(gòu) 樹型結(jié)構(gòu) 第一個數(shù)據(jù)元素 (無前驅(qū) ) 根結(jié)點 (無前驅(qū) )