[電腦基礎(chǔ)知識(shí)]第7章 樹(shù)-全文預(yù)覽
【正文】 文件總碼長(zhǎng)達(dá)到最小的前綴編碼的方法（構(gòu)造一棵赫夫曼樹(shù)）： （ 1）用頻率作為葉子結(jié)點(diǎn)的權(quán)值生成一棵赫夫曼樹(shù)，并將對(duì)應(yīng)權(quán)值 wi的葉子結(jié)點(diǎn)注明對(duì)應(yīng)的字符； （ 2）約定左分支表示字符 “ 0”，右分支表示字符 ‘ 1’ （ 3）從葉子結(jié)點(diǎn)開(kāi)始，順著雙親反推上去，直到根結(jié)點(diǎn)，路徑上的 ‘ 0’或 ‘ 1’連接的序列就是結(jié)點(diǎn)對(duì)應(yīng)的字符的二進(jìn)制編碼的逆序。 6 7 5 c d (b) 11 b 5 7 c d (c) 7 18 a 11 c d b 5 6 2 4 (d) a b c d 7 5 2 4 (a) 例：給定權(quán)值 {7， 5， 2， 4}，構(gòu)造哈夫曼樹(shù)。 （ 2）在森林 F中選取兩棵根結(jié)點(diǎn)權(quán)值 最小的和次小的二叉樹(shù) (當(dāng)這樣的樹(shù)不止兩棵樹(shù)時(shí)，可以從中任選兩棵 )作為左右子樹(shù)構(gòu)造一棵新的二叉樹(shù)，其根結(jié)點(diǎn)的權(quán)值為左右子樹(shù)根結(jié)點(diǎn)權(quán)值之和。 ? 樹(shù)的帶權(quán)路徑長(zhǎng)度 （ weighted path length of tree）：樹(shù)中所有 葉子結(jié)點(diǎn) 的帶權(quán)路徑長(zhǎng)度之和。 如何進(jìn)行二叉樹(shù)的線索化呢？ 線索化的實(shí)質(zhì)是將二叉鏈表中的空指針改為指向結(jié)點(diǎn)前驅(qū)或后繼的線索，而一個(gè)結(jié)點(diǎn)的前驅(qū)和后繼的信息只有在遍歷時(shí)才能得到，因此線索化過(guò)程即為 在遍歷的過(guò)程中修改空指針的過(guò)程。 2）非終端結(jié)點(diǎn)若無(wú)右孩子，則其右鏈?zhǔn)蔷€索，指向后繼，若有右孩子，則其后繼是中序遍歷其右子樹(shù)時(shí)訪問(wèn)的第一個(gè)結(jié)點(diǎn)，即 右子樹(shù)中最左下結(jié)點(diǎn) 。 int leftThread,rightThread。這樣，線索二叉樹(shù)結(jié)點(diǎn)類(lèi)型定義為： typedef struct btnode *tbtlink。 后序遍歷二叉樹(shù) 的操作定義為： 若二叉樹(shù)為空，則空操作；否則 （ 1）后序遍歷左子樹(shù)； （ 2）后序遍歷右子樹(shù)； （ 3）訪問(wèn)根結(jié)點(diǎn)。 if(hlhr) return ++hl。 } } 返回二叉樹(shù)的高度 int Height(btlink t) { int hl,hr。 InOrder(visit,tright)。 PreOrder(visit,tleft)。 Rroot=Trootright。 } 將二叉樹(shù)拆分 TreeItem BreakTree(BinaryTree T,BinaryTree L,BinaryTree R) { TreeItem x。 Trootelement=x。 return T。 if((p=malloc(sizeof(Btnode)))==0) Error(“Exhausted memory.”)。 G B C A D E F I J H ? 用指針實(shí)現(xiàn)的抽象數(shù)據(jù)類(lèi)型二叉樹(shù)結(jié)構(gòu)定義為： typedef struct binarytree *BinaryTree。 btlink right。 （ 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（二叉鏈表結(jié)構(gòu)）） ? 每個(gè)結(jié)點(diǎn)由數(shù)據(jù)域、左指針域和右指針域組成。因此，對(duì) 完全 二叉樹(shù)而言，順序存儲(chǔ)結(jié)構(gòu)既簡(jiǎn)單又節(jié)省存儲(chǔ)空間。 （ 3）當(dāng) i為奇數(shù)且不為 1時(shí)，結(jié)點(diǎn) i的左兄弟結(jié)點(diǎn)為 i1,當(dāng) i為偶數(shù)時(shí)，結(jié)點(diǎn) i的右兄弟結(jié)點(diǎn)為 i+1。 ? 具體實(shí)現(xiàn)如下： 將一棵具有 n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，從樹(shù)根起，自上層到下層，逐層從左到右給所有結(jié)點(diǎn)編號(hào)，其中每個(gè)結(jié)點(diǎn)的編號(hào)作為結(jié)點(diǎn)的名稱(chēng)。 1 2 3 4 5 6 (a)完全二叉樹(shù) ? 對(duì)一棵完全二叉樹(shù)，有： 于 2； ； ，反之不然，在完全二叉樹(shù)中，若某個(gè)結(jié)點(diǎn)沒(méi)有左孩子，則它一定沒(méi)有右孩子，即該結(jié)點(diǎn)必是葉結(jié)點(diǎn)。 4 2 3 1 6 7 8 9 10 11 12 13 14 15 5 特點(diǎn)： 1的結(jié)點(diǎn)，每個(gè)分支結(jié)點(diǎn)均有兩棵高度相同的子樹(shù)，且葉子都在最下一層。 ? 性質(zhì) 5：在二叉樹(shù)的第 i層上至多有 2i個(gè)結(jié)點(diǎn) (i=0)。 樹(shù) 二叉樹(shù) 二叉樹(shù)的性質(zhì) ① 高度為 h=0的二叉樹(shù)至少有 h+1個(gè)結(jié)點(diǎn)。 ，分別稱(chēng)之為左子樹(shù)和右子樹(shù) ,其次序不能任意顛倒。 在計(jì)算機(jī)內(nèi)， 使用后綴表達(dá)式易于求值。該表達(dá)式用二叉樹(shù)表示如圖 。 – 中序遍歷： B、 F、 D、 G、 A、 C、 E、 H 。 ② 對(duì) T進(jìn)行中序遍歷是先中序遍歷 T1，然后訪問(wèn)樹(shù)根 n,接著依次對(duì) T2,…… ,TK進(jìn)行中序遍歷。當(dāng)我們刪去的是一棵有序樹(shù)的樹(shù)根時(shí)，留下的子樹(shù)也是有序的，這些樹(shù)組成一個(gè)樹(shù)表。 – 有序樹(shù)：在樹(shù) T中， 如果將樹(shù)中結(jié)點(diǎn)的各子樹(shù)看成從左至右是有次序的，則稱(chēng)該樹(shù)為 有序樹(shù) ，否則稱(chēng)為 無(wú)序樹(shù) 。 – 真祖先、真子孫： 樹(shù)中一個(gè)結(jié)點(diǎn)的非自身祖先和子孫分別稱(chēng)為該結(jié)點(diǎn)的真祖先和真子孫。在圖 ，結(jié)點(diǎn) F的祖先是 A、 B、 F。樹(shù)的高度是指根結(jié)點(diǎn)的高度。 – 葉結(jié)點(diǎn)：度為 0的結(jié)點(diǎn)，即無(wú)后繼的結(jié)點(diǎn)，也稱(chēng)為終端結(jié)點(diǎn)。 ? 定義：樹(shù) (Tree)是 n(n=0)個(gè)結(jié)點(diǎn)的有限集 T，T為空時(shí)稱(chēng)為空樹(shù)，否則它滿(mǎn)足如下兩個(gè)條件： （ 1）有且僅有一個(gè)特定的稱(chēng)為根 (Root)的結(jié)點(diǎn)； （ 2）其余的結(jié)點(diǎn)可分為 m(m=0)個(gè)互不相交的子集 T1,T2,T3… Tm，其中每個(gè)子集又是一棵樹(shù)，并稱(chēng)其為子樹(shù) (Subtree)。樹(shù)結(jié)構(gòu)在客觀世界國(guó)是大量存在
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1