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