【導(dǎo)讀】集合是成員的一個(gè)群集。集合的成員必須互不相同。在算法與數(shù)據(jù)結(jié)構(gòu)中所遇到的集合，其。name={“An”,“Cao”,“Liu”,“Ma”,集合中的成員一般是無序的，但在表示。常設(shè)定集合中的單元素具有線性有序關(guān)。整數(shù)、字符和字符串都有一個(gè)自然線性。指針也可依據(jù)其在序列中安排的。位置給予一個(gè)線性順序。當(dāng)集合是全集合{0,1,2,…當(dāng)全集合是由有限的可枚舉的成員組成的。集合時(shí)，可建立全集合成員與整數(shù)0,1,的一一對(duì)應(yīng)關(guān)系，用位向量來表示該。s3=s1+s2;//求s1與s2的并{0,1,…

　　

【正文】 ) / 2。 if ( Element[mid].key x ) mid = BinarySearch ( x, mid +1, high )。 else if ( Element[mid].key x ) mid = BinarySearch ( x, low, mid 1 )。 } return mid。 } templateclass Type int orderedList Type:: BinarySearch ( const Type amp。 x ) const { //折半搜索的迭代算法 int high = CurrentSize1, low = 0, mid。 while ( low = high ) { mid = ( low + high ) / 2。 if ( Element[mid].key x ) low = mid + 1。 //右縮搜索區(qū)間 else if ( Element[mid].key x ) high = mid 1。 //左縮搜索區(qū)間 else return mid。 //搜索成功 } return 1。 //搜索失敗 } 有序順序表的折半搜索的判定樹 ( 10, 20, 30, 40, 50, 60 ) 10 50 = = = = = = 30 20 40 60 ASLunsucc = (2*1+3*6)/7 = 20/7 ASLsucc = (1+2*2+ 3*3)/6 = 14/6 ? 搜索成功時(shí)檢測(cè)指針停留在樹中某個(gè)結(jié)點(diǎn)。 ? 搜索不成功時(shí)檢測(cè)指針停留在某個(gè)外結(jié)點(diǎn)（失敗結(jié)點(diǎn)）。 35 15 45 50 25 10 20 30 搜索 22 搜索 45 折半搜索性能分析 ? 若設(shè) n = 2h1，則描述折半搜索的判定樹是高度為 h1 的滿二叉樹。 2h = n+1, h = log2(n+1) ? 第 0層結(jié)點(diǎn)有 1個(gè) , 搜索第 0層結(jié)點(diǎn)要比較 1次 。 第 1層結(jié)點(diǎn)有 2個(gè) , 搜索第 1層結(jié)點(diǎn)要比較 2次 。 …, 第 i (0 ≤ i ? h) 層結(jié)點(diǎn)有 2i 個(gè) , 搜索第 i 層結(jié)點(diǎn)要比較 i+1次， … 。 ? 假定每個(gè)結(jié)點(diǎn)的搜索概率相等，即 pi = 1/n，則搜索成功的平均搜索長(zhǎng)度為 121)(221)( 232211 1221???????????????? ??hhhhhh?11)(l o g11)(l o g1 )1)(1 ) l og((11)21)((1 222???????????????nnnnnnnnhnA S Lhs u c c可以用歸納法證明 這樣 定義 二叉搜索樹或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹： ? 每個(gè)結(jié)點(diǎn)都有一個(gè)作為搜索依據(jù)的關(guān)鍵碼 (key)，所有結(jié)點(diǎn)的關(guān)鍵碼互不相同。 ? 左子樹 (如果存在 )上 所有結(jié)點(diǎn)的關(guān)鍵碼都小于根結(jié)點(diǎn)的關(guān)鍵碼 。 ? 右子樹 (如果存在 )上 所有結(jié)點(diǎn)的關(guān)鍵碼都大于根結(jié)點(diǎn)的關(guān)鍵碼 。 ? 左子樹和右子樹也是二叉搜索樹。 二叉搜索樹 ( Binary Search Tree ) 35 15 45 50 40 25 10 20 30 二叉搜索樹例 ? 結(jié)點(diǎn)左子樹上所有關(guān)鍵碼小于結(jié)點(diǎn)關(guān)鍵碼。 ? 右子樹上所有關(guān)鍵碼大于結(jié)點(diǎn)關(guān)鍵碼。 ? 注意：若從根結(jié)點(diǎn)到某個(gè)葉結(jié)點(diǎn)有一條路徑，路徑左邊的結(jié)點(diǎn)的關(guān)鍵碼不一定小于路徑上的結(jié)點(diǎn)的關(guān)鍵碼。 n 個(gè)結(jié)點(diǎn)的二叉搜索樹的數(shù)目 【例】 3 個(gè)結(jié)點(diǎn)的二叉搜索樹 ： 512345641C131 332 ???????? ?1 2 2 1 3 3 1 3 2 1 2 3 1 2 3 {123} {132} {213} {231} {312} {321} 二叉搜索樹的類定義 include template class Type class BST。 template class Type Class BstNode Type : public BinTreeNode { friend class BST Type。 如果對(duì)一棵二叉搜索樹進(jìn)行中序遍歷，可以按從小到大的順序，將各結(jié)點(diǎn)關(guān)鍵碼排列起來，所以也稱二叉搜索樹為二叉排序樹。 protected: Type data。 BstNodeType *leftChild, *rightChild。 }。 public: BstNode ( ) : leftChild (NULL), rightChild (NULL) { } //構(gòu)造函數(shù) BstNode ( const Type d, BstNodeType * L = NULL, BstNodeType *R = NULL) : data (d), leftChild (L), rightChild (R) { } void setData ( Type d ) { data = d。 } Type GetData ( ) { return data。 } ~BstNode ( ) { } //析構(gòu)函數(shù) }。 template class Type class BST : public BinaryTreeType { private: BstNodeType *root。 //根指針 Type RefValue。 //數(shù)據(jù)輸入停止的標(biāo)志 void MakeEmpty ( BstNodeType *amp。 ptr )。 void Insert ( Type x, BstNodeType *amp。 ptr )。 //插入 void Remove ( Type x, BstNodeType *amp。 ptr )。 //刪除 void PrintTree ( BstNodeType * ptr ) const。 BstNodeType *Copy ( const BstNodeType * ptr )。 //復(fù)制 BstNodeType *Find ( Type x, BstNodeType * ptr )。 //搜索 BstNodeType *Min ( BstNodeType * ptr ) const。 //求最小 BstNodeType *Max ( BstNodeType * ptr ) const。 //求最大 public: BST ( ) : root (NULL) { } //構(gòu)造函數(shù) BST ( Type value )。 //構(gòu)造函數(shù) ~BST ( )。 //析構(gòu)函數(shù) const BSTamp。 operator = ( const BSTamp。 Value )。 void MakeEmpty ( ) { MakeEmpty ( root )。 root = NULL。 } void PrintTree ( ) const { PrintTree ( root )。 } int Find ( Type x ) //搜索元素 { return Find ( x, root ) != NULL。 } Type Min ( ) { return Min ( root )data。 } Type Max ( ) { return Max ( root )data。 } void Insert ( Type x ) { Insert ( x, root )。 } //插入新元素 void Remove ( Type x ) { Remove ( x, root )。 } //刪除含 x的結(jié)點(diǎn) } 在二叉搜索樹上進(jìn)行搜索，是一個(gè) 從根結(jié)點(diǎn)開始，沿某一個(gè)分支逐層向下進(jìn)行比較判等 的過程。它可以是一個(gè)遞歸的過程。 二叉搜索樹上的搜索 ? 假設(shè)想要在二叉搜索樹中搜索關(guān)鍵碼為 x的元素 ， 搜索過程從根結(jié)點(diǎn)開始 。 ? 如果根指針為 NULL， 則搜索不成功；否則用給定值 x與根結(jié)點(diǎn)的關(guān)鍵碼進(jìn)行比較： ? 如果給定值等于根結(jié)點(diǎn)的關(guān)鍵碼 ， 則搜索成功 。 ? 如果給定值小于根結(jié)點(diǎn)的關(guān)鍵碼 ， 則繼續(xù)遞歸搜索根結(jié)點(diǎn)的左子樹； ? 否則 。 遞歸搜索根結(jié)點(diǎn)的右子樹 。 35 15 45 50 40 25 10 20 30 搜索 45 搜索成功 搜索 28 搜索失敗 template class Type BstNodeType * BSTType :: Find ( Type x, BstNodeType * ptr ) const { //二叉搜索樹的遞歸的搜索算法 if ( ptr == NULL ) return NULL。 //搜索失敗 else if ( x ptrdata ) //在左子樹搜索 return Find ( x, ptrleftChild )。 else if ( x ptrdata ) //在右子樹搜索 return Find ( x, ptrrightChild )。 else return ptr。 //相等 ,搜索成功 } template class Type BstNode Type * BST Type :: Find ( Type x, BstNodeType * ptr ) const { //二叉搜索樹的迭代的搜索算法 if ( ptr != NULL ) { BstNodeType * temp = ptr。 //從根搜索 while ( temp != NULL ) { if ( tempdata == x ) return temp。 if ( tempdata x ) temp = temprightChild。 //右子樹 else temp = templeftChild。 //左子樹 } } return NULL。 //搜索失敗 } 二叉搜索樹的插入 35 15 45 50 40 25 10 20 30 28 每次結(jié)點(diǎn)的插入，都要從根結(jié)點(diǎn)出發(fā)搜索插入位置，然后把新結(jié)點(diǎn)作為 葉結(jié)點(diǎn) 插入。 插入新結(jié)點(diǎn) 28 ? 為了向二叉搜索樹中插入一個(gè)新元素 ， 必須先檢查這個(gè) 元素是否在樹中已經(jīng)存在 。 ? 在插入之前 ， 先使用搜索算法在樹中檢查要插入元素有還是沒有 。 ? 搜索成功 : 樹中已有這個(gè)元素 ,不再插入 。 ? 搜索不成功 : 樹中原來沒有關(guān)鍵碼等于給定值的結(jié)點(diǎn) ， 把新元素加到搜索操作停止的地方 。 遞歸的二叉搜索樹插入算法 template class Type void BSTType :: Insert ( Type x, BstNodeType * amp。 ptr) { if ( ptr == NULL ) {