【正文】 具有 n個(gè)結(jié)點(diǎn)的完全二叉樹的深度 k為 [log2n]+1。性質(zhì) 4一棵深度為 k的二叉樹中，最多具有 2k－ 1個(gè)結(jié)點(diǎn)。性質(zhì) 2二叉樹的 5個(gè)性質(zhì)。 數(shù)據(jù)結(jié)構(gòu)和算法簡(jiǎn)介數(shù)據(jù)結(jié)構(gòu) (C描述 )小結(jié)在本章中，你已經(jīng)學(xué)到：二叉樹（ Binary 數(shù)據(jù)結(jié)構(gòu)和算法簡(jiǎn)介數(shù)據(jù)結(jié)構(gòu) (C描述 )最優(yōu)二叉樹 ――哈夫曼樹 構(gòu)造算法（ 1）由給定的 n個(gè)權(quán)值 {W1， W2， … ， Wn}構(gòu)造 n棵只有一個(gè)葉結(jié)點(diǎn)的二叉樹，從而得到一個(gè)二叉樹的集合 F＝ {T1， T2， … ， Tn}；（ 2）在 F中選取根結(jié)點(diǎn)的權(quán)值最小和次小的兩棵二叉樹作為左、右子樹構(gòu)造一棵新的二叉樹，這棵新的二叉樹根結(jié)點(diǎn)的權(quán)值為其左、右子樹根結(jié)點(diǎn)權(quán)值之和；（ 3）在集合 F中刪除作為左、右子樹的兩棵二叉樹，并將新建立的二叉樹加入到集合 F中；（ 4）重復(fù)（ 2）（ 3）兩步，當(dāng) F中只剩下一棵二叉樹時(shí)，這棵二叉樹便是所要建立的哈夫曼樹。帶權(quán)路徑長(zhǎng)度將各不相同?；疽髣?dòng)態(tài)構(gòu)建二叉樹用遞歸實(shí)現(xiàn)該算法活動(dòng)：二叉樹操作數(shù)據(jù)結(jié)構(gòu)和算法簡(jiǎn)介數(shù)據(jù)結(jié)構(gòu) (C描述 )最優(yōu)二叉樹 ――哈夫曼樹 最優(yōu)二叉樹，也稱哈夫曼（ Haffman）樹，是指對(duì)于一組帶有確定權(quán)值的葉結(jié)點(diǎn)，構(gòu)造的具有最小帶權(quán)路徑長(zhǎng)度的二叉樹。圖 //將當(dāng)前結(jié)點(diǎn)的左孩子結(jié)點(diǎn)入隊(duì) } if ( != null) { ()。 //結(jié)點(diǎn)出隊(duì) ({o}, tmp)。 //根結(jié)點(diǎn)入隊(duì) (root)。 public void LevelOrder(NodeT root) { if (root == null) { //根結(jié)點(diǎn)為空 return。)。postorder()。!=if}empty)。(Tree{))if{ptr)void否則，（ 1）后序遍歷根結(jié)點(diǎn)的左子樹；（ 2）后序遍歷根結(jié)點(diǎn)的右子樹。inorder()。+inorder()。{null)(ptrreturn。is(IsEmpty())ptr)void否則，（ 1）中序遍歷根結(jié)點(diǎn)的左子樹；（ 2）訪問根結(jié)點(diǎn)；（ 3）中序遍歷根結(jié)點(diǎn)的右子樹。preorder()。)。({null)(ptrreturn。isif{ptr)void先序遍歷根結(jié)點(diǎn)的右子樹。訪問根結(jié)點(diǎn)；　　 (2)先序遍歷的遞歸過程為：若二叉樹為空，遍歷結(jié)束。 數(shù)據(jù)結(jié)構(gòu)和算法簡(jiǎn)介數(shù)據(jù)結(jié)構(gòu) (C描述 )二叉樹的遍歷與實(shí)現(xiàn) 1．先序遍歷（ DLR）若以 D、 L、 R分別表示訪問根結(jié)點(diǎn)、遍歷根結(jié)點(diǎn)的左子樹、遍歷根結(jié)點(diǎn)的右子樹，則二叉樹的遍歷方式有六種： DLR、 LDR、 LRD、 DRL、 RDL和 RLD。由二叉樹的定義可知，一棵二叉樹由根結(jié)點(diǎn)、根結(jié)點(diǎn)的左子樹和根結(jié)點(diǎn)的右子樹三部分組成。 public NodeT Search(NodeT root, T value)216。 public NodeT DeleteL(NodeT p)216。 public void InsertL(T val, NodeT p)216。 public NodeT GetLChild(NodeT p) 216。 public bool IsEmpty() 216。 public LinkBiTree(T val)216。 這種存儲(chǔ)結(jié)構(gòu)既便于查找孩子結(jié)點(diǎn)，又便于查找雙親結(jié)點(diǎn)。 數(shù)據(jù)結(jié)構(gòu)和算法簡(jiǎn)介數(shù)據(jù)結(jié)構(gòu) (C描述 )用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示二叉樹 （２）三叉鏈表存儲(chǔ)在三叉鏈表存儲(chǔ)中，每個(gè)結(jié)點(diǎn)由四個(gè)域組成 （ 1）二叉鏈表存儲(chǔ)鏈表中每個(gè)結(jié)點(diǎn)由三個(gè)域組成，除了數(shù)據(jù)域外，還有兩個(gè)指針域，分別用來給出該結(jié)點(diǎn)左孩子和右孩子所在的鏈結(jié)點(diǎn)的存儲(chǔ)地址。數(shù)據(jù)結(jié)構(gòu)和算法簡(jiǎn)介數(shù)據(jù)結(jié)構(gòu) (C描述 )用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示二叉樹 二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是指，用鏈表來表示一棵二叉樹，即用鏈表來指示著元素的邏輯關(guān)系。 的順序存儲(chǔ)如圖 ： 依據(jù)二叉樹的性質(zhì)，完全二叉樹和滿二叉樹采用順序存儲(chǔ)比較合適，樹中結(jié)點(diǎn)的序號(hào)可以唯一地反映出結(jié)點(diǎn)之間的邏輯關(guān)系。數(shù)據(jù)結(jié)構(gòu)和算法簡(jiǎn)介數(shù)據(jù)結(jié)構(gòu) (C描述 )用順序存儲(chǔ)結(jié)構(gòu)表示二叉樹 所謂二叉樹的順序存儲(chǔ)，就是用一組連續(xù)的存儲(chǔ)單元存放二叉樹中的結(jié)點(diǎn)。此外，若對(duì)二叉樹的根結(jié)點(diǎn)從 0開始編號(hào)，則相應(yīng)的 i號(hào)結(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號(hào)為（ i－ 1） /2，左孩子的編號(hào)為 2i＋ 1，右孩子的編號(hào)為 2i＋ 2。（ 3）如果 2i＋ 1≤n，則序號(hào)為 i的結(jié)點(diǎn)的右孩子結(jié)點(diǎn)的序號(hào)為 2i＋ 1；如果 2i＋ 1n，則序號(hào)為 i的結(jié)點(diǎn)無右孩子。（ 1）如果 i1，則序號(hào)為 i的結(jié)點(diǎn)的雙親結(jié)點(diǎn)的序號(hào)為 i/2(“/”表示整除 )；如果i＝ 1，則序號(hào)為 i的結(jié)點(diǎn)是根結(jié)點(diǎn)，無雙親結(jié)點(diǎn)。對(duì)于具有 n個(gè)結(jié)點(diǎn)的完全二叉樹，如果按照從上至下和從左到右的順序?qū)Χ鏄渲械乃薪Y(jié)點(diǎn)從 1開始順序編號(hào)，則對(duì)于任意的序號(hào)為 i的結(jié)點(diǎn)，有：性質(zhì) 5 一棵深度為 k的二叉樹中，最多具有 2k－ 1個(gè)結(jié)點(diǎn)。性質(zhì) 2一棵非空二叉樹的第 i層上最多有 2i1個(gè)結(jié)點(diǎn)（ i≥1）。數(shù)據(jù)結(jié)構(gòu)和算法簡(jiǎn)介數(shù)據(jù)結(jié)構(gòu) (C描述 )認(rèn)識(shí)二叉樹 ——識(shí)別二叉樹的主要性質(zhì)性質(zhì) 1Search（ bt， x）：在二叉樹 bt中查找數(shù)據(jù)元素 x。DeleteL（ bt， parent）：在二叉樹 bt中刪除結(jié)點(diǎn) parent的左子樹。InsertR（ bt， x， parent）：將數(shù)據(jù)域信息為 x的結(jié)點(diǎn)插入到二叉樹bt中作為結(jié)點(diǎn) parent的右孩子結(jié)點(diǎn)。InsertL（ bt， x， parent）：將數(shù)據(jù)域信息為 x的結(jié)點(diǎn)插入到二叉樹bt中作為結(jié)點(diǎn) parent的左孩子結(jié)點(diǎn)。數(shù)據(jù)結(jié)構(gòu)和算法簡(jiǎn)介數(shù)據(jù)結(jié)構(gòu) (C描述 )認(rèn)識(shí)二叉樹 ——識(shí)別二叉樹的基本操作Initiate（ bt）：建立一棵空二叉樹。一棵深度為 k的有 n個(gè)結(jié)點(diǎn)的二叉樹，對(duì)樹中的結(jié)點(diǎn)按從上至下、從左到右的順序進(jìn)行編號(hào)，如果編號(hào)為 i（ 1≤i≤n）的結(jié)點(diǎn)與滿二叉樹中編號(hào)為 i的結(jié)點(diǎn)在二叉樹中的位置相同，則這棵二叉樹稱為完全二叉樹。 （ 10） 滿二叉樹。（ 9） 樹的度。（ 8） 樹的深度。數(shù)據(jù)結(jié)構(gòu)和算法簡(jiǎn)介數(shù)據(jù)結(jié)構(gòu) (C描述 )認(rèn)識(shí)二叉樹 ——分析二叉樹的邏輯結(jié)構(gòu)３、二叉樹的相關(guān)術(shù)語 （ 7） 結(jié)點(diǎn)的層數(shù)。（ 6） 祖先、子孫。 如果一棵樹的一串結(jié)點(diǎn) n1,n2,…, nk有如下關(guān)系：結(jié)點(diǎn) ni是 ni+1的父結(jié)點(diǎn)（ 1≤ik） ,就把 n1,n2,…, nk稱為一條由 n1至 nk的路徑。具有同一個(gè)雙親的孩子結(jié)點(diǎn)互稱為兄弟。 樹中一個(gè)結(jié)點(diǎn)的子樹的根結(jié)點(diǎn)稱為這個(gè)結(jié)點(diǎn)的孩子。一棵樹的結(jié)點(diǎn)除葉結(jié)點(diǎn)外，其余的都是分支結(jié)點(diǎn)。（ 3） 分枝結(jié)點(diǎn)。（ 2） 葉結(jié)點(diǎn)。 Ф左子樹 右子樹 左子樹 右子樹２、二叉樹的５種形態(tài)　 　　數(shù)據(jù)結(jié)構(gòu)和算法簡(jiǎn)介數(shù)據(jù)結(jié)構(gòu) (C描述 )認(rèn)識(shí)二叉樹 ——分析二叉樹的邏輯結(jié)構(gòu)３、二叉樹的相關(guān)術(shù)語（ 1） 結(jié)點(diǎn)的度。當(dāng)集合為空時(shí)，稱該二叉樹為空二叉樹。數(shù)據(jù)結(jié)構(gòu)和算法簡(jiǎn)介數(shù)據(jù)結(jié)構(gòu) (C描述 )認(rèn)識(shí)二叉樹 ——分析二叉樹的邏輯結(jié)構(gòu)二叉樹的定義　 　　二叉樹（ Binary現(xiàn)需要實(shí)現(xiàn)如下的功能：選擇一種數(shù)據(jù)結(jié)構(gòu)在內(nèi)存中存放索引表，通過該數(shù)據(jù)結(jié)構(gòu)能高效地插入、刪除和搜索索引表；? 輸入任一關(guān)鍵字，顯示出查詢?cè)撽P(guān)鍵字的路徑。；解決二叉樹的編程問題數(shù)據(jù)結(jié)構(gòu) (C語言版 )數(shù)據(jù)結(jié)構(gòu)和算法簡(jiǎn)介數(shù)據(jù)結(jié)構(gòu) (C描述 )目標(biāo)在本章中，你將達(dá)到以下目標(biāo)：理解二叉樹的兩種存儲(chǔ)結(jié)構(gòu)解決二叉樹的編程問題構(gòu)造哈夫曼編碼數(shù)據(jù)結(jié)構(gòu)和算法簡(jiǎn)介數(shù)據(jù)結(jié)構(gòu) (C描述 )學(xué)習(xí)情境 ——用二叉樹解決快速搜索磁盤文件中的編程 [問題描述 ]磁盤上有一個(gè)文件，物理上隨機(jī)存儲(chǔ)了很多記錄，如下表 (a)，每條記錄有一個(gè)關(guān)鍵字 (職工號(hào) )段唯一的標(biāo)識(shí)該記錄。；稀疏矩陣的三元組順序表中除了存儲(chǔ)三元組外，還應(yīng)該存儲(chǔ)矩陣行數(shù)、列數(shù)和總的非零元素?cái)?shù)目，這樣才能唯一的確定一個(gè)矩陣 ；對(duì)特殊矩陣進(jìn)行壓縮存儲(chǔ)時(shí)，矩陣中值相同的元素只分配一個(gè)存儲(chǔ)空間，零元素不存儲(chǔ)；數(shù)據(jù)結(jié)構(gòu)和算法簡(jiǎn)介數(shù)據(jù)結(jié)構(gòu) (C描述 )小結(jié)（續(xù)）在本章中，你已經(jīng)學(xué)到：對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)的時(shí)侯需要存儲(chǔ)非零元素值的同時(shí)還要存儲(chǔ)非零元素在矩陣中的位置，即非零元素所在的行號(hào)和列號(hào)，也就是在存儲(chǔ)某個(gè)元素比如 aij的值的同時(shí)，還需要存儲(chǔ)該元素所在的行號(hào) i和它的列號(hào) j，這樣就構(gòu)成了一個(gè)三元組 (i,j,aij)的線性表 數(shù)組可以看作是線性表的推廣，一維數(shù)組為按順序存儲(chǔ)的線性表，二維數(shù)組為數(shù)據(jù)元素類型為一維數(shù)組的線性表，三維數(shù)組為數(shù)據(jù)元素類型為二維數(shù)組的線性表，依此類推；矩陣在科學(xué)計(jì)算和工程應(yīng)用中被泛使用，矩陣用二維數(shù)組來表示；在某些特殊情況下，經(jīng)常會(huì)出現(xiàn)一些階數(shù)很高的矩陣，其中含有很多值相同的元素或者零元素，為了節(jié)省存儲(chǔ)空間，經(jīng)常需要對(duì)這些矩陣進(jìn)行壓縮存儲(chǔ) 第二步：當(dāng)三元組表非空（ M矩陣的非零元不為 0）時(shí)，對(duì) M中的每一列col(0≤col≤n1)，通過從頭至尾掃描三元組表 data，找出所有列號(hào)等于 col的那些三元組，將它們的行號(hào)和列號(hào)互換后依次放人 N的 data中，即可得到 N的按行優(yōu)先的壓縮存貯表示 M[i][j]=N[j][i]? 矩陣轉(zhuǎn)置運(yùn)算是矩陣運(yùn)算中最重要的一項(xiàng)，它是將 mn的矩陣變成另外一個(gè) nm的矩陣，使原來矩陣中元素的行和列的位置互換而值保持不變，即若矩陣 N是矩陣 M的轉(zhuǎn)置矩陣，則有：數(shù)據(jù)結(jié)構(gòu)和算法簡(jiǎn)介數(shù)據(jù)結(jié)構(gòu) (C描述 )? 矩陣運(yùn)算通常包括矩陣轉(zhuǎn)置、矩陣加、矩陣乘、矩陣求逆等。認(rèn)識(shí)稀疏矩陣 ——稀疏矩陣的壓縮存儲(chǔ) (續(xù)）數(shù)據(jù)結(jié)構(gòu)和算法簡(jiǎn)介數(shù)據(jù)結(jié)構(gòu) (C描述 )? 十字鏈表可以看作是由各個(gè)行鏈表和列鏈表共同搭建起來的一個(gè)綜合鏈表，每個(gè)結(jié)點(diǎn) aij既是處在第 i行鏈表的一個(gè)結(jié)點(diǎn)，同時(shí)也是處在第 j列鏈表上的一個(gè)結(jié)點(diǎn)，就你是處在十字交叉路口上的一個(gè)結(jié)點(diǎn)一樣，這就是十字鏈表的由來 認(rèn)識(shí)稀疏矩陣 ——稀疏矩陣的壓縮存儲(chǔ)行頭和列頭結(jié)點(diǎn)，這類結(jié)點(diǎn)也有域組成，其中行和列的值均為零，沒有實(shí)際意義， right和 down的域用于在行方向和列方向上指向表結(jié)點(diǎn)， next用于指向下一個(gè)行或列的表頭結(jié)點(diǎn) :數(shù)據(jù)結(jié)構(gòu)和算法簡(jiǎn)介數(shù)據(jù)結(jié)構(gòu) (C描述 )順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)三元組線性表的 C代碼參見 P121頁認(rèn)識(shí)稀疏矩陣 ——稀疏矩陣的壓縮存儲(chǔ) 1. 用 順序 表存儲(chǔ)稀疏矩陣的三元組 認(rèn)識(shí)稀疏矩陣 ——稀疏矩陣的壓縮存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)和算法簡(jiǎn)介數(shù)據(jù)結(jié)構(gòu) (C描述 )由于非零元素分布沒有任何規(guī)律，所以在進(jìn)行壓縮存儲(chǔ)的時(shí)侯需要存儲(chǔ)非零元素值的同時(shí)還要存儲(chǔ)非零元素在矩陣中的位置，即非零元素所在的行號(hào)和列號(hào)，也就是在存儲(chǔ)某個(gè)元素比如 aij的值的同時(shí)，還需要存儲(chǔ)該元素所在的行號(hào) i和它的列號(hào) j，這樣就構(gòu)成了一個(gè)三元組 (i,j,aij)的線性表 學(xué)習(xí)情境 ——用稀疏矩陣解決超市物品購(gòu)買數(shù)據(jù)的編程數(shù)據(jù)結(jié)構(gòu)和算法簡(jiǎn)介數(shù)據(jù)結(jié)構(gòu) (C描述 )對(duì)于那些零元素?cái)?shù)目遠(yuǎn)遠(yuǎn)多于非零元素?cái)?shù)目，并且非零元素的分布沒有規(guī)律的矩陣稱為稀疏矩陣（ sparse）人們無法給出稀疏矩陣的確切定義，一般都只是憑個(gè)人的直覺來理解這個(gè)概念，即矩陣中非零元素的個(gè)數(shù)遠(yuǎn)遠(yuǎn)小于矩陣元素的總數(shù)，并且非零元素沒有分布規(guī)律 *price是一個(gè) 10001的矩陣，它給出每個(gè)顧客所花費(fèi)的購(gòu)物金額。的單價(jià)。超級(jí)市場(chǎng)有一個(gè) 10， 0001的價(jià)格矩陣 price， price(i)表示顧客 j(i,認(rèn)識(shí)特殊矩陣 ——用特殊矩陣解決查詢城市間距離的編程數(shù)據(jù)結(jié)構(gòu)和算法簡(jiǎn)介數(shù)據(jù)結(jié)構(gòu) (C描述 )[問題描述 ]某超級(jí)市場(chǎng)正在開展一項(xiàng)關(guān)于顧客購(gòu)物品種的研究。數(shù)據(jù)結(jié)構(gòu)和算法簡(jiǎn)介數(shù)據(jù)結(jié)構(gòu) (C描述 )代碼請(qǐng)參見 P118119頁 ,這樣存儲(chǔ)單元的總數(shù)是：認(rèn)識(shí)特殊矩陣 ——特殊矩陣的壓縮存儲(chǔ)可以以行序?yàn)橹鬟M(jìn)行壓縮存儲(chǔ)，也可以以列序?yàn)橹鬟M(jìn)行壓縮存儲(chǔ)。所示。)。(j,)(i,和 jitmy所示 。0。)(i,jtriangular）： M是一個(gè)上三角矩陣當(dāng)且僅當(dāng) i所示。0。)(i,jtriangular）： M是一個(gè)下三角矩陣當(dāng)且僅當(dāng) i所示。0。)時(shí)有 M(i,jiaoadr? 三對(duì)角矩陣（ 如圖 =時(shí)有 M(i,aoa特殊矩陣通常有：? 對(duì)角矩陣（ d；? 當(dāng)用戶任意輸入兩個(gè)城市的名字，將在屏幕上顯示這兩個(gè)城市間的距離。)，所以該矩陣是一個(gè)對(duì)稱矩陣。(j,j)=有 distance由于對(duì)于所有的 i之間的距離。代表城市 ij個(gè)城市， distance任意兩個(gè)城市之間的距離可以用一個(gè)66的矩陣來表示。Orlando,Tallahassee和 Tampa。Jacksonville,當(dāng)在程序中聲明并創(chuàng)建了一個(gè)數(shù)組后，該數(shù)組就是一個(gè) Array類的實(shí)例，該類除了具有在 ，還有很多其他的屬性和方法