【正文】 點(diǎn) 左子樹 右子樹 二叉樹的五種基本形態(tài)： N 空樹 只含根結(jié)點(diǎn) N N N L R R 右子樹為空樹 L 左子樹為空樹 左右子樹均不為空樹 二叉樹的主要基本操作 ： 查 找 類 插 入 類 刪 除 類 Root(T)。 RightChild(T, e)。 BiTreeDepth(T)。 LevelOrderTraverse(T, Visit())。e, value)。 ClearBiTree(amp。 DeleteChild(T, p, LR)。 證明： 基于上一條性質(zhì)，深度為 k 的二叉樹上的結(jié)點(diǎn)數(shù)至多為 20+21+ ? ? ? ? ? ? +2k1 = 2k1 。 完全二叉樹 ： 樹中所含的 n 個(gè)結(jié)點(diǎn)和滿二叉樹中 編號(hào)為 1 至 n 的結(jié)點(diǎn) 一一對(duì)應(yīng)。 二叉樹的存儲(chǔ)結(jié)構(gòu) 二、二叉樹的鏈?zhǔn)? 存儲(chǔ)表示 一、 二叉樹的順序 存儲(chǔ)表示 define MAX_TREE_SIZE 100 // 二叉樹的最大結(jié)點(diǎn)數(shù) typedef TElemType SqBiTree[MAX_ TREE_SIZE]。 // 左右孩子指針 } BiTNode, *BiTree。 //雙親指針 } TriTNode, *TriTree。而二叉樹是非 線性結(jié)構(gòu)， 每個(gè)結(jié)點(diǎn)有兩個(gè)后繼 ， 則 存在如何遍歷 即按什么樣的 搜索 路徑 遍歷的問題。 按層次遍歷該二叉樹的序列為： A B E C F D G H K A B C D E F G H K 三、先左后右的遍歷算法 先 （根）序的遍歷算法 中 （根）序的遍歷算法 后 （根）序的遍歷算法 若二叉樹為空樹，則空操作；否則， （ 1）訪問根結(jié)點(diǎn)； （ 2）先序遍歷左子樹； （ 3）先序遍歷右子樹。 // 遍歷左子樹 Preorder(Trchild, visit)。 // 遍歷左子樹 visit(Tdata)。 e)) { // 后序遍歷二叉樹 if (T) { Postreorder(Tlchild, visit)。 Push(S,T)。 Pop(S,p)。 } } return OK。 p=plchild。 } } return OK。T){ scanf( amp。 Tdata=ch。 } // CreateBiTree 統(tǒng)計(jì)二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù) 算法基本思想 : 先序 (或中序或后序 )遍歷二叉樹，在遍歷過程中查找葉子結(jié)點(diǎn)，并計(jì)數(shù)。amp。 } // if } // CountLeaf 求二叉樹的深度 (后序遍歷 ) 算法基本思想 : 從二叉樹深度的定義可知， 二叉樹的深度應(yīng)為其左、右子樹深度的最大值加 1。 else { depthLeft = Depth( Tlchild )。 } 線索二叉樹 ? 何謂線索二叉樹？ ? 線索鏈表的遍歷算法 ? 如何建立線索鏈表？ 一、何謂線索二叉樹？ 遍歷二叉樹的結(jié)果是， 求得結(jié)點(diǎn)的一個(gè)線性序列。 線索鏈表的結(jié)點(diǎn)結(jié)構(gòu) ltag和 rtag是增加的兩個(gè)標(biāo)志域，用來區(qū)分結(jié)點(diǎn)的左、右指針域是指向其左、右孩子的指針，還是指向其前驅(qū)或后繼的線索。 // 左右標(biāo)志 } BiThrNode, *BiThrTree。 p = Succ(p) ) Visit (p)。 void InOrderTraverse_Thr(BiThrTree T, void (*Visit)(TElemType e)) { p = Tlchild。amp。 // p進(jìn)至其右子樹根 } } // InOrderTraverse_Thr 在中序遍歷過程中修改結(jié)點(diǎn)的 左、右指針域，以保存當(dāng)前訪問結(jié) 點(diǎn)的“前驅(qū)”和“后繼”信息。 plchild = pre。 // 保持 pre 指向 p 的前驅(qū) InThreading(prchild)。 ThrtRTag =Thread。 pre = Thrt。 Thrtrchild = pre。 // 雙親位置域 } PTNode。 樹結(jié)構(gòu) : A B C D E F G 0 A 1 1 B 0 2 C 0 3 D 0 4 E 2 5 F 2 6 G 4 r=0 n=7 data parent firstchild 1 2 3 4 5 6 二、孩子鏈表表示法 : typedef struct CTNode { int child。 ChildPtr firstchild。 // 結(jié)點(diǎn)數(shù)和根結(jié)點(diǎn)的位置 } CTree。 C語言的類型描述 : 結(jié)點(diǎn)結(jié)構(gòu) : firstchild data nextsibling 森林和二叉樹的對(duì)應(yīng)關(guān)系 設(shè) 森林 F = ( T1, T2, …, T n )。 B C D E F G H I J K B E C F D G H I J K 例如 ： 由二叉樹轉(zhuǎn)換為森林 的轉(zhuǎn)換規(guī)則為： 若 B = Φ， 則 F = Φ； 否則， 由 Node(root) 對(duì)應(yīng)得到 ROOT( T1 )； 由 LBT 對(duì)應(yīng)得到 ( t11, t12, … ， t1m)； 由 RBT 對(duì)應(yīng)得到 (T2, T3, …, T n)。 若樹不空，則先依次后根遍歷各棵子樹，然后訪問根結(jié)點(diǎn)。 1. 先序遍歷 森林的遍歷 即： 依次從左至右 對(duì)森林中的每一棵樹 進(jìn)行 先根遍歷 。 結(jié)點(diǎn)的路徑長(zhǎng)度 定義為： 從根結(jié)點(diǎn)到該結(jié)點(diǎn)的路徑上 分支的數(shù)目。 例如： WPL(T)= 7?2+5?2+2?2+4?2 =36 WPL(T)= 7?1+5?2+2?3+4?3 =35 WPL(T)= 7?3+5?3+4?2+2?1 =46 根據(jù)給定的 n 個(gè)權(quán)值 {w1, w2, …, w n}，構(gòu)造 n 棵二叉樹的集合 F = {T1, T2, … , T n}， 其中每棵二叉樹 Ti中均只含一個(gè)帶權(quán)值 為 wi 的根結(jié)點(diǎn)，其左、右子樹為空樹； 二、如何構(gòu)造最優(yōu)樹 (1) (哈夫曼算法 ) 以二叉樹為例： 在 F 中選取其根結(jié)點(diǎn)的權(quán)值為最 小的兩棵二叉樹，分別作為左、 右子樹構(gòu)造一棵新的二叉樹，并 置這棵新的二叉樹根結(jié)點(diǎn)的權(quán)值 為其左、右子樹根結(jié)點(diǎn)的權(quán)值之 和； (2) 從 F中刪去這兩棵樹，同時(shí)加入 剛生成的新樹； 重復(fù) (2) 和 (3) 兩步，直至 F 中只 含一棵樹為止。 前綴編碼 在電文傳輸中，需要將電文中出現(xiàn)的每個(gè)字符進(jìn)行二進(jìn)制編碼。 設(shè)字符集只含有 4個(gè)字符 A， B， C， D， 用兩位二進(jìn)制表示的編碼分別為 00， 01， 10， 11。 2. 不等長(zhǎng)編碼 在傳送電文時(shí)，為了使其二進(jìn)制位數(shù)盡 可能地少，可以將每個(gè)字符的編碼設(shè)計(jì)為不等長(zhǎng) 的，使用頻度較 高 的字符分配一個(gè)相對(duì)比較 短 的 編碼，使用頻度較 低 的字符分配一個(gè)比較 長(zhǎng) 的編 碼。 哈夫曼編碼的構(gòu)造方法 ： 例如 ： 假設(shè)有一個(gè)電文字符集中有 8個(gè)字符，每個(gè)字符 的使用頻率分別為 {, ,}， 現(xiàn)以此為例設(shè)計(jì)哈夫曼編碼。 m=2*n1。++i,++p,++w) *p={*w,0,0,0} for(。HT, HuffmanCode amp。i=n。 else cd[start]=“1”。 }//Huffmancoding 1. 熟練掌握 二叉樹的結(jié)構(gòu)特性 ，了解相應(yīng)的證明方法。掌握各種遍歷策略的 遞歸算法 ， 靈活運(yùn)用遍歷算法 實(shí)現(xiàn)二叉樹的其它操作。 5. 熟悉 樹的 各種 存儲(chǔ)結(jié)構(gòu) 及其特點(diǎn)，掌握 樹和森林與二叉樹的轉(zhuǎn)換 方法。