【正文】 )。 無序樹： 子樹之間不存在確定的次序關(guān)系。T) // 銷毀樹的結(jié)構(gòu) DeleteChild(amp。T, definition) // 按定義構(gòu)造樹 Assign(T, cur_e, value) // 給當(dāng)前結(jié)點(diǎn)賦值 InsertChild(amp。 若 D為空集，則稱為空樹 。 否則 : (1) 在 D中存在唯一的稱為根的數(shù)據(jù)元素 root； (2) 當(dāng) n1時(shí)，其余結(jié)點(diǎn)可分為 m (m0)個(gè)互 不相交的有限集 T1, T2, … , Tm，其中每一 棵子集本身又是一棵符合本定義的樹， 稱為根 root的子樹。T, amp。T, amp。 任何一棵非空樹是一個(gè)二元組 Tree = （ root， F） 其中： root 被稱為根結(jié)點(diǎn) F 被稱為子樹森林 森林： 是 m（ m≥ 0）棵互 不相交的樹的集合 A root B C D E F G H I J M K L F 二叉樹的類型定義 二叉樹或?yàn)?空樹 ，或是由一個(gè) 根結(jié)點(diǎn) 加上 兩棵 分別稱為 左子樹 和 右子樹的、 互不交的 二叉樹 組成。 LeftChild(T, e)。 BiTreeEmpty(T)。 PostOrderTraverse(T, Visit())。 Assign(T, amp。 InsertChild(T, p, LR, c)。T)。 ?性質(zhì) 2 ： 深度為 k 的二叉樹上至多含 2k1 個(gè)結(jié)點(diǎn)（ k≥ 1）。 兩類 特殊 的二叉樹： 滿二叉樹 ： 指的是深度為 k且含有 2k1個(gè)結(jié)點(diǎn)的二叉樹。 ?性質(zhì) 5 ： 若對(duì)含 n 個(gè)結(jié)點(diǎn)的完全二叉樹從上到下且從左至右進(jìn)行 1 至 n 的編號(hào)，則對(duì)完全二叉樹中任意一個(gè)編號(hào)為 i 的結(jié)點(diǎn)： (1) 若 i=1，則該結(jié)點(diǎn)是二叉樹的根，無雙親， 否則，編號(hào)為 ?i/2? 的結(jié)點(diǎn)為其 雙親 結(jié)點(diǎn)； (2) 若 2in，則該結(jié)點(diǎn)無左孩子， 否則，編號(hào)為 2i 的結(jié)點(diǎn)為其 左孩子 結(jié)點(diǎn)； (3) 若 2i+1n，則該結(jié)點(diǎn)無右孩子結(jié)點(diǎn)， 否則，編號(hào)為 2i+1 的結(jié)點(diǎn)為其 右孩子 結(jié)點(diǎn) 。 struct BiTNode *lchild, *rchild。 // 左右孩子指針 struct TriTNode *parent。 “遍歷 ”是任何類型均有的操作， 對(duì)線性結(jié)構(gòu)而言，只有一條搜索路 徑 (因?yàn)槊總€(gè)結(jié)點(diǎn)均只有一個(gè)后繼 )， 故不需要另加討論。下面我們將給出一棵二叉樹及其按層次順序訪問其中每個(gè)結(jié)點(diǎn)的遍歷序列。 // 訪問結(jié)點(diǎn) Preorder(Tlchild, visit)。 e)) { // 中序遍歷二叉樹 if (T) { Inreorder(Tlchild, visit)。 后（根）序的遍歷算法： void Postorder (BiTree T, void( *visit)(TElemTypeamp。 // 訪問結(jié)點(diǎn) } } 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)。 p) Push(S,plchild)。 Push(S,prchild)。 while(p||!StackEmpty(S)){ if(p) {Push(S,p)。 p=prchild。 Status CreateBiTree (BiTree amp。 else{ if(!(T=(BiTNode *)malloc(sizeof(BiTNode))) exit(OVERFLOW)。 //構(gòu)造右子樹 } return(OK)。 count){ if ( T ) { if ((!Tlchild)amp。 CountLeaf( Trchild, count)。 int Depth (BiTree T ){ // 返回二叉樹的深度 if ( !T ) depthval = 0。 } return depthval。 如此定義的二叉樹的存儲(chǔ)結(jié)構(gòu)稱作“ 線索鏈表 ”。 // 左右指針 PointerThr LTag, RTag。 p。 若 無右子樹， 則為 后繼線索 所指結(jié)點(diǎn)； 否則為 對(duì)其 右子樹 進(jìn)行中序 遍歷 時(shí)訪問的 第一個(gè)結(jié)點(diǎn)。 while (pRTag==Thread amp。 } // 訪問后繼結(jié)點(diǎn) p = prchild。 // 左子樹線索化 if (!plchild) // 建前驅(qū)線索 { pLTag = Thread。 } pre = p。 ThrtLTag = Link。 else { Thrtlchild = T。 preRTag = Thread。 int parent。 // 根結(jié)點(diǎn)的位置和結(jié)點(diǎn)個(gè)數(shù) } PTree。 孩子結(jié)點(diǎn)結(jié)構(gòu) : child next C語言的類型描述 : typedef struct { Elem data。 int n, r。 } CSNode, *CSTree。 由森林轉(zhuǎn)換成二叉樹 的 轉(zhuǎn)換規(guī)則為 : 若 F = Φ，則 B = Φ； 否則， 由 ROOT( T1 ) 對(duì)應(yīng)得到 Node(root)； 由 (t11, t12, …, t 1m ) 對(duì)應(yīng)得到 LBT； 由 (T2, T3,…, T n ) 對(duì)應(yīng)得到 RBT。 樹和森林的遍歷 一、樹的遍歷 二、森林的遍歷 樹的遍歷可有三條搜索路徑 : 按層次遍歷 : 先根 (次序 )遍歷 : 后根 (次序 )遍歷 : 若樹不空，則先訪問根結(jié)點(diǎn)，然后依次先根遍歷各棵子樹。 森林由三部分構(gòu)成： 二、森林的遍歷 若森林不空，則 訪問 森林中第一棵樹的根結(jié)點(diǎn)； 先序遍歷 森林中第一棵樹的子樹森林； 先序遍歷 森林中 (除第一棵樹之外 )其 余樹構(gòu)成的森林。 B C D E F G H I J K 例如 ： 先序遍歷時(shí)頂點(diǎn)的訪問次序： B E F C D G H I J K 后序遍歷時(shí)頂點(diǎn)的訪問次序： E F B C I J K H G D 樹的遍歷和二叉樹遍歷的對(duì)應(yīng)關(guān)系 ？ 先根遍歷 后根遍歷 樹 二叉樹 森林 先序遍歷 先序遍歷 中序遍歷 中序遍歷 哈 夫 曼 樹 與 哈 夫 曼 編 碼 ? 最優(yōu)樹 (哈夫曼樹 )的定義 ? 如何構(gòu)造最優(yōu)樹 ? 前綴編碼 ? 哈夫曼編碼 一、最優(yōu)樹的定義 樹的路徑長度 定義為： 樹中每個(gè)結(jié)點(diǎn)的路徑長度之和。 在所有含 n 個(gè)葉子結(jié)點(diǎn)、并帶相同權(quán) 值的 m 叉樹中，必存在一棵其 帶權(quán)路徑 長度取最小值 的樹，稱為“ 最優(yōu)樹 ”。 ③ 哈夫曼樹是嚴(yán)格的二叉樹，沒有度數(shù)為 1的分支結(jié)點(diǎn)。 1. 等長編碼 這種編碼方式的特點(diǎn) : 每個(gè)字符的編碼 長度相同 。 這種編碼的特點(diǎn) : 譯碼簡單且具有唯一性，但編碼長度并不是 最短的。稱為哈夫曼編碼 哈夫曼編碼 （ 1）利用字符集中每個(gè)字符的使用 頻率作為權(quán)值構(gòu)造一個(gè)哈夫曼樹； （ 2）從根結(jié)點(diǎn)開始，為到每個(gè)葉子 結(jié)點(diǎn)路徑上的左分支賦予 0，右分支 賦予 1，并從根到葉子方向形成該葉子 結(jié)點(diǎn)的編碼。 哈夫曼編碼的存儲(chǔ)結(jié)構(gòu) Weight parent lchild rchild 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 5 29 7 8 14 23 3 11 0 1 2 3 4