【正文】 riTree。 // 左、右孩子標(biāo)志域 } BPTNode typedef struct BPTree{ // 樹結(jié)構(gòu) BPTNode nodes[MAX_TREE_SIZE]。如果結(jié)點(diǎn) Parent原來有左孩子結(jié)點(diǎn)，則將結(jié)點(diǎn) Parent原來的左孩子結(jié)點(diǎn)作為結(jié)點(diǎn)x的左孩子結(jié)點(diǎn)。 btLchild=NULL。 if((bt =(BiTree)malloc(sizeof(BiTNode)) ==NULL） return NULL。 return p。 pdata = x。 else { plchild=Parentlchild。 p= Parentlchild。 } 二叉樹的遍歷 一、問題的提出 二、先左后右的遍歷算法 三、算法的遞歸描述 四、中序遍歷算法的非遞歸描述 四 、 遍歷算法的應(yīng)用舉例 順著某一條搜索路徑 巡訪 二叉樹 中的結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn) 均被訪問一 次 ，而且 僅被訪問一次 。 對(duì) “ 二叉樹 ” 而言 ， 可以有三條搜索路徑： ? 1． 先上后下 的按層次遍歷； ? 2． 先左 （ 子樹 ） 后右 （ 子樹 ）的遍歷； ? 3． 先右 （ 子樹 ） 后左 （ 子樹 ）的遍歷 。 后（根）序的遍歷算法： A B C D E F G H K 例如： 先序序列： 中序序列： 后序序列： A B C D E F G H K B D C A E H G K F D C B H K G F E A 三、算法的遞歸描述 void Preorder (BiTree T) { // 先序遍歷二叉樹 if (T) { printf(“%d”,Tdata)。 int top。 //退棧并訪問該結(jié)點(diǎn) printf(“%d”,pdata)。 top++。 } return T。 // 找到最左下的結(jié)點(diǎn) while(t){ visit(tdata)。 四 、 遍歷算法的應(yīng)用舉例 統(tǒng)計(jì)二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù) 求二叉樹的深度 (后序遍歷 ) 建立二叉樹的存儲(chǔ)結(jié)構(gòu) 查詢二叉樹中某個(gè)結(jié)點(diǎn) 1. 在二叉樹不空的前提下 ,和根結(jié)點(diǎn)的元素進(jìn)行比較 ,若相等 ,則找到返回 TRUE。 return OK,} }//if else return FALSE。 int CountLeaf (BiTree T,count){ if( T ) { if ((!Tlchild)amp。 CountLeaf( Trchild, count)。由此， 需先分別求得左、右子樹的深度，算法中 “訪問結(jié)點(diǎn)”的操作為 :求得左、右子樹深度的最大值，然后加 1 。 depthRight= Depth( Trchild )。T) { scanf(amp。) T = NULL。 // 構(gòu)造左子樹 CreateBiTree(Trchild)。 if (ch==39。 Tdata = ch。 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 指向該線性序列中的“前驅(qū)”和 “后繼” 的 指針 ，稱作“ 線索 ” 與其相應(yīng)的二叉樹，稱作 “ 線索二叉樹 ” 包含 “線索” 的存儲(chǔ)結(jié)構(gòu)，稱作 “ 線索鏈表 ” A B C D E F G H K ^ D ^ C ^ ^ B E ^ 對(duì) 線索鏈表 中結(jié)點(diǎn)的約定： 在二叉鏈表的結(jié)點(diǎn)中 增加兩個(gè)標(biāo)志域 ， 并作如下規(guī)定： 若該結(jié)點(diǎn)的左子樹不空， 則 Lchild域的指針指向其左子樹， 且左標(biāo)志域的值為“ 0”； 否則， Lchild域的指針指向其“前驅(qū)”， 且左標(biāo)志的值為“ 1” 。 // 左右指針 PointerThr LTag, RTag。 p。 // p指向根結(jié)點(diǎn) while (p != T) { // 空樹或遍歷結(jié)束時(shí)， p==T while (pLTag==Link) {p = plchild。 visit(pdata) // 訪問后繼結(jié)點(diǎn) } p = prchild。 data parent define MAX_TREE_SIZE 100 結(jié)點(diǎn)結(jié)構(gòu) : C語言的類型描述 : typedef struct { PTNode nodes [MAX_TREE_SIZE]。 struct CTNode *nextchild。 // 孩子鏈的頭指針 } CTBox。 樹結(jié)構(gòu) : A B C D E F G root A B C E D F G A B C E D F G 三、樹的二叉鏈表 (孩子 兄弟）存儲(chǔ)表示法 root typedef struct CSNode{ Elem data。 T1 = ( root， t11, t12, …, t 1m )。 否則， 由 (t11, t12, …, t 1m ) 對(duì)應(yīng)得到 LBT。 否則， 由 Node(root) 對(duì)應(yīng)得到 ROOT( T1 )。 若樹不空，則先依次后根遍歷各棵子樹，然后訪問根結(jié)點(diǎn)。森林中第一棵樹的子樹森林； 3。 先序遍歷 森林中 (除第一棵樹之外 )其 余樹構(gòu)成的森林。 中序遍歷 森林中 (除第一棵樹之外 )其 余樹構(gòu)成的森林。 } CSNode, *CSTree。 Return Max{d1+1,d2} int TreeDepth( CTree T ) { // T 是樹的孩子鏈表存儲(chǔ)結(jié)構(gòu)， // 返回該樹的深度 if ( == 0) return 0。 while ( p ) { h = Depth( T, pchild )。 } 哈 夫 曼 樹 與 哈 夫 曼 編 碼 ? 最優(yōu)樹的定義 ? 如何構(gòu)造最優(yōu)樹 ? 前綴編碼 一、最優(yōu)樹的定義 樹的路徑長度 定義為： 樹中每個(gè)結(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)值之 和 。 三、前綴編碼 利用赫夫曼樹可以構(gòu)造一種不等長的二進(jìn)制編碼，并且構(gòu)造所得的 赫夫曼編碼 是一種 最優(yōu)前綴編碼 ，即使所傳 電文的總長度最短 。以它們?yōu)楦魅~結(jié)點(diǎn)上的權(quán)值 , 建立霍夫曼樹。 總編碼長度正好等于霍夫 曼樹的帶權(quán)路徑長度 WPL。 2. 熟悉二叉樹的各種 存儲(chǔ)結(jié)構(gòu) 的特點(diǎn)及適用范圍。 層次遍歷 是按另一種搜索策略進(jìn)行的遍歷。建立存儲(chǔ)結(jié)構(gòu)是進(jìn)行其它操作的前提，因此應(yīng) 掌握 1 至 2 種 建立 二叉樹的 存儲(chǔ)結(jié)構(gòu)的方法 。 4 、已知一棵二叉樹的后序遍歷序列為LGHDIEBJKFCA，中序遍歷序列為GLDHBEIACJFK，畫出這棵二叉樹，并寫出后序遍歷序列。 編寫遞歸算法，在二叉樹中求位于先序序列中第 k個(gè)位置的結(jié)點(diǎn)的值。 exit(