【正文】 左子樹 和 右子樹的、 互不交的 二叉樹 組成。 (2) Create（ bt）： 創(chuàng)建一棵非空二叉樹 bt。 (4) Empty（ bt）： 若 bt為空，則返回 TRUE，否則返回 FALSE。若 bt為空二叉樹，則函數(shù)返回“空”。求二叉樹 bt中結(jié)點 x的雙親結(jié)點。 16 (7) LeftChild（ bt， x）： 求左孩子。 (8) RightChild（ bt， x）： 求右孩子。 (9) Traverse（ bt） : 遍歷操作。 (10) Clear（ bt）： 清除操作。 17 三、二叉樹的性質(zhì) 18 ? 性質(zhì) 1 ： 在二叉樹的第 i 層上至多有 2i1 個結(jié)點。 二叉樹上每個結(jié)點至多有兩棵子樹， 則第 i 層的結(jié)點數(shù) = 2i2? 2 = 2i1 。 結(jié)點編號： 一般從根開始按層自上而下 , 每層從左至右對結(jié)點連續(xù)編號。 完全二叉樹： 樹中所含的 n 個結(jié)點和滿二叉樹中 編號為 1 至 n 的結(jié)點 一一對應(yīng)。 (2) 若 2in，則該結(jié)點無左孩子， 否則，編號為 2i 的結(jié)點為其 左孩子 結(jié)點； (3) 若 2i+1n，則該結(jié)點無右孩子結(jié)點， 否則，編號為 2i+1 的結(jié)點為其 右孩子 結(jié)點 。 25 二叉樹的存儲結(jié)構(gòu) 二、鏈?zhǔn)酱鎯Ρ硎? 一、 順序存儲表示 二叉樹的結(jié)構(gòu)是非線性的 ， 每一個結(jié)點最多可有兩個后繼 。 可用一維數(shù)組存儲： bt[n] 順序：完全二叉樹中將編號 i的結(jié)點存在分量 bt[i]中。 29 單支二叉樹 1 3 7 A B C A B C D 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 D 15 順序存儲只適用于完全二叉樹和滿二叉樹 30 二、鏈?zhǔn)酱鎯Y(jié)構(gòu) 對于任意的二叉樹來說，每個結(jié)點最多只有兩個孩子，我們可以設(shè)計每個二叉樹結(jié)點包括三個域： 數(shù)據(jù)域、左孩子域和右孩子域 。 LChild Data RChild RChild Parent Data LChild 31 D A B C E F G A ? B C D ? ? E ? ? F ? ? G ? 二叉樹 T 二叉鏈表 一個二叉樹若含有 n個結(jié)點，則它的二叉鏈表中含有 2n個指針域，其中必有 n＋ 1個空的鏈域。 struct BiTNode *lchild, *rchild。 lchild data rchild 結(jié)點結(jié)構(gòu) : C 語言的類型描述如下 : 33 root A D E B C F ? ? ? ? ? ? ? ? 2． 三叉鏈表 34 三叉鏈表類型表述如下： typedef char DataType。 struct Node *parent。 struct Node *rchild。 結(jié)點結(jié)構(gòu) : lchild data rchild parent 35 一、遍歷的含義 三、算法的遞歸描述 四 、 二叉樹的應(yīng)用舉例 二、先左后右的遍歷算法 36 五、由遍歷序列確定 二叉樹 遍歷： 按 一定規(guī)律 訪問 二叉樹中的每個結(jié)點，使得每個結(jié)點均被 訪問一次 ，而且 僅被訪問一次 。 一、遍歷的含義 非線性的樹 線性化的 結(jié)點訪問序列 遍歷 遍歷目的： 二叉樹是非線性結(jié)構(gòu)，每個結(jié)點有兩個后繼，遍歷時存在 如何遍歷 的問題，即按什么樣的 規(guī)律 (搜索路徑 )訪問結(jié)點 ? 37 對 “ 二叉樹 ” 而言 ， 可以有三條搜索路徑： ? 1． 先上后下 的按層次遍歷； ? 2． 先左 （ 子樹 ） 后右 （ 子樹 ） 的遍歷； ? 3． 先右 （ 子樹 ） 后左 （ 子樹 ） 的遍歷 。 41 中序遍歷（ LDR）操作過程 若二叉樹為空樹，則空操作；否則， （ 1）中序遍歷左子樹； （ 2）訪問根結(jié)點； （ 3）中序遍歷右子樹。 43 A B C D E F G H K 例如： 先序序列： 中序序列： 后序序列： A B C D E F G H K B D C A E H G K F D C B H K G F E A 44 a b c d e f g h i j 又如 : 先序遍歷 : a b d h i e j c f g 中序遍歷 : h d i b j e a f c g 后序遍歷 : h i d j e b f g c a 45 用二叉樹表示表達式 + / a * e f b c d 先序 : +a*bcd/ef 中序 : a+b*cde/f 后序 : abcd*+ef/ 三個序列恰好為它的 前綴、 中綴、 后綴 表示式 原式 :a+b*(cd)e/f 46 三、遍歷算法的遞歸描述 先序遍歷 void PreOrder(BiTree root) /*先序遍歷二叉樹 , root為二叉樹根結(jié)點的指針 */ { if (root!=NULL) {Visit(root data)。 /*先序遍歷左子樹 */ PreOrder(root RChild)。 /*中序遍歷左子樹 */ Visit(root data)。 /*中序遍歷右子樹 */ } } 中序遍歷 48 后序遍歷 void PostOrder(BiTree root) /* 后序遍歷二叉樹 ， root為二叉樹根結(jié)點的指針 */ {if(root!=NULL) { PostOrder(root LChild)。 /*后序遍歷右子樹 */ Visit(root data)。 2. 輸出二叉樹的左子樹 。 52 void Preorder (BiTree root) { if (root!=NULL) { printf(“%c”,rootdata)。 Preorder(rootrchild)。 53 輸出二叉樹中的葉子結(jié)點 void PreOrder(BiTree root) /* 先序遍歷輸出二叉樹中葉結(jié)點 , root為二叉樹根結(jié)點的指針 */ { if (root!=NULL) {if (root LChild==NULL amp。 root RChild==NULL) printf (root data)。 /* 先序遍歷左子樹 */ PreOrder(root RChild)。 由此， 需在遍歷算法中增添一個“計數(shù)”的參數(shù)， 并將算法中“訪問結(jié)點” 的操作改為 :若是葉子，則計數(shù)器增 1。 leaf(rootRChild)。amp。 } } 方法一：設(shè)全局變量 LeafCount計葉子結(jié)點數(shù)目， 調(diào)用前賦初值為 0 56 方法二：空樹：返回 0；葉子結(jié)點，返回 1； 否則為左右子樹的葉子結(jié)點數(shù)之和 。 if (root==NULL) LeafCount = 0。amp。 else {L= leaf(rootLChild)。 LeafCount=L+R。 } 57 求二叉樹的深度 算法基本思想 : 從二叉樹深度的定義可知， 二叉樹的深度應(yīng)為其左、右子樹深度的最大值加 1。 首先分析 二叉樹的深度 和它的 左 、 右子樹深度 之間的關(guān)系。 else { depthLeft = Depth( Tlchild )。 depthval = 1 + (depthLeft depthRight ? depthLeft : depthRight)。 } 59 五、由遍歷序列確定二叉樹 在對一棵二叉樹進行遍歷，只要遍歷的策略已確定，就可以得到一個唯一的結(jié)點序列。假如 在遍歷二叉樹時，我們使用某個特定的符號表示空子樹，則稱得到的序列為擴展的結(jié)點序列 。 64 BiTree CreateBiTree() { char ch。 ch=getchar()。 else { p=(BiTreeNode *) malloc(sizeof(BiTreeNode))。 pLChild=CreateBiTree()。 return (p)。但是，給定結(jié)點的遍歷序列，卻不能唯一確定一棵二叉樹！ ? 由遍歷序列確定二叉樹 二叉樹的先序序列 二叉樹的中序序列 左子樹 左子樹 右子樹 右子樹 根 根 那么，給定一棵二叉樹結(jié)點的先序序列和中序序列，能否唯一確定一棵二叉樹呢？ 66 二叉樹先序遍歷是先訪問根結(jié)點 D,即 第一結(jié)