【正文】 Ar。因而要設置標記向量 visited[1..n] 種類：一種是深度優(yōu)先搜索遍歷 ， 另一種是廣度優(yōu)先搜索遍歷 。 VexNode adjlist[max]。 ArcNode *firstarc。 }。 //n為圖中允許的最大頂點數(shù) struct ArcNode //弧結(jié)點類型定義 {int adjvex。 邊上帶有權的圖稱作帶權圖 ， 也常稱作網(wǎng) 。 4 1 5 3 2 4 1 3 2 104 圖有關的基本術語 權和網(wǎng) 在一個圖中 ， 每條邊可以標上具有某種含義的數(shù)值 ， 此數(shù)值稱為該邊的權 (weight)。是 G的子圖 。是 V的子集 ， 且 E39。, E39。 特別地當 v1＝ vm時 ， 則稱次路徑為回路或環(huán) 103 圖有關的基本術語 子圖 設有兩個圖 G = (V, E)和 G39。 有向圖中頂點的度有入度和出度之分：入度是該頂點的入邊的數(shù)目；出度是該頂點的出邊的數(shù)目 ，頂點 v的度等于它的入度和出度之和 。 101 圖有關的基本術語 頂點的度 、 入度 、 出度 無向圖中頂點 v的度 (degree)定義為以該頂點為一個端點的邊的數(shù)目 ， 簡單地說 ， 就是該頂點的邊的數(shù)目 ， 記為 d(v)。 圖：多對多 ， 頂點間的關系是任意的 。 E(G1) = {(1,2), (1,3), (2,3), (2,4), (2,5), (3,5), (4,5)}。 } weight=4 code=101 weight=2 code=1001 weight=6 code=01 weight=8 code=11 weight=3 code=001 weight=2 code=100 weight=1 code=1000 96 后記 ? 結(jié)束 97 版權所有 , 1997 (c) Dale Carnegie amp。 coutendl。jn。i++) {coutweight= hc[i].weight code=。 for(i=0。 HaffCode *hc = new HaffCode [n]。 int n=7,i,j。 95 哈夫曼編碼生成程序：執(zhí)行實例 設有字符集 {A、 B、 C、 D、 E、 F、 G}， 各字符對應的權值分別為 4,2,6,8,3,2,1，設計各字符的哈夫曼編碼 。 hc[i].weight=。j++) hc[i].bit[j]=[j]。 for(j=+1。 parent=ht[child].parent。 。 while (parent!=0) {if( ht[parent].lchild==child) []=0。 child=i。i++) //由哈夫曼樹生成哈夫曼編碼 { =n1。 for(i=0。 94 樹的應用：哈夫曼編碼生成程序 //步驟 2 由哈夫曼樹生成哈夫曼編碼 HaffCode cd。 ht[n+i].rchild=x2。 ht[n+i].weight=ht[x1].weight+ht[x2].weight。 } } ht[x1].parent=n+i。 ht[j].parent==0) { m2=ht[j].weight。 } else if( ht[j].weightm2 amp。 m1=ht[j].weight。 ht[j].parent==0) { m2=m1。j++) { if( ht[j].weightm1 amp。 for(j=0。i++) //構造哈夫曼樹的 n1個分支結(jié)點 {m1=m2=1000。 93 樹的應用：哈夫曼編碼生成程序 for(i=0。j++)表示從根結(jié)點到當前已生成的分支結(jié)點中找出兩個權值最小的結(jié)點 。 在構造某一個分支結(jié)點時使用了一個循環(huán) for(j=0。 ht[i].rchild=1。 ht[i].parent=0。i++) //哈夫曼樹初始化 {if(in)ht[i].weight=w[i]。 //m m2分別表示最小 、 次小的權值 //x x2分別表示當前分支結(jié)點的左右兒子 //步驟 1 構造哈夫曼樹 for(i=0。 }。 int start。 }。 int lchild。 struct HaffNode {int weight。 對每個葉結(jié)點都進行如下的處理： 掃描由葉結(jié)點到根結(jié)點的各條分支 ， 若分支中的當前結(jié)點與雙親結(jié)點是左支關系 ， 則生成編碼 0， 若分支中的當前結(jié)點與雙親結(jié)點是右支關系 ， 則生成編碼 1， 由此生成的二進制碼的序列即為該結(jié)點的哈夫曼編碼 。 ???niii lwW P L184 樹的應用：哈 夫 曼 樹 (a) WPL = 9 2＋ 6 2＋ 5 2＋ 3 2＝ 46 (b) WPL = 6 1＋ 3 2＋ 9 3＋ 5 3＝ 54 (c) WPL = 9 1＋ 6 2＋ 5 3＋ 3 3＝ 45 b 5 3 c 6 d a 9 a 6 5 b 9 c d 3 a 5 6 c 9 b d 3 85 哈夫曼樹的定義 具有 n個帶權葉節(jié)點的二叉樹中 WPL最小的二叉樹稱為哈夫曼樹 意義：用于編碼設計 編碼長度－－路徑長度 使用頻率－－權值 報文總長－－ WPL 報文總長最短－－ WPL最小 86 各類編碼 各類編碼 A B C D 等長編碼 00 01 10 11 報文總長可以縮短 不等長編碼 0 1 00 11 存在多義性 0000 AAAA AAC ACA 前綴編碼 0 10 110 111 一組編碼中任何一個編碼均不為其他編碼的前綴 .避免了多義性，且縮短了報文總長 哈夫曼編碼 通過建立哈夫曼樹得到最優(yōu)的二進制前綴編碼 87 哈夫曼樹的構造 設給定葉結(jié)點的個數(shù) n及權值集合 { w1 , w2 ,… , wn } 為使二叉樹的帶權路徑長度達到最小 ， 權值越大的葉結(jié)點應越靠近根結(jié)點 ， 而權值越小的葉結(jié)點則離根結(jié)點越遠 。 e d a c b Firstchild data Nextsibling a b c d e 81 樹、森林轉(zhuǎn)換成二叉樹 樹轉(zhuǎn)換成二叉樹 轉(zhuǎn)換方法：用兒子兄弟表示法表示一棵樹 ， 并將兒子鏈看作為左子樹 ， 將兄弟鏈看作為右子樹 。 樹 當節(jié)點個數(shù) n0 時由根節(jié)點與 M棵子樹構成的森林所構成 。 return pdata。 if (p==NULL) coutemptyendl。 其處理過程為： 使 p=root， 若 p為空 ， 則顯示相應的信息 ， 否則 (1) 若 p所指結(jié)點有左兒子 ， 則令 p指向該結(jié)點； (2) 重復 (1)， 直至 p所指結(jié)點的左兒子鏈為空； (3) 返回 p所指結(jié)點的關鍵碼 。 //遞歸插入函數(shù) }。 //非遞歸插入函數(shù) static void inst(BTreeNodeT *p, BTreeNodeT *amp。//遞歸查找函數(shù) void inst(T el)。 //查找實例函數(shù) BTreeNodeT *sear1(T el)。 T maxv()。}。 } … c … f … a … b … d … y … z … x 74 排序二叉樹的定義 排序二叉樹或為空樹或為滿足具有以下特點的二叉樹： （ 1） 所有結(jié)點的 （ 數(shù)據(jù) ） 值均不相同； （ 2） 若左子樹為非空 ， 則左子樹中所有結(jié)點的值均小于根結(jié)點的值； （ 3） 若右子樹為非空 ， 則右子樹中所有結(jié)點的值均大于根結(jié)點的值； （ 4） 左子樹和右子樹均是排序二叉樹 。 (p3)。z39。,NULL,NULL)。 BTreeNodechar *p2=new BTreeNodechar(39。x39。 ()。 } void main( ) {char *str2=abcd f。 73 互動環(huán)節(jié)：重置函數(shù)及其測試 template class T void BTreeT::setroot(BTreeNodeT *p) { dest(root)。 } } void prnt(){prnt(root,1)。 cout...pdataendl。i6*(l1)。 遞歸打印函數(shù)的程序代碼如下： 72 互動環(huán)節(jié)：二叉樹顯示 template class T void BTreeT::prnt(BTreeNodeT *p, int l) { if (p!=NULL ) { prnt(prchild,l+1)。 由于把二叉樹逆時針旋轉(zhuǎn) 90度后顯示在上方的右子樹 ， 然后是根節(jié)點 ， 最后是左子樹 ， 所以該算法是一種特殊的中序遍歷算法 。 } 71 互動環(huán)節(jié)：二叉樹顯示 為二叉樹類增設一個打印二叉樹的成員函數(shù) ， 按二叉樹的凹入表示法打印二叉樹 ， 其輸出的形式相當于把二叉樹逆時針旋轉(zhuǎn) 90度 。 stack[top]=prchild 。 if (top=0) { p=stack[top]。 stack[++top]=p。stack[top]=root。 s=。 70 中序遍歷的非遞歸函數(shù) template class T void BTreeT::inorder1(void visit(BTreeNodeT *p)) { BTreeNodeT *stack[10],*p。 (2) 若棧非空 ， 則棧頂結(jié)點的左兒子相繼進棧 ， 直至NULL退棧；訪問棧頂結(jié)點 （ 執(zhí)行 visit函數(shù)的操作 ） 并使棧頂結(jié)點的右兒子成為棧頂結(jié)點 。 inorder(prchild,visit)。 } template class T void BTreeT::inorder(BTreeNodeT *p, void visit(BTreeNodeT *p)) { if (p!=NULL ) { inorder(plchild,visit)。 void BTreeT::inorder(void visit(BTreeNodeT *p)) 66 中序遍歷的遞歸函數(shù)與實例函數(shù) template class T void BTreeT::inorder(void visit(BTreeNodeT *p)) { inorder(root,visit)。 (3) 中序遍歷 p所指結(jié)點的右子樹 。 64 二叉樹的遍歷 先序：根節(jié)點 、 左子樹 、 右子樹 A B D H I C F G 中序：左子樹 、 根節(jié)點 、 右子樹 H D I B A F C G 后序：左子樹 、 右子樹 、 根節(jié)點 H I D B F G C A D H I A B C F G 65 中序遍歷的遞歸函數(shù)與實例函數(shù) void inorder(BTreeNodeT *p, void visit(BTreeNodeT *p)) 其功能為對 p所指的二叉樹進行中序遍歷 ， 對每個結(jié)點執(zhí)行visit函數(shù)的操作 ， 其處理過程為： 若 p非空 ， 則 (1)中序遍歷 p所指結(jié)點的左子樹 。 63 二叉樹的遍歷 二叉樹的遍歷是指按照一定次序訪問樹中所有結(jié)點 ， 并且每個結(jié)點僅被訪問一次的過程 。 } } 要注意的是參數(shù) p是結(jié)點指針類型 ， 其值會有所改變 ， 因此必修加上引用符號‘ amp。 copybt(plchild,qlchild)。 else {p=new BTreeNodeT。 template class T void BTreeT::copybt(BTreeNodeT *amp。 否則 ， (2)創(chuàng)建一個新的結(jié)點 ， 復制結(jié)點 q中的數(shù)據(jù) 。p,BTreeNodeT *q) 其功能為復制 q所指向的二叉樹 ， 并由 p指向新復制的二叉樹 。 delete p。