【正文】 mp。 swap(Heap, pos, j)。 if(rcn)amp。 i) siftdown(i)。} bool remove(int, Elemamp。amp。 )。 buildHeap()。 //堆當(dāng)前元素個數(shù) int size。 } BST中 removehelp函數(shù)的實現(xiàn) 思考： ? BST樹平衡性如何？？能不能保證平衡？ 54 55 AVL樹 一、 AVL樹（高度平衡的 BST）概念 定義 ——AVL或是空樹，或是具有下列性質(zhì)的 BST： 它的左、右子樹都是 AVL樹，且左右子樹的高度之差的絕對值不超過 1。 Elem te=subrooval()。 t=subroot。t) { if(subroot==NULL) return NULL。} else {subrootSetLeft(deletemin(subrootleft(),min))。 // Return subtree with node inserted return subroot。 } ?一般對尾遞歸或單向遞歸的情形，都可利用迭代方法，不使用棧將遞歸過程改為非遞歸過程 二、 BST上的搜索 48 三、 BST中的插入 方法 ?先搜索 BST中有無該結(jié)點，只有無才插入 ?插入是作為葉子插入，插入后仍滿足 BST ?插入位置應(yīng)是搜索操作停止（指針 ptr為空）的地方 算法 template class Key, class Elem, class KEComp, class EEComp BinNodeElem* BSTKey,Elem,KEComp,EEComp:: inserthelp(BinNodeElem* subroot, const Elemamp。 return true。} } ?該算法的遞歸調(diào)用語句都于程序的最尾，稱為尾遞歸 ?返回時返回到上一層調(diào)用處的下條語句去執(zhí)行 ?因為是最尾語句，程序結(jié)束，不必用棧保存返回地址和局部變量的值 ?該算法可以不用棧，采用迭代方法改寫成非遞歸程序 二、 BST上的搜索 47 迭代算法 template class Key, class Elem, class KEComp, class EEComp bool BSTKey,Elem,KEComp,EEComp:: findHelp (BinTreeNodeElem*subroot, constKey amp。 else if (KEComp::lt(K,subrootval())) return findHelp (subrootleft(),K,e)。 } }。 e) const {return findhelp(root, K,e)。 nodecount。 e){ if(root==NULL) return false。 nodecount。K, Elemamp。 e) {root=inserthelp(root,e)。} void clear(){clearhelp(root)。 void printhelp(BinTreeNodeElem* ,int) const。 BinTreeNodeELem* removehelp(BinTreeNodeElem*, const Keyamp。 BinTreeNodeElem* inserthelp(BinTreeNodeElem*,const Elemamp。 53 65 81 87 09 45 23 17 78 94 41 一、基本概念 BST是基于二叉樹的動態(tài)搜索結(jié)構(gòu)，其刪除和插入結(jié)點可能要改變樹的結(jié)構(gòu)。 //從第一個結(jié)點開始沿著后繼方向遍歷二叉樹 ……} 40 二叉搜索樹（ Binary Search Tree） 一、基本概念 定義 ——或是空、或是具有下列性質(zhì)的二叉樹： ?每個結(jié)點有一個作為搜索依據(jù)的關(guān)鍵碼（ Key）。 ThreadNodeElem *Last(ThreadNodeElem * current)。}} 39 template class Elem class ThreadTree { private : ThreadNode Elem *root。 private: int leftThread, rightThread。 ◆ 中序遍歷線索二叉樹結(jié)構(gòu)示例 ◆ 若根的左子樹不空，則其最左下角的結(jié)點為中序遍歷的第一個結(jié)點，否則根為中序遍歷的第一個結(jié)點。各只占一個二進(jìn)制位，只增加很少的額外空間開銷。 if (p rightChild != NULL) (p rightChild)。 BinTreeNode Elem *p = root。} if ( St. length()!=0) {st. pop (p )。 BinTreeNode Elem *p = root。 } } 二、 TBT的遞歸算法 － ＋ / ＊ － a b c d e f 對表達(dá)式 a+b*(cd)e/f 的語法樹進(jìn)行后序遍歷得到其后綴表示： a b c d – * + e f / – 29 二、 TBT的遞歸算法 TBT遞歸算法的簡化 traversal (BinTreeNode Elem *current) { if (current != NULL) { traversal (current leftChild)。 PreOrder (current rightChild)。 //中序遍歷左子樹 cout current data。 ◆ ―訪問”包括輸出結(jié)點值，修改值，統(tǒng)計等以不破壞BT的結(jié)構(gòu)為原則。 216。 216。} ~BinTreeNode(){} 鏈?zhǔn)酱鎯Φ奶攸c ? 動態(tài)建立，靈活性高 ? 結(jié)構(gòu)性開銷大 19 20 使用數(shù)組實現(xiàn) a b c d e f g h i j k l A B C D E F G H I J K L 1 2 3 4 5 6 7 8 9 10 11 12 21 一般二叉樹 A B C D E F G 216。 //右子結(jié)點指針域 public: BinTreeNode(){lchild=rchild=NULL。 template class Elem class BinTreeNode { firend class BinaryTreeElem。 //返回右結(jié)點的指針 virtual void setLeft(BinNode*)=0。 。 [i/2] i i+1 2i 2i+1 2(i+1) 2i+3 [i+1/2] i+1 2(i+1) 2i+3 i 2i 2i+1 圖 完全二叉樹中結(jié)點 I和 i+1 (a)I和 i+1結(jié)點在同一層 (b)I和 i+1結(jié)點不在同一層 二叉樹的實現(xiàn) ? 二叉樹抽象數(shù)據(jù)類型 ? 使用指針實現(xiàn) ? 使用數(shù)組實現(xiàn) 15 16 二叉樹結(jié)點的 ADT template class Elem class BinNode{ public: virtual Elemamp。 特點 ◆ 每個結(jié)點最多只有兩個孩子結(jié)點，即結(jié)點的度不大于 2。第五章 二叉樹 主要內(nèi)容 ? 定義與主要特性 ? 二叉樹的實現(xiàn) ? 遍歷二叉樹及線索化 ? 二叉搜索樹 ? AVL樹 ? 堆 ? 霍夫曼編碼樹 2 定義與特性 ? 定義和術(shù)語 ? 二叉樹的性質(zhì) 3 一、樹的定義 5 定義：樹 (Tree)是 n(n=0)個結(jié)點的有限集 T， T為空時稱為空樹，否則它滿足如下兩個條件： （ 1）有且僅有一個特定的稱為根 (Root)的結(jié)點； （ 2）其余的結(jié)點可分為 m(m=0)個互不相交的子集T1,T2,T3… Tm，其中每個子集又是一棵樹，并稱其為子樹(Subtree) ? 這是一個 遞歸 定義。二叉樹可以是空集合，根可以有空的左子樹或空的右子樹 三、相關(guān)術(shù)語 7 ? 結(jié)點的度 ? 樹的度 ? 葉結(jié)點 ? 分支結(jié)點 ? 左孩子、右孩子、雙親 ? 路徑、路徑長度 ? 祖先、子孫 ? 結(jié)點的深度 ? 樹的高度 9 9 一、二叉樹的定義和特點 定義：二叉樹是有限個結(jié)點的集合，它或者是空，或者是由一個根結(jié)點加上兩棵分別稱為左子樹和右子樹、互不相交的二叉樹組成。 2 4 5 3 6 7 1 圖 滿二叉樹 三、滿二叉樹 12 1 2 3 4 5 6 1 2 3 4 5 7 1 2 3 6 7 (a)完全二叉樹 (b)非完全二叉樹 ( c)非完全二叉樹 圖 完全二叉樹 四、完全二叉樹 一棵高度為 d的二叉樹除了 d1層以外每一層都是滿的，并且每一層都是從左到右填充 13 定理 1：非空滿二叉樹的葉結(jié)點數(shù)等于其分支結(jié)點數(shù)加 1 四、滿二叉樹定理 定理 2：一棵非空二叉樹空子樹的數(shù)目等于其結(jié)點數(shù)目加 1 14 如圖 左右孩子結(jié)點之間的關(guān)系。)=0。//返回左結(jié)點的指針 virtual BinNode* right()=0。 //判斷是否為葉結(jié)點 } 16 17 使用指針實現(xiàn) 結(jié)點結(jié)構(gòu)和示例 leftChild data rightChild A B C D E F root A ∧ B ∧ C ∧ D ∧ E ∧ ∧ F ∧ root 18 二叉樹的二