【正文】 先（根）序的遍歷算法： 四、算法的遞歸描述 void Preorder (BiTree T, void( *visit)(TElemTypeamp。 // 訪問結(jié)點 Inreorder(Trchild, visit)。 while(!StackEmpty(S)) { while(GetTop(S,p) amp。 } Status InorderTraverse(Bitree T, Status(*Visit)(TElemType e)) { InitStack(S)。 } 算法二： 六 、 遍歷算法的應(yīng)用舉例 統(tǒng)計二叉樹中葉子結(jié)點的個數(shù) (先序遍歷 ) 求二叉樹的深度 (后序遍歷 ) 輸入結(jié)點值，構(gòu)造二叉樹 (先序遍歷 ） 輸入結(jié)點值，構(gòu)造二叉樹 算法基本思想 : 先序 (或中序或后序 )遍歷二叉樹， 讀入一個字符，若讀入字符為空，則二叉樹為空 ,若讀入字符非空，則生成一個結(jié)點。 //生成根結(jié)點 CreateBiTree( Tlchild)。 (!Trchild)) count++。 depthRight= Depth( Trchild )。 lchild LTag data RTag rchild ??????0 l c h i l dL T ag =1 l c h i l d0 r c h i l dRT ag =1 r c h i l d域指向結(jié)點的左孩子域指向結(jié)點的前驅(qū)域指向結(jié)點的右孩子域指向結(jié)點的后繼typedef struct BiThrNod { TElemType data。 由于在線索鏈表中添加了遍歷中得到的“前驅(qū)”和“后繼”的信息，從而簡化了遍歷的算法。 prchild!=T) { p = prchild。 } if (!prerchild) // 建后繼線索 { preRTag = Thread。 Thrtrchild = Thrt。 } return OK。 struct CTNode *next。 樹結(jié)構(gòu) : 三、樹的二叉鏈表 (孩子 兄弟）存儲表示法 A B C D E F G A B C E D F G root A B C E D F G typedef struct CSNode{ Elem data。 例如 ： B E C F D G H I J K B C D E F G H I J K 由此，樹的各種操作均可對應(yīng)二叉樹的操作來完成。 ２．中序遍歷 若森林不空，則 中序遍歷 森林中第一棵樹的子樹森林； 訪問 森林中第一棵樹的根結(jié)點； 中序遍歷 森林中 (除第一棵樹之外 )其 余樹構(gòu)成的森林。這棵樹便是哈夫 曼樹 (3) (4)9 例如 : 已知權(quán)值 W={ 5, 6, 2, 9, 7 } 5 6 2 7 5 2 7 6 9 7 6 7 13 9 5 2 7 6 7 13 9 5 2 7 9 5 2 7 16 6 7 13 29 注意： ? ① 初始森林中的 n棵二叉樹，每棵樹有一個孤立的結(jié)點，它們既是根，又是葉子 ② n個葉子的哈夫曼樹要經(jīng)過 n1次合并，產(chǎn)生 n1個新結(jié)點。若現(xiàn)在電文為： ABACCDA， 則應(yīng)發(fā)送二進(jìn)制序列： 00010010101100， 總長度為 14位。 為方便計算，將所有字符的頻度乘以 100，使 其轉(zhuǎn)換成整型數(shù)值集合，得到 {5,29,7,8,14,23, 3,11}； 哈夫曼編碼設(shè)計如下圖： 11 5 29 7 8 14 23 3 100 0 1 15 58 29 0 0 0 1 1 1 8 42 19 0 0 0 1 1 1 00 010 0110 0111 1110 1111 110 10 哈夫曼樹的存儲結(jié)構(gòu) 用一個大小為 2n1的向量來存儲哈夫曼樹中 的結(jié)點，其存儲結(jié)構(gòu)為： typedef struct { //結(jié)點類型 int weight； //權(quán)值，不妨設(shè)權(quán)值均大于零 int lchild， rchild， parent； //左右孩子及雙親指針 }HTNode， *HuffmanTree。i=m。i++){ start=n1； for(c=i,f=HT[i].parent。 2. 熟悉二叉樹的各種 存儲結(jié)構(gòu) 的特點及適用范圍。建立存儲結(jié)構(gòu)是進(jìn)行其它操作的前提，因此讀者應(yīng) 掌握 1 至 2 種 建立 二叉樹和樹的 存儲結(jié)構(gòu)的方法 。二叉樹的 線索化過程 是 基于 對二叉樹進(jìn)行 遍歷 ，而線索二叉樹上的 線索又為相應(yīng)的遍歷提供了 方便 。cd[start])； } free(cd)。 cd[n1]=“\0”； for(i=1。i=n。稱為哈夫曼編碼 哈夫曼編碼 （ 1）利用字符集中每個字符的使用 頻率作為權(quán)值構(gòu)造一個哈夫曼樹； （ 2）從根結(jié)點開始，為到每個葉子 結(jié)點路徑上的左分支賦予 0，右分支 賦予 1，并從根到葉子方向形成該葉子 結(jié)點的編碼。 1. 等長編碼 這種編碼方式的特點 : 每個字符的編碼 長度相同 。 在所有含 n 個葉子結(jié)點、并帶相同權(quán) 值的 m 叉樹中，必存在一棵其 帶權(quán)路徑 長度取最小值 的樹，稱為“ 最優(yōu)樹 ”。 森林由三部分構(gòu)成： 二、森林的遍歷 若森林不空，則 訪問 森林中第一棵樹的根結(jié)點； 先序遍歷 森林中第一棵樹的子樹森林； 先序遍歷 森林中 (除第一棵樹之外 )其 余樹構(gòu)成的森林。 由森林轉(zhuǎn)換成二叉樹 的 轉(zhuǎn)換規(guī)則為 : 若 F = Φ，則 B = Φ； 否則， 由 ROOT( T1 ) 對應(yīng)得到 Node(root)； 由 (t11, t12, …, t 1m ) 對應(yīng)得到 LBT； 由 (T2, T3,…, T n ) 對應(yīng)得到 RBT。 int n, r。 // 根結(jié)點的位置和結(jié)點個數(shù) } PTree。 preRTag = Thread。 ThrtLTag = Link。 // 左子樹線索化 if (!plchild) // 建前驅(qū)線索 { pLTag = Thread。 while (pRTag==Thread amp。 p。 如此定義的二叉樹的存儲結(jié)構(gòu)稱作“ 線索鏈表 ”。 int Depth (BiTree T ){ // 返回二叉樹的深度 if ( !T ) depthval = 0。 count){ if ( T ) { if ((!Tlchild)amp。 else{ if(!(T=(BiTNode *)malloc(sizeof(BiTNode))) exit(OVERFLOW)。 p=prchild。 Push(S,prchild)。 // 訪問結(jié)點 } } A B C D E F G H K 例如 : 先序 序列 : A B C D E F G H K 中序 序列 : B D C A H G K F E 后序 序列 : D C B H K G F E A 五、中序遍歷算法的非遞歸描述 中序遍歷示意圖 算法一： Status InorderTraverse(Bitree T, Status(*Visit)(TElemType e)) { InitStack(S)。 e)) { // 中序遍歷二叉樹 if (T) { Inreorder(Tlchild, v