【正文】 isit)。下面我們將給出一棵二叉樹及其按層次順序訪問其中每個結(jié)點(diǎn)的遍歷序列。 // 左右孩子指針 struct TriTNode *parent。 ?性質(zhì) 5 ： 若對含 n 個結(jié)點(diǎn)的完全二叉樹從上到下且從左至右進(jìn)行 1 至 n 的編號，則對完全二叉樹中任意一個編號為 i 的結(jié)點(diǎn)： (1) 若 i=1，則該結(jié)點(diǎn)是二叉樹的根，無雙親， 否則，編號為 ?i/2? 的結(jié)點(diǎn)為其 雙親 結(jié)點(diǎn)； (2) 若 2in，則該結(jié)點(diǎn)無左孩子， 否則，編號為 2i 的結(jié)點(diǎn)為其 左孩子 結(jié)點(diǎn)； (3) 若 2i+1n，則該結(jié)點(diǎn)無右孩子結(jié)點(diǎn)， 否則，編號為 2i+1 的結(jié)點(diǎn)為其 右孩子 結(jié)點(diǎn) 。 ?性質(zhì) 2 ： 深度為 k 的二叉樹上至多含 2k1 個結(jié)點(diǎn)（ k≥ 1）。 InsertChild(T, p, LR, c)。 PostOrderTraverse(T, Visit())。 LeftChild(T, e)。T, amp。 否則 : (1) 在 D中存在唯一的稱為根的數(shù)據(jù)元素 root； (2) 當(dāng) n1時(shí)，其余結(jié)點(diǎn)可分為 m (m0)個互 不相交的有限集 T1, T2, … , Tm，其中每一 棵子集本身又是一棵符合本定義的樹， 稱為根 root的子樹。T, definition) // 按定義構(gòu)造樹 Assign(T, cur_e, value) // 給當(dāng)前結(jié)點(diǎn)賦值 InsertChild(amp。 無序樹： 子樹之間不存在確定的次序關(guān)系。 RightSibling(T, e)。T)。 DestroyBiTree(amp。 證明： 設(shè) 二叉樹上結(jié)點(diǎn)總數(shù) n = n0 + n1 + n2 又 二叉樹上分支總數(shù) b = n1+2n2 而 b = n1 = n0 + n1 + n2 1 由此， n0 = n2 + 1 。 一、 二叉樹的順序存儲表示 例如 : A B C D E F A B D C E F 0 1 2 3 4 5 6 7 8 9 10 11 12 13 1 4 0 13 2 6 二、二叉樹的鏈?zhǔn)酱鎯Ρ硎? 1. 二叉鏈表 2． 三叉鏈表 A D E B C F ? ? ? ? ? ? ? root lchild data rchild 結(jié)點(diǎn)結(jié)構(gòu) : 1. 二叉鏈表 typedef struct BiTNode { // 結(jié)點(diǎn)結(jié)構(gòu) TElemType data。 一、問題的提出 “訪問 ”的含義可以很廣，如：輸出結(jié) 點(diǎn)的信息等。 e)) { // 先序遍歷二叉樹 if (T) { visit(Tdata)。// 遍歷右子樹 } } A B C D E F G L D R T L D R L D R A B E L D R L D R LDR LDR C F D G 中序遍歷結(jié)果 : B D C A G F E T 若二叉樹為空樹，則空操作；否則， （ 1）后序遍歷左子樹； （ 2）后序遍歷右子樹； （ 3）訪問根結(jié)點(diǎn)。amp。 p=T。將算法中“ 訪問結(jié)點(diǎn) ”的操作改為： 生成一個結(jié)點(diǎn)，輸入結(jié)點(diǎn)的值 。 //構(gòu)造左子樹 CreateBiTree( Trchild)。 // 對葉子結(jié)點(diǎn)計(jì)數(shù) CountLeaf( Tlchild, count)。 depthval = 1 + (depthLeft depthRight ? depthLeft : depthRight)。 struct BiThrNode *lchild, *rchild。 例如 : 對中序線索化鏈表的遍歷算法 ※ 中序遍歷的第一個結(jié)點(diǎn) ？ ※ 在中序線索化鏈表中結(jié)點(diǎn)的后繼 ？ 左子樹上處于 “最左下” （沒有左子樹）的結(jié)點(diǎn)。 Visit(pdata)。 prerchild = p。 if (!T) Thrtlchild = Thrt。 } // InOrderThreading 樹和森林 的表示方法 樹的三種存儲結(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 5 r=0 n=7 data parent 一、雙親表示法 : typedef struct PTNode { Elem data。 } *ChildPtr。 struct CSNode *firstchild, *nextsibling。 應(yīng)當(dāng)注意的是， 和樹對應(yīng)的二叉樹，其左、右子樹的概念 已改變?yōu)椋? 左是孩子，右是兄弟。 即： 依次從左至右 對森林中的每一棵樹 進(jìn)行 后根遍歷 。最終求得的哈夫曼樹中共有 2n1個結(jié)點(diǎn)。當(dāng)接收方接收到這段電文后， 將按兩位一段進(jìn)行譯碼。 Typedef char **Huffmancode。++i,++p) *p={0,0,0,0} for(i=n+1； i=m； i++){ SelectMin(HT， i1， s1， s2)； HT[s1].parent=i。f!=0。 3. 遍歷二叉樹 是二叉樹各種操作的基礎(chǔ)。 6. 學(xué)會編寫 實(shí)現(xiàn)樹的各種操作 的算法。 4. 理解二叉樹 線索化的實(shí)質(zhì) 是建立結(jié)點(diǎn)與其在相應(yīng)序列中的前驅(qū)或后繼之間的直接聯(lián)系，熟練掌握二叉樹的 線索化過程 以及在中序線索化樹上找給定結(jié)點(diǎn)的前驅(qū)和后繼的方法。 strcpy(Hc[i]， amp。 cd=(char *)malloc(n*sizeof(char *))。 求哈夫曼編碼的算法 : for(p=HT+1,i=1。 利用哈夫曼樹可以構(gòu)造一種不等長的二進(jìn)制編碼，并且構(gòu)造所得的 哈夫曼編碼 是一種 最優(yōu)前綴編碼 ，即使所傳 電文的總長度最短 。下面我們介紹兩種編碼的方式。 樹的帶權(quán)路徑長度 定義為： 樹中所有葉子 結(jié)點(diǎn)的帶權(quán)路徑長度 之和 WPL(T) = ?wklk (對所有葉子結(jié)點(diǎn) )。 一、樹的遍歷 先根遍歷時(shí)頂點(diǎn)的訪問次序： A B C E F G D 后根遍歷時(shí)頂點(diǎn)的訪問次序： B E G F C D A 層次遍歷時(shí)頂點(diǎn)的訪問次序： A B C D E F G A B C D E F G B C D E F G H I J K 1．森林中第一棵樹的根結(jié)點(diǎn)； 2．森林中第一棵樹的子樹森林； 3．森林中其它樹構(gòu)成的森林。 二叉樹 B =( LBT, Node(root), RBT )。 雙親結(jié)點(diǎn)結(jié)構(gòu) data firstchild typedef struct { CTBox nodes[MAX_TREE_SIZE]。 int r, n。 prerchild = Thrt。Thrt, BiThrTree T) { // 構(gòu)建中序線索鏈表 if (!(Thrt = (BiThrTree)malloc(sizeof( BiThrNode)))) exit (OVERFLOW)。 三、如何建立線索鏈表？ void InThreading(BiThrTree p) { if (p) { // 對以 p為根的非空二叉樹進(jìn)行線索化 InThreading(plchild)。 // 第 一個結(jié)點(diǎn) Visit(pdata)。 // Link==0:指針， Thread==1:線索 ABCDEFGHI 例如： 二、線索鏈表的遍歷算法 : for ( p = firstNode(T)。 若該結(jié)點(diǎn)的右子樹不空， 則 rchild域的指針指向其右子樹， 且右標(biāo)志域的值為 “ 指針 Link