【正文】 性質(zhì) 4: 具有 n個(gè)結(jié)點(diǎn)的完全二叉樹的深度必為 log2n ＋ 1 性質(zhì) 5: 對(duì)完全二叉樹，若從上至下、從左至右編號(hào)，則編號(hào)為 i 的結(jié)點(diǎn)，其左孩子編號(hào)必為 2i，其右孩子編號(hào)必為 2i＋ 1；其雙親的編號(hào)必為 i/2（ i＝ 1 時(shí)為根 ,除外 ）。 （特點(diǎn)：每層都“充滿”了結(jié)點(diǎn)） 完全二叉樹： 深度為 k 的 ， 有 n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為 k 的滿二叉樹中編號(hào)從 1至 n的結(jié)點(diǎn)一一對(duì)應(yīng)。 這其實(shí)是 順序 二叉樹 的含義。 Ａ )２ 9 Ｂ )２ 8 Ｃ )９ Ｄ )２ 9－ 1 k 的二叉樹的結(jié)點(diǎn)總數(shù)，最多為 個(gè)。 Ａ ) 高度 Ｂ ) 層次 Ｃ ) 深度 Ｄ ) 度 課堂討論： 滿二叉樹和完全二叉樹有什么區(qū)別 ？ 答： 滿二叉樹是葉子一個(gè)也不少的樹 ， 而完全二叉樹雖然前 n1層是滿的 ，但最底層卻允許在右邊缺少連續(xù)若干個(gè)結(jié)點(diǎn) 。 √ √ √ 27 二叉樹 1. 二叉樹的定義 2. 二叉樹的性質(zhì) 3. 二叉樹的存儲(chǔ)結(jié)構(gòu) 28 3. 二叉樹的存儲(chǔ)結(jié)構(gòu) 一、順序存儲(chǔ)結(jié)構(gòu) 按二叉樹的結(jié)點(diǎn) “ 自上而下 、 從左至右 ” 編號(hào) ， 用一組連續(xù)的存儲(chǔ)單元存儲(chǔ) 。 而且有規(guī)律：下標(biāo)值為 i的雙親，其左孩子的下標(biāo)值必為2i，其右孩子的下標(biāo)值必為 2i＋ 1（即性質(zhì) 5） 例如，對(duì)應(yīng) [2]的兩個(gè)孩子必為 [4]和 [5],即 B的左孩子必是 D,右孩子必為 E。 A B ^ C ^ ^ ^ D ^ … E [1] [2] [3] [4] [5] [6] [7] [8] [9] . [16] A B E C D 缺點(diǎn)： ① 浪費(fèi)空間；②插入、刪除不便 30 二、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 用二叉鏈表即可方便表示。 typedef struct node { int data。 } node。 （相應(yīng)地，訪問樹中結(jié)點(diǎn)時(shí)也只能從根開始） 注： 如果需要倒查某結(jié)點(diǎn)的雙親，可以再增加一個(gè)雙親域（直接前趨）指針，將二叉鏈表變成三叉鏈表。 Binary Tree ） 樹的基本概念 二叉樹 遍歷二叉樹和線索二叉樹 樹和森林 赫夫曼樹及其應(yīng)用 33 遍歷二叉樹和線索二叉樹 一、 遍歷二叉樹（ Traversing Binary Tree） 二、線索二叉樹（ Threaded Binary Tree） 34 遍歷定義 ——指按某條搜索路線遍訪每個(gè)結(jié)點(diǎn)且不重復(fù)（又稱周游）。 遍歷方法 ——牢記一種約定，對(duì)每個(gè)結(jié)點(diǎn)的查看都是“ 先左后右 ” 。 36 例 1： 先序遍歷的結(jié)果是： 中序遍歷的結(jié)果是： 后序遍歷的結(jié)果是： A B C D E A B D E C D B E A C D E B C A DLR—先序遍歷，即 先根再左再右 LDR—中序遍歷，即先左再根再右 LRD—后序遍歷，即先左再右再根 37 例 2： 用二叉樹表示算術(shù)表達(dá)式 先序： +a*bcd/ef 中序 A+b*cde/f 后序 abcd*+ef/ 38 先序遍歷算法 DLR(Node *root ) { if (root !=NULL) //非空二叉樹 { printf(“%d”,rootdata)。 //遞歸遍歷左子樹 DLR(rootrchild)。 } 中序遍歷算法 LDR(Node*root) { if(root !=NULL) {LDR(rootlchild)。 LDR(rootrchild)。 } 后序遍歷算法 LRD (Node *root) { if(root !=NULL) { LRD(rootlchild)。 printf(“%d”,rootdata)。 } 結(jié)點(diǎn)數(shù)據(jù)類型自定義 typedef struct Node{ int data。 39 對(duì)遍歷的分析： 1. 從前面的三種遍歷算法可以知道：如果將 printf語句抹去，從遞歸的角度看，這三種算法是完全相同的，或者說這三種遍歷算法的 訪問路徑是相同的，只是訪問結(jié)點(diǎn)的時(shí)機(jī)不同 。 A F E D C B G 第 1次 經(jīng)過時(shí)訪問＝ 先序 遍歷 第 2次 經(jīng)過時(shí)訪問＝ 中序 遍歷 第 3次 經(jīng)過時(shí)訪問＝ 后序 遍歷 2. 二叉樹遍歷的時(shí)間效率和空間效率 時(shí)間效率 :O(n) //每個(gè)結(jié)點(diǎn)只訪問一次 空間效率 :O(n) //棧占用的最大輔助空間 40 例： 【 嚴(yán)題集 ③】 編寫遞歸算法，計(jì)算二叉樹中葉子結(jié)點(diǎn)的數(shù)目。 DLR(Node *root) //采用中序遍歷的遞歸算法 { if ( root!=NULL ) //非空二叉樹條件 ， 還可寫成 if(root) {if(!rootlchildamp。!rootrchild) //是葉子結(jié)點(diǎn)則統(tǒng)計(jì)并打印 {sum++。} DLR(rootlchild)。 } //遞歸遍歷右子樹 ， 直到葉子處； } return(0)。T){ scanf(“%c”,amp。 if(ch==’’)T=NULL。 Tdata=ch。 createBTpre(Trchild)。 } 建樹 ——見教材 P131程序 42 習(xí)題討論： 1. 求二叉樹深度，或從 x結(jié)點(diǎn)開始的子樹深度。 2. 按層次輸出二叉樹中所有結(jié)點(diǎn)。 技巧： 當(dāng)根結(jié)點(diǎn)入隊(duì)后 ， 令其左 、 右孩子結(jié)點(diǎn)入隊(duì) ， 而左孩子出隊(duì)時(shí)又令它的左右孩子結(jié)點(diǎn)入隊(duì) ， …… 由此便可產(chǎn)生按層次輸出的效果 ?？芍苯佑?while語句和 push/pop操作。 （即順序二叉樹）。 技巧 :按層序遍歷方式 ， 先把所有結(jié)點(diǎn) （ 不管當(dāng)前結(jié)點(diǎn)是否有左右孩子 ） 都入隊(duì)列 .若為完全二叉樹 ,則層序遍歷時(shí)得到的肯定是一個(gè)連續(xù)的不包含空指針的序列 .如果序列中出現(xiàn)了空指針 ， 則說明不是完全二叉樹 。 例： 已知一棵二叉樹的 中序序列 和 后序序列 分別是 BDCEAFHG 和 DECBHGFA，請(qǐng)畫出這棵二叉樹。 45 中序遍歷： B D C E A F H G 后序遍歷： D E C B H G F A （ B D C E） （ F H G） A B F （ D C E） （ H G） C D E G H A B B FF 46 問： 用二叉鏈表法（ l_child, r_child）存儲(chǔ)包含 n個(gè)結(jié)點(diǎn)的二叉樹，結(jié)點(diǎn)的指針區(qū)域中會(huì)有多少個(gè)空指針？ 分析： 用二叉鏈表存儲(chǔ)包含 n個(gè)結(jié)點(diǎn)的二叉樹 ， 結(jié)點(diǎn)必有 2n個(gè)鏈域 （ 見二叉鏈表數(shù)據(jù)類型說明 ） 。 思考： 二叉鏈表空間效率這么低，能否利用這些空閑區(qū)存放有用的信息或線索？ ——我們可以用它來存放當(dāng)前結(jié)點(diǎn)的直接前驅(qū)和后繼等線索，以加快查找速度。 n+1 47 遍歷二叉樹和線索二叉樹 一、 遍歷二叉樹（ Traversing Binary Tree） 二、線索二叉樹（ Threaded Binary Tree） 48 二、 線索二叉樹 （ Threaded Binary Tree） 普通二叉樹只能找到結(jié)點(diǎn)的左右孩子信息， 而該結(jié)點(diǎn)的直接前驅(qū)和直接后繼只能在遍歷過程中獲得。 兩種解決方法 增加兩個(gè)域： fwd和 bwd； 利用空鏈域（ n+1個(gè)空鏈域） 存放前驅(qū)指針 存放后繼指針 如何預(yù)存這類信息？ 例如中序遍歷結(jié)果： B D C E A F H G，實(shí)際上 已將二叉樹轉(zhuǎn)為線性排列，顯然具有唯一前驅(qū)和唯一后繼！ 可能是根、或最左（右）葉子 49 規(guī) 定： 1）若結(jié)點(diǎn)有左子樹，則 lchild指向其左孩子； 否則， lchild指向其直接前驅(qū) (即線索 )； 2）若結(jié)點(diǎn)有右子樹，則 rchild指向其右孩子； 否則， rchild指向其直接后繼 (即線索 ) 。 當(dāng) Tag域?yàn)?1時(shí) ,表示 線索 情況 . 50 有關(guān)線索二叉樹的幾個(gè)術(shù)語： 線索鏈表： 用上一頁結(jié)點(diǎn)結(jié)構(gòu)所構(gòu)成的二叉鏈表 線 索： 指向結(jié)點(diǎn)前驅(qū)和后繼的指針 線索二叉樹： 加上線索的二叉樹 （圖形式樣） 線 索 化： 對(duì)二叉樹以 某種次序遍歷 使其變?yōu)榫€索二叉樹的過程 注： 在線索化二叉樹中，并不是每個(gè)結(jié)點(diǎn)都能直接找到其后繼的， 當(dāng)標(biāo)志為 0時(shí)，則需要通過一定運(yùn)算才能找到它的后繼 。 52 A B C G E I D H F root 懸空？ 懸空？ 解： 該二叉樹中序遍歷結(jié)果為 : H, D, I, B, E, A, F, C, G 所以添加線索應(yīng)當(dāng)按如下路徑進(jìn)行： 例 2： 畫出以下