【正文】 點是：葉子結(jié)點只能出現(xiàn)在最下層和次下層，且最下層的葉子結(jié)點集中在樹的左部。數(shù)據(jù)結(jié)構(gòu)和算法簡介數(shù)據(jù)結(jié)構(gòu) (C描述 )認(rèn)識二叉樹 ——識別二叉樹的基本操作Initiate（ bt）：建立一棵空二叉樹。Create（ x， lbt， rbt）：生成一棵以 x為根結(jié)點的數(shù)據(jù)域信息，以二叉樹 lbt和 rbt為左子樹和右子樹的二叉樹。InsertL（ bt， x， parent）：將數(shù)據(jù)域信息為 x的結(jié)點插入到二叉樹bt中作為結(jié)點 parent的左孩子結(jié)點。如果結(jié)點 parent原來有左孩子結(jié)點，則將結(jié)點 parent原來的左孩子結(jié)點作為結(jié)點 x的左孩子結(jié)點。InsertR（ bt， x， parent）：將數(shù)據(jù)域信息為 x的結(jié)點插入到二叉樹bt中作為結(jié)點 parent的右孩子結(jié)點。如果結(jié)點 parent原來有右孩子結(jié)點，則將結(jié)點 parent原來的右孩子結(jié)點作為結(jié)點 x的右孩子結(jié)點。DeleteL（ bt， parent）：在二叉樹 bt中刪除結(jié)點 parent的左子樹。DeleteR（ bt， parent）：在二叉樹 bt中刪除結(jié)點 parent的右子樹。Search（ bt， x）：在二叉樹 bt中查找數(shù)據(jù)元素 x。Traverse（ bt）：按某種方式遍歷二叉樹 bt的全部結(jié)點。數(shù)據(jù)結(jié)構(gòu)和算法簡介數(shù)據(jù)結(jié)構(gòu) (C描述 )認(rèn)識二叉樹 ——識別二叉樹的主要性質(zhì)性質(zhì) 1一棵非空二叉樹的第 i層上最多有 2i1個結(jié)點（ i≥1）。 性質(zhì) 2一棵深度為 k的二叉樹中，最多具有 2k－ 1個結(jié)點。性質(zhì) 3對于一棵非空的二叉樹，如果葉子結(jié)點數(shù)為 n0，度數(shù)為 2的結(jié)點數(shù)為 n2，則有 :n0＝ n2＋ 1。 性質(zhì) 4具有 n個結(jié)點的完全二叉樹的深度 k為 [log2n]+1。性質(zhì) 5對于具有 n個結(jié)點的完全二叉樹，如果按照從上至下和從左到右的順序?qū)Χ鏄渲械乃薪Y(jié)點從 1開始順序編號，則對于任意的序號為 i的結(jié)點，有：（ 1）如果 i1，則序號為 i的結(jié)點的雙親結(jié)點的序號為 i/2(“/”表示整除 )；如果i＝ 1，則序號為 i的結(jié)點是根結(jié)點，無雙親結(jié)點。（ 2）如果 2i≤n，則序號為 i的結(jié)點的左孩子結(jié)點的序號為 2i；如果 2in，則序號為 i的結(jié)點無左孩子。（ 3）如果 2i＋ 1≤n，則序號為 i的結(jié)點的右孩子結(jié)點的序號為 2i＋ 1；如果 2i＋ 1n，則序號為 i的結(jié)點無右孩子。此外，若對二叉樹的根結(jié)點從 0開始編號，則相應(yīng)的 i號結(jié)點的雙親結(jié)點的編號為（ i－ 1） /2，左孩子的編號為 2i＋ 1，右孩子的編號為 2i＋ 2。 數(shù)據(jù)結(jié)構(gòu)和算法簡介數(shù)據(jù)結(jié)構(gòu) (C描述 )用順序存儲結(jié)構(gòu)表示二叉樹 所謂二叉樹的順序存儲，就是用一組連續(xù)的存儲單元存放二叉樹中的結(jié)點。一般是按照二叉樹結(jié)點從上至下、從左到右的順序存儲。 依據(jù)二叉樹的性質(zhì)，完全二叉樹和滿二叉樹采用順序存儲比較合適，樹中結(jié)點的序號可以唯一地反映出結(jié)點之間的邏輯關(guān)系。圖 (a)的順序存儲如圖 ： 數(shù)據(jù)結(jié)構(gòu)和算法簡介數(shù)據(jù)結(jié)構(gòu) (C描述 )用順序存儲結(jié)構(gòu)表示二叉樹 對于一般的二叉樹，如果仍按從上至下和從左到右的順序?qū)渲械慕Y(jié)點順序存儲在一維數(shù)組中，則數(shù)組元素下標(biāo)之間的關(guān)系不能夠反映二叉樹中結(jié)點之間的邏輯關(guān)系，只有增添一些并不存在的空結(jié)點，使之成為一棵完全二叉樹的形式，然后再用一維數(shù)組順序存儲。 數(shù)據(jù)結(jié)構(gòu)和算法簡介數(shù)據(jù)結(jié)構(gòu) (C描述 )用鏈?zhǔn)酱鎯Y(jié)構(gòu)表示二叉樹 二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)是指，用鏈表來表示一棵二叉樹，即用鏈表來指示著元素的邏輯關(guān)系。 （ 1）二叉鏈表存儲鏈表中每個結(jié)點由三個域組成，除了數(shù)據(jù)域外，還有兩個指針域，分別用來給出該結(jié)點左孩子和右孩子所在的鏈結(jié)點的存儲地址。圖 (a)給出了圖 (b)所示的一棵二叉樹的二叉鏈表示。 數(shù)據(jù)結(jié)構(gòu)和算法簡介數(shù)據(jù)結(jié)構(gòu) (C描述 )用鏈?zhǔn)酱鎯Y(jié)構(gòu)表示二叉樹 （２）三叉鏈表存儲在三叉鏈表存儲中，每個結(jié)點由四個域組成 parent域為指向該結(jié)點雙親結(jié)點的指針。這種存儲結(jié)構(gòu)既便于查找孩子結(jié)點，又便于查找雙親結(jié)點。圖 (b)所示的一棵二叉樹的三叉鏈表示。 數(shù)據(jù)結(jié)構(gòu)和算法簡介數(shù)據(jù)結(jié)構(gòu) (C描述 )實現(xiàn)鏈?zhǔn)酱鎯Φ亩鏄涞幕静僮?16。 public LinkBiTree(T val)216。 public LinkBiTree(T val, NodeT lp, NodeT rp) 216。 public bool IsEmpty() 216。 public NodeT Root()216。 public NodeT GetLChild(NodeT p) 216。 public NodeT GetRChild(NodeT p)216。 public void InsertL(T val, NodeT p)216。 public void InsertR(T val, NodeT p)216。 public NodeT DeleteL(NodeT p)216。 public NodeT DeleteR(NodeT p)216。 public NodeT Search(NodeT root, T value)216。 public bool IsLeaf(NodeT p)具體操作參與 P140143數(shù)據(jù)結(jié)構(gòu)和算法簡介數(shù)據(jù)結(jié)構(gòu) (C描述 )二叉樹的遍歷與實現(xiàn) 二叉樹的遍歷是指按照某種順序訪問二叉樹中的每個結(jié)點，使每個結(jié)點被訪問一次且僅被訪問一次。由二叉樹的定義可知，一棵二叉樹由根結(jié)點、根結(jié)點的左子樹和根結(jié)點的右子樹三部分組成。因此，只要依次遍歷這三部分，就可以遍歷整個二叉樹。若以 D、 L、 R分別表示訪問根結(jié)點、遍歷根結(jié)點的左子樹、遍歷根結(jié)點的右子樹，則二叉樹的遍歷方式有六種： DLR、 LDR、 LRD、 DRL、 RDL和 RLD。如果限定先左后右，則只有前三種方式，即 DLR（稱為先序遍歷）、 LDR（稱為中序遍歷）和 LRD（稱為后序遍歷）。 數(shù)據(jù)結(jié)構(gòu)和算法簡介數(shù)據(jù)結(jié)構(gòu) (C描述 )二叉樹的遍歷與實現(xiàn) 1．先序遍歷（ DLR）先序遍歷的遞歸過程為：若二叉樹為空，遍歷結(jié)束。否則，　　 (1)訪問根結(jié)點；　　 (2)先序遍歷根結(jié)點的左子樹；　　 (3)先序遍歷根結(jié)點的右子樹?！?publicvoidpreorder(NodeTptr){if(IsEmpty()){(Treeisempty)。return。}if(ptr!=null){(+)。preorder()。preorder()。}}數(shù)據(jù)結(jié)構(gòu)和算法簡介數(shù)據(jù)結(jié)構(gòu) (C描述 )二叉樹的遍歷與實現(xiàn) 2．中序遍歷（ LDR）中序遍歷的遞歸過程為：若二叉樹為空，遍歷結(jié)束。否則，（ 1）中序遍歷根結(jié)點的左子樹；（ 2）訪問根結(jié)點；（ 3）中序遍歷根結(jié)點的右子樹。publicvoidinorder(NodeTptr){if(IsEmpty()){(Treeisempty)。return。}if(ptr!=null){inorder()。(+)。inorder()。}}數(shù)據(jù)結(jié)構(gòu)和算法簡介數(shù)據(jù)結(jié)構(gòu) (C描述 )二叉樹的遍歷與實現(xiàn) 3．后序遍歷（ LRD）后序遍歷的遞歸過程為：若二叉樹為空，遍歷結(jié)束。否則，（ 1）后序遍歷根結(jié)點的左子樹；（ 2）后序遍歷根結(jié)點的右子樹。（ 3）訪問根結(jié)點； publicvoidpostorder(NodeTptr){if(IsEmpty()){(Treeisempty)。return。}if(ptr!=null){postorder()。postorder()。(+)。}}數(shù)據(jù)結(jié)構(gòu)和算法簡介數(shù)據(jù)結(jié)構(gòu) (C描述 )二叉樹的遍歷與實現(xiàn) 4．層次遍歷所謂二叉樹的層次遍歷，是指從二叉樹的第一層（根結(jié)點）開始，從上至下逐層遍歷，在同一層中，則按從左到右的順序?qū)Y(jié)點逐個訪問。 public void LevelOrder(NodeT root) { if (root == null) { //根結(jié)點為空 return。 } //設(shè)置一個隊列保存層序遍歷的結(jié)點 CSeqQueueNodeT sq = new CSeqQueueNodeT(50)。 //根結(jié)點入隊 (root)。 while (!()) {//隊列非空，結(jié)點沒有處理完 NodeT tmp = ()。 //結(jié)點出隊 ({o}, tmp)。 //處理當(dāng)前結(jié)點 if ( != null) { ()。 //將當(dāng)前結(jié)點的左孩子結(jié)點入隊 } if ( != null) { ()。 //將當(dāng)前結(jié)點的右孩子結(jié)點入隊 } } }數(shù)據(jù)結(jié)構(gòu)和算法簡介數(shù)據(jù)結(jié)構(gòu) (C描述 )用二叉搜索樹解決快速搜索磁盤文件中記錄的問題 在二叉樹中，如果一個結(jié)點的左子結(jié)點的值永遠(yuǎn)小于該結(jié)點的值，而右子結(jié)點的值永遠(yuǎn)大于該結(jié)點的值，這樣的二叉樹為二叉搜索樹。圖 為基于圖 (b)所示的索引表建立的二叉搜索樹，用二叉搜索樹解決快速搜磁盤文件記錄代碼 參見 P147150數(shù)據(jù)結(jié)構(gòu)和算法簡介數(shù)據(jù)結(jié)構(gòu) (C描述 )問題描述：統(tǒng)計出二叉樹中葉子結(jié)點的數(shù)目 基本要求動態(tài)構(gòu)建二叉樹用遞歸實現(xiàn)該算法活動：二叉樹操作數(shù)據(jù)結(jié)構(gòu)和算法簡介數(shù)據(jù)結(jié)構(gòu) (C描述 )最優(yōu)二叉樹 ――哈夫曼樹 最優(yōu)二叉樹，也稱哈夫曼（ Haffman）樹，是指對于一組帶有確定權(quán)值的葉結(jié)點，構(gòu)造的具有最小帶權(quán)路徑長度的二叉樹。設(shè)二叉樹具有 n個帶權(quán)值的葉結(jié)點，那么從根結(jié)點到各個葉結(jié)點的路徑長度與相應(yīng)葉結(jié)點權(quán)值的乘積之和叫做二叉樹的帶權(quán)路徑長度，記為：例： 4個葉結(jié)點，其權(quán)值分別為 1， 3， 5， 7，可構(gòu)造出形狀不同的多個二叉樹。帶權(quán)路徑長度將各不相同。圖 5個不同形狀的二叉樹。 數(shù)據(jù)結(jié)構(gòu)和算法簡介數(shù)據(jù)結(jié)構(gòu) (C描述 )最優(yōu)二叉樹 ――哈夫曼樹 構(gòu)造算法（ 1）由給定的 n個權(quán)值 {W1， W2， … ， Wn}構(gòu)造 n棵只有一個葉結(jié)點的二叉樹，從而得到一個二叉樹的集合 F＝ {T1， T2， … ， Tn}；（ 2）在 F中選取根結(jié)點的權(quán)值最小和次小的兩棵二叉樹作為左、右子樹構(gòu)造一棵新的二叉樹，這棵新的二叉樹根結(jié)點的權(quán)值為其左、右子樹根結(jié)點權(quán)值之和；（ 3）在集合 F中刪除作為左、右子樹的兩棵二叉樹，并將新建立的二叉樹加入到集合 F中；（ 4）重復(fù)（ 2）（ 3）兩步，當(dāng) F中只剩下一棵二叉樹時，這棵二叉樹便是所要建立的哈夫曼樹。葉結(jié)點權(quán)值集合為W＝ {1， 3， 5， 7}的哈夫曼樹的構(gòu)造過程。 數(shù)據(jù)結(jié)構(gòu)和算法簡介數(shù)據(jù)結(jié)構(gòu) (C描述 )小結(jié)在本章中，你已經(jīng)學(xué)到：二叉樹（ BinaryTree）是個有限元素的集合，該集合或者為空、或者由一個稱為根 (root)的元素及兩個不相交的、被分別稱為左子樹和右子樹的二叉樹組成二叉樹中的相關(guān)概念：結(jié)點的度，葉結(jié)點，分枝結(jié)點，左孩子、右孩子、雙親，路徑、路徑長度，祖先、子孫，結(jié)點的層數(shù)，樹的深度，樹的度，滿二叉樹，完全二叉樹。二叉樹的 5個性質(zhì)。性質(zhì) 1一棵非空二叉樹的第 i層上最多有 2i1個結(jié)點（ i≥1）。性質(zhì) 2一棵深度為 k的二叉樹中，最多具有 2k－ 1個結(jié)點。性質(zhì) 3對于一棵非空的二叉樹，如果葉子結(jié)點數(shù)為 n0，度數(shù)為 2的結(jié)點數(shù)為 n2，則有 :n0＝ n2＋ 1。性質(zhì) 4具有 n個結(jié)點的完全二叉樹的深度 k為 [log2n]+1。數(shù)據(jù)結(jié)構(gòu)和算法簡介數(shù)據(jù)結(jié)構(gòu) (C描述 )小結(jié)（續(xù)）性質(zhì) 5對于