集合及其表示

1、集合運(yùn)算的文氏集合運(yùn)算的文氏(Venn)圖圖Template class Set Set ( int MaxSetSize ) : MaxSize ( MaxSetSize ); void MakeEmpty ( Set &s ); int AddMember ( Set &s, const Type x ); int DelMember ( Set &s, const Type & x ); void Assign ( Set &s1, Set &s2 ); void Union ( Set & s1, Set &s2 ); v

2、oid Intersection ( Set &s1, Set &s2 ); void Difference ( Set & s1, Set &s2 ); int Contains ( Set &s, const Type & x ); int Equal ( Set &s1, Set &s2 ); int SubSet ( Set &s1, Set &s2 );#include const int DefaultSize = 100;class Set private: int * bitVector; int

3、MaxSize;public: Set ( int MaxSetSize = DefaultSize ); Set ( ) delete bitVector; void MakeEmpty ( ) for ( int i = 0; i 0 ); bitVector = new int MaxSize; assert ( bitVector != 0 ); for ( int i = 0; i = 0 & x = 0 & x MaxSize ); if ( bitVectorx ) bitVectorx = 0; return 1; return 0;void Set:opera

4、tor = ( Set & right ) assert ( MaxSize = right.MaxSize ); for ( int i =0; i = 0 & x MaxSize ); if ( bitVectorx ) bitVectorx = 0; return 1; return 0;void Set:operator = ( Set & right ) assert ( MaxSize = right.MaxSize ); for ( int i = 0; i MaxSize; i+ ) bitVectori = right.bitVectori;void

5、Set:operator + (Set & right ) assert ( MaxSize = right.MaxSize ); for ( int i = 0; i MaxSize; i+ ) bitVectori = bitVectori | right.bitVectori;void Set:operator * (Set & right ) assert ( MaxSize = right.MaxSize ); for ( int i = 0; i MaxSize; i+) bitVectori = bitVectori & right.bitVectori;

6、void Set:operator - ( Set & right ) assert ( MaxSize = right.MaxSize ); for ( int i = 0; i = 0 & x MaxSize ); return bitVectorx;int Set:operator = ( Set & right ) assert ( MaxSize = right.MaxSize ); for ( int i = 0; i MaxSize; i+) if ( bitVectori != right.bitVectori ) return 0; return 1;

7、int Set:SubSet (Set & right ) assert ( MaxSize = right.MaxSize ); for ( int i = 0; i MaxSize; i+) if (bitVectori & ! right.bitVectori) return 0; return 1;用帶表頭結(jié)點(diǎn)的有序鏈表表示集合用帶表頭結(jié)點(diǎn)的有序鏈表表示集合template class SetList;template class SetNode friend class SetList;public: SetNode (const Type & item )

8、: data (item), link (NULL);private: Type data; SetNode *link;template class SetList private: SetNode *first, *last;public: SetList ( ); void MakeEmpty ( ); int AddMember ( const Type & x ); int DelMember ( const Type & x ); void operator = ( SetList & right ); void operator + ( SetList &

9、amp; right ); void operator * ( SetList & right ); void operator - ( SetList & right ); int Contains ( const Type & x ); int operator = ( SetList & right ); Type & Min ( ); Type & Max ( );template int SetList: Contains (const Type & x ) SetNode *temp = firstlink; while (

10、temp != NULL & tempdata x ) temp = templink; if (temp != NULL & tempdata = x) return 1; else return 0;template void SetList:SetList ( ) SetNode *first = *last = new SetNode(0); firstlink = NULL;template int SetList: AddMember ( const Type & x ) SetNode *p = firstlink, *q = first; while (

11、 p != NULL & pdata x ) q = p; p = plink; if ( p != NULL & pdata = x ) return 0; SetNode *s = new SetNode (x); slink = p; qlink = s; if ( p = NULL ) last = s; return 1;template int SetList :DelMember ( const Type & x ) SetNode *p = firstlink, *q = first; while ( p != NULL & pdata x )

12、q = p; p = plink; if ( p != NULL & pdata = x ) qlink = plink; if ( p = last ) last = q; delete p; return 1; else return 0;template void SetList: operator = ( SetList & right ) SetNode*pb = right.firstlink; SetNode*pa = first = new SetNode; while ( pb != NULL ) palink = new SetNode (pbdata);

13、pa = palink; pb = pblink; palink = NULL; last = pa;template void SetList: operator + ( SetList & right ) SetNode *pb = right.firstlink; SetNode *pa = firstlink; SetNode *pc = first; while ( pa != NULL & pb != NULL ) if ( padata = pbdata ) pclink = pa; pa = palink; pb = pblink; else if ( pada

14、ta pbdata ) pclink = pa; pa = palink; else pclink = new SetNode (pbdata); pb = pblink; pc = pclink; if ( pa != NULL ) pclink = pa; else while ( pb != NULL ) pclink = new SetNode (pbdata); pc = pclink; pb = pblink; pclink = NULL; last = pc; template void SetList: operator * ( SetList & right ) Se

15、tNode *pb = right.firstlink; SetNode *pa = firstlink; SetNode *pc = first; while ( pa != NULL & pb != NULL ) if ( padata = pbdata ) pc = pclink; pa = palink; pb = pblink; else if ( padata pbdata ) pclink = palink; delete pa; pa = pclink; else pb = pblink; while ( pa != NULL ) pclink = palink; de

16、lete pa; pa = pclink; last = pc;template void SetList: operator - ( SetList & right ) SetNode *pb = right.firstlink; SetNode *pa = firstlink; SetNode *pc = first; while ( pa != NULL & pb != NULL ) if ( padata = pbdata ) pclink = palink; delete pa; pa = pclink; pb = pblink; else if ( padata p

17、bdata ) pc = pclink; pa = palink; else pb = pblink; if ( pa = NULL ) last = pc;template int SetList: operator = ( SetList & right ) SetNode *pb = right.firstlink; SetNode *pa = firstlink; while ( pa != NULL & pb != NULL ) if ( padata = pbdata ) pa = palink; pb = pblink; else return 0; if ( p

18、a != NULL | pb != NULL ) return 0; return 1; n void equivalence ( ) 初始化初始化; while 等價(jià)對(duì)未處理完等價(jià)對(duì)未處理完 讀入下一個(gè)等價(jià)對(duì)讀入下一個(gè)等價(jià)對(duì) ( i, j ); 存儲(chǔ)這個(gè)等價(jià)對(duì)存儲(chǔ)這個(gè)等價(jià)對(duì) ; 輸出初始化輸出初始化; for ( 尚未輸出的每個(gè)對(duì)象尚未輸出的每個(gè)對(duì)象 ) 輸出包含這個(gè)對(duì)象的等價(jià)類輸出包含這個(gè)對(duì)象的等價(jià)類 ; 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 0, 4, 1, 2, 3, 5, 6, 7, 8, 9, 10, 11 0, 4, 1, 3, 2, 5, 6

19、, 7, 8, 9, 10, 110, 4, 1, 3, 2, 5, 6, 10, 7, 8, 9, 11 0, 4, 1, 3, 2, 5, 6, 10, 7, 8, 9, 11 0, 4, 7, 1, 3, 2, 5, 6, 10, 8, 9, 11 0, 4, 7, 1, 3, 2, 5, 6, 8, 9, 10, 11 0, 4, 7, 1, 3, 5, 2, 6, 8, 9, 10, 110, 4, 7, 1, 3, 5, 2, 11, 6, 8, 9, 100, 2, 4, 7, 11, 1, 3, 5, 6, 8, 9, 10void equivalence ( ) 讀入讀入 n

20、; 將將 seq 初始化為初始化為 0 且將且將 out 初始化為初始化為 False; while等價(jià)對(duì)未處理完等價(jià)對(duì)未處理完 讀入下一個(gè)等價(jià)對(duì)讀入下一個(gè)等價(jià)對(duì)( i, j ); 將將 j 鏈入鏈入 seqi鏈表鏈表; 將將 i 鏈入鏈入 seqj鏈表鏈表; for ( i = 0; i n; i+ ) /檢測(cè)所有對(duì)象檢測(cè)所有對(duì)象 if ( outi = False ) /若對(duì)象若對(duì)象i未輸出未輸出 outi = True; /對(duì)象對(duì)象i做輸出標(biāo)志做輸出標(biāo)志 輸出包含對(duì)象輸出包含對(duì)象 i 的等價(jià)類的等價(jià)類; 鏈鏈序序號(hào)號(hào)等等價(jià)價(jià) 對(duì)對(duì)OUT初初態(tài)態(tài)輸輸出出OUT終終態(tài)態(tài) 棧棧 0False

21、0 True 0 11 False 11 True 11 0 4 False 4 True 11,4 4 7 False 7 True 11,7 4 0 True True 11,7 鏈鏈序序號(hào)號(hào)等等價(jià)價(jià) 對(duì)對(duì)OUT初初態(tài)態(tài)輸輸出出OUT終終態(tài)態(tài)棧棧 7 4 True True 11 11 0 True True 11 0 True True 11 2 False 2 True 2 2 11 True Trueenum Boolean False, True ;class ListNode /定義鏈表結(jié)點(diǎn)類定義鏈表結(jié)點(diǎn)類friend void equivalence ( );private:

22、int data;/結(jié)點(diǎn)數(shù)據(jù)結(jié)點(diǎn)數(shù)據(jù) ListNode *link;/結(jié)點(diǎn)鏈指針結(jié)點(diǎn)鏈指針 ListNode ( int d ) data = d; link = NULL; ;typedef ListNode *ListNodePtr;void equivalence ( ) ifstream inFile ( equiv.in, ios:in ); /輸入文件輸入文件 if ( !inFile ) cout “不能打開(kāi)輸入文件不能打開(kāi)輸入文件 n; /讀入對(duì)象個(gè)數(shù)讀入對(duì)象個(gè)數(shù) seq = new ListNodePtrn; out = new Booleann; /初始化初始化seq和和o

23、ut for (i = 0; i i j; /輸入等價(jià)對(duì)輸入等價(jià)對(duì) ( i, j ) while ( inFile.good ( ) ) /輸入文件結(jié)束轉(zhuǎn)出循環(huán)輸入文件結(jié)束轉(zhuǎn)出循環(huán) x = new ListNode ( j ); /創(chuàng)建結(jié)點(diǎn)創(chuàng)建結(jié)點(diǎn) j xlink = seqi; seqi = x; /鏈入第鏈入第i個(gè)鏈表個(gè)鏈表 y = new ListNode ( i ); /創(chuàng)建結(jié)點(diǎn)創(chuàng)建結(jié)點(diǎn)i ylink = seqj; seqj = y; /鏈入第鏈入第j個(gè)鏈表個(gè)鏈表 inFile i j;/輸入下一個(gè)等價(jià)對(duì)輸入下一個(gè)等價(jià)對(duì) for ( i =0; i n; i+ ) if ( outi

24、 = False ) /未輸出未輸出, , 需要輸出需要輸出 cout endl “A new class: ” i; /輸出輸出 outi = True;/作輸出標(biāo)記作輸出標(biāo)記 ListNode *x = seqi; /取第取第i鏈表頭指針鏈表頭指針 ListNode *top = NULL; /棧初始化棧初始化 while (1) /找類的其它成員找類的其它成員 while ( x ) /處理鏈表處理鏈表,直到直到 x=0 j = xdata; /成員成員j if ( outj = False ) /未輸出未輸出, , 輸出輸出 cout “,” j; outj=True; ListNod

25、e *y = xlink; xlink = top; top = x; /結(jié)點(diǎn)結(jié)點(diǎn)x進(jìn)棧進(jìn)棧 x = y;/x進(jìn)到鏈表下一個(gè)結(jié)點(diǎn)進(jìn)到鏈表下一個(gè)結(jié)點(diǎn) else x = xlink; /已輸出過(guò)已輸出過(guò), ,跳過(guò)跳過(guò) if ( top = NULL ) break; /?？胀顺鲅h(huán)?？胀顺鲅h(huán) else x = seqtopdata; top = toplink; /棧不空棧不空, , 退棧退棧, , x是根據(jù)結(jié)點(diǎn)編號(hào)回是根據(jù)結(jié)點(diǎn)編號(hào)回 /溯的另一個(gè)鏈表的頭指針?biāo)莸牧硪粋€(gè)鏈表的頭指針 delete seq; delete out; ； 。parent- -1 4 - -1 2 - -1 2 0 0

26、 0 40 1 2 3 4 5 6 7 8 9const int DefaultSize = 10;class UFSets /public: UFSets ( int s = DefaultSize ); UFSets ( ) delete parent; const UFSets & operator = ( UFSets const & Value ); void Union ( int Root1, int Root2 ); int Find ( int x ); void UnionByHeight ( int Root1, int Root2 );private:

27、int *parent; int size;UFSets:UFSets ( int s ) / size = s; parent = new int size; for ( int i = 0; i = size; i+ ) parenti = -1;unsigned int UFSets:Find ( int x ) /搜索操作搜索操作 if ( parentx = 0 ) return x; else return Find ( parentx );void UFSets:Union ( int Root1, int Root2 ) /并并 parentRoot2 = Root1; /Ro

28、ot2指向指向Root1nini12OO)()(parent0(= - -4) parent4 (= - -3)void UFSets:WeightedUnion(int Root1, int Root2) Unionint temp = parentRoot1 + parentRoot2; if ( parentRoot2 = 0; j = parentj); /讓讓 j 循雙親指針走到根循雙親指針走到根 while ( i != j ) /換換 parenti 到到 j int temp = parenti; parenti = j; i = temp; return j;template

29、 class dataList; template class Node friend class dataList;public: Node ( const Type & value ) : key ( value ) Type getKey ( ) const return key; void setKey ( Type k ) key = k; private: Type key; other;template class dataList public: dataList ( int sz = 10 ) : ArraySize (sz), Element (new Node s

30、z) virtual dataList ( ) delete Element; friend ostream &operator (ostream & OutStream, const dataList & OutList ); friend istream & operator ( istream & InStream, dataList & InList );protected: Type *Element; int ArraySize, CurrentSize;template class searchList : public dataL

31、ist /作為派生類的靜態(tài)搜索表的類定義作為派生類的靜態(tài)搜索表的類定義public: searchList ( int sz = 10 ) : dataList (sz) virtual searchList ( ) virtual int Search ( const Type & x ) const;template istream & operator ( istream & InStream, dataList & InList ) /從輸入流對(duì)象從輸入流對(duì)象InStream輸入數(shù)據(jù)到數(shù)據(jù)表輸入數(shù)據(jù)到數(shù)據(jù)表InList cout InList.Curre

32、ntSize; cout “輸入數(shù)組元素值輸入數(shù)組元素值 : n”; for ( int i = 0; i InList.CurrentSize; i+ ) cout “元素元素 ” i InList.Elementi; return InStream;template ostream & operator ( ostream & OutStream, const dataList & OutList ) /將數(shù)據(jù)表將數(shù)據(jù)表OutList內(nèi)容輸出到輸出流對(duì)象內(nèi)容輸出到輸出流對(duì)象OutStream OutStream “數(shù)組內(nèi)容數(shù)組內(nèi)容 : n”; for ( int i

33、 = 0; i OutList.CurrentSize; i+ ) OutStream OutList.Elementi ; OutStream endl; OutStream “數(shù)組當(dāng)前大小數(shù)組當(dāng)前大小 : ” OutList.CurrentSize endl; return OutStream;template int searchList:Search ( const Type & x ) const /順序搜索的迭代算法，順序搜索的迭代算法，0號(hào)元素為監(jiān)視哨號(hào)元素為監(jiān)視哨 ElementCurrentSize.setKey ( x ); int i = 0; while (El

34、ementi.getKey ( ) != x ) i +; return i;template int earchList :Search ( const Type & x, int & loc ) const /順序搜索的遞歸算法順序搜索的遞歸算法 if ( loc CurrentSize ) return -1; else if ( Elementloc.getKey( ) = x ) return loc; else return Search ( x, loc+1 );const int Size = 10;main ( ) /順序搜索的主過(guò)程順序搜索的主過(guò)程searc

35、hList List1 (Size); float Target; int Location; cin List1; cout List1; /輸入輸入/ /輸出數(shù)據(jù)表輸出數(shù)據(jù)表List1 cout Target; if ( ( Location = List1.search (Target ) ) != 0 ) cout “ 找到下標(biāo)找到下標(biāo) ” Location endl; else cout “ 沒(méi)有找到?jīng)]有找到.n”; 1010niiniiisuccpcpASL) 1 ( .)(110ipASLniisucc.)()(102121111nisuccnnnninASL搜索成功的例子搜索成

36、功的例子 搜索失敗的例子搜索失敗的例子template class orderedList : public dataList /有序表的類定義有序表的類定義,繼承了數(shù)據(jù)表繼承了數(shù)據(jù)表public: orderedList (int sz = 10) : dataList (sz) virtual orderedList ( ) virtual int Search ( const Type & x ) const; template int orderedList:BinarySearch ( const Type & x, const int low, const int

37、high ) const /對(duì)分搜索的遞歸算法對(duì)分搜索的遞歸算法 int mid = -1; if ( low = high ) mid = ( low + high ) / 2; if ( Elementmid.getKey( ) x ) mid = BinarySearch ( x, low, mid -1 ); return mid;template in orderedList : BinarySearch ( const Type & x ) const /對(duì)分搜索的迭代算法對(duì)分搜索的迭代算法 int high = CurrentSize-1, low = 0, mid; w

38、hile ( low = high ) mid = ( low + high ) / 2; if ( Elementmiddle.getKey ( ) x ) high = mid - 1; else return mid; return -1;搜索成功的情形搜索成功的情形 搜索不成功的情形搜索不成功的情形)22)1( 23 2211 (1112211010hhniiniiisucchhnCnCPASL12) 1(22) 1( 2322111221hhhhhh1) 1(log1) 1(log1 ) 1(log) 1(1) 12) 1(1 222nnnnnnnnhnASLhsucc定義定義 #i

39、nclude template class BST;幾個(gè)二叉搜索樹(shù)的例子幾個(gè)二叉搜索樹(shù)的例子template Class BstNode : public BinTreeNode /二叉搜索樹(shù)結(jié)點(diǎn)類二叉搜索樹(shù)結(jié)點(diǎn)類friend class BST;public: BstNode ( ) : leftChild (NULL), rightChild (NULL) BstNode ( const Type d ) : data (d), leftChild (NULL), rightChild (NULL) BstNode ( const Type d=0, BstNode *L=NULL, Bs

40、tNode *R =NULL) : data (d), leftChild (L), rightChild (R) BstNode ( ) protected: Type data; BstNode *leftChild, *rightChild; ;template class BST : BinaryTree private: BstNode *root; /二叉搜索樹(shù)的根指針二叉搜索樹(shù)的根指針 Type RefValue; /數(shù)據(jù)輸入停止的標(biāo)志數(shù)據(jù)輸入停止的標(biāo)志 BstNode *lastfound; /最近搜索到的結(jié)點(diǎn)的指針最近搜索到的結(jié)點(diǎn)的指針 void MakeEmpty ( Bs

41、tNode *& ptr ); void Insert ( const Type & x, BstNode *& ptr ); /插入插入 void Remove ( const Type & x, BstNode *& ptr ); /刪除刪除 void PrintTree ( BstNode *ptr ) const; BstNode *Copy (const BstNode *ptr ); /復(fù)制復(fù)制 BstNode *Find (const Type & x, BstNode * ptr ) const; /搜索搜索 BstNode *M

42、in ( BstNode * ptr ) const; /求最小求最小 BstNode *Max ( BstNode * ptr ) const; /求最大求最大 friend class BSTIterator; /中序游標(biāo)類中序游標(biāo)類public: BST ( ) : root (NULL) BST ( Type value ) : RefValue (value), root (NULL) BST ( ) MakeEmpty ( root ); const BST & operator = ( const BST & Value ); void MakeEmpty ( )

43、 MakeEmpty (root); root=NULL; void PrintTree ( ) const PrintTree ( root ); int Find ( const Type & x ) const return Find ( x, root ) = NULL; Type Min ( ); Type Max ( ); void Insert (const Type & x ) Insert ( x, root ); void Remove (const Type & x ) Remove ( x, root ); template BstNode *B

44、ST:Find (const Type & x, BstNode * ptr ) const /二叉搜索樹(shù)的遞歸的搜索算法二叉搜索樹(shù)的遞歸的搜索算法 if ( ptr = NULL ) return NULL; /搜索失敗搜索失敗 else if ( x ptrdata ) /在右子樹(shù)遞歸搜索在右子樹(shù)遞歸搜索 return Find ( x, ptrrightChild ); else return ptr; /相等相等, ,搜索成功搜索成功template BstNode *BST : Find (const Type & x, BstNode * ptr ) const /

45、二叉搜索樹(shù)的迭代的搜索算法二叉搜索樹(shù)的迭代的搜索算法 if ( ptr != NULL ) Node * temp = ptr; while ( temp != NULL ) if ( tempdata = x ) return temp; /成功成功 if ( tempdata x ) temp = temprightChild; /右子樹(shù)右子樹(shù) else temp = templeftChild; /左子樹(shù)左子樹(shù) return NULL; /搜索失敗搜索失敗 二叉搜索樹(shù)的搜索二叉搜索樹(shù)的搜索 插入新結(jié)點(diǎn)插入新結(jié)點(diǎn)88template void BST:Insert (const Type

46、& x, BstNode * & ptr) /遞歸的二叉搜索樹(shù)插入算法遞歸的二叉搜索樹(shù)插入算法 if ( ptr = NULL ) /空二叉樹(shù)空二叉樹(shù) ptr = new BstNode (x); /創(chuàng)建含創(chuàng)建含x的結(jié)點(diǎn)的結(jié)點(diǎn) if ( ptr = NULL ) cout Out of space endl; exit (1); else if ( x ptrdata ) /在右子樹(shù)插入在右子樹(shù)插入 Insert ( x, ptrrightChild ); template BST:BST ( Type value ) /輸入數(shù)據(jù)，建立二叉搜索樹(shù)的算法輸入數(shù)據(jù)，建立二叉搜索樹(shù)的

47、算法, RefValue是是/輸入結(jié)束標(biāo)志輸入結(jié)束標(biāo)志 Type &x; root = NULL; RefValue = value; cin x; while ( x.key != RefValue ) Insert ( x, root ); cin x; 二叉搜索樹(shù)的刪除算法二叉搜索樹(shù)的刪除算法template void BST:Remove (const Type &x, BstNode * &ptr) BstNode * temp; if ( ptr != NULL ) if ( x ptdata ) Remove ( x, ptrrightChild ); e

48、lse if ( ptrleftChild != NULL & ptrrightChild != NULL ) temp = Min ( ptrrightChild ); ptrdata = tempdata; Remove ( ptrdata, ptrrightChild ); else temp = ptr; if ( ptrleftChild = NULL ) ptr = ptrrightChild; else if ( ptrrightChild = NULL ) ptr = ptrleftChild; delete temp; template class InorderIt

49、erator public: InorderIterator ( BST & Tree ) : ref (Tree) Init ( ); int Init ( ); /迭代棧初始化迭代棧初始化 int operator ! ( ); /判迭代棧空否判迭代?？辗?Type operator ( ) ( ); /取棧頂元素關(guān)鍵碼取棧頂元素關(guān)鍵碼 int operator + ( ); /按前序序列進(jìn)棧按前序序列進(jìn)棧,遍歷遍歷private: BST & ref; /二叉搜索樹(shù)對(duì)象二叉搜索樹(shù)對(duì)象 Stack BstNode * itrStack; /迭代棧迭代棧與二叉搜索樹(shù)相關(guān)的中序

50、游標(biāo)類與二叉搜索樹(shù)相關(guān)的中序游標(biāo)類template int InorderIterator: Init ( ) itrStack.MakeEmpty ( );/迭代棧置空迭代棧置空 if ( ref.root != NULL ) /樹(shù)非空樹(shù)非空,根進(jìn)棧根進(jìn)棧 itrStack.Push ( ref.root ); return ! itrStack.IsEmpty ( ); /棧空返回?？辗祷?template int InorderIterator:operator ! ( ) return ! itrStack.IsEmpty ( ); /棧空返回?？辗祷?template int Ino

51、rderIterator:operator + ( ) BstNode * current = itrStack.GetTop ( ); BstNode * next = currentleftChild; if ( next != NULL ) /棧頂元素左子女非空棧頂元素左子女非空, 進(jìn)棧進(jìn)棧 itrStack.Push ( next ); return 1; while ( ! itrStack.IsEmpty ( ) ) /棧非空時(shí)循環(huán)棧非空時(shí)循環(huán) current = itrStack.Pop ( ); next = currentrightChild; if ( next != NU

52、LL ) /右子女非空右子女非空 itrStack.Push ( next ); return 1; /進(jìn)棧進(jìn)棧 return 0;template Type InorderIterator:operator ( ) ( ) Node * current = itrStack.GetTop ( ); return currentdata; /返回棧頂元素值返回棧頂元素值template BST:BST (const BST & T) : root (NULL) InorderIterator itr ( Type ); for ( itr.init ( ); ! itr; itr+)

53、Insert ( itr ( ) );template BST:BST ( ) MakeEmpty ( ); /二叉搜索樹(shù)析構(gòu)函數(shù)二叉搜索樹(shù)析構(gòu)函數(shù)Cnnn211(b)(d)(a)(c).(*1p1i liASLnisuccnjunsuccjljASL0q. * ASL = ASLsucc + ASLunsucc ninjji10qp1 .nisucciASL121log.1nniunsucciASL212log njninCjljiliASL010q1p *)(* 關(guān)鍵碼集合關(guān)鍵碼集合 key1 key2 key3 實(shí)實(shí) 例例 do if to 對(duì)應(yīng)對(duì)應(yīng) 內(nèi)部結(jié)點(diǎn)內(nèi)部結(jié)點(diǎn) p1=50 p2=

54、10 p3=5權(quán)值權(quán)值 外部結(jié)點(diǎn)外部結(jié)點(diǎn) q0=15 q1=10 q2=5 q3=5 C 150 190 215 W 100 100 100 R 1 2 3左子樹(shù)左子樹(shù) T0,0 T0,1 T0,2右子樹(shù)右子樹(shù) T1,3 T2,3 T3,30 0 75 115 1501 0 25 502 0 153 00 15 75 90 1001 10 25 352 5 153 5WijCijRij3個(gè)關(guān)鍵碼個(gè)關(guān)鍵碼 do, if, to 的的最優(yōu)二叉搜索樹(shù)最優(yōu)二叉搜索樹(shù)0 1 2 30 1 2 30 1 2 30 0 1 1 11 0 2 22 0 33 0 p1=50, p2=10, p3=5q0=15

55、, q1=10, q2= 5, q3= 5 template class AVLTree public: struct AVLNode Type data; AVLNode *left, *right; int balance; AVLNode ( ) : left (NULL), right (NULL), balance (0) AVLNode ( Type d, AVLNode *l = NULL, AVLNode *r = NULL ) : data (d), left (l), right (r), balance (0) ;protected: Type RefValue; AVL

56、Node *root; int Insert ( AVLNode* &tree, Type x, int &taller ); void RotateLeft ( AVLNode *Tree, AVLNode* &NewTree ); void RotateRight ( AVLNode *Tree, AVLNode* &NewTree ); void LeftBalance ( AVLNode* &Tree, int &taller ); void RightBalance(AVLNode* &Tree, int &taller

57、); int Depth ( AVLNode *t ) const;public: AVLTree ( ) : root (NULL) AVLNode ( Type Ref ) : RefValue (Ref), root (NULL) int Insert ( Type x ) int taller; return Insert ( root, x, taller ); friend istream& operator ( istream& in, AVLTree& Tree ); friend ostream& operator ( ostream&

58、 out, const AVLTree& Tree ); int Depth ( ) const;hhhACEBD(a) (b) (c)hhh+1BACEDhhh+1CEABDtemplate void AVLTree:RotateLeft ( AVLNode *Tree, AVLNode* &NewTree ) NewTree = Treeright; Treeright = NewTreeleft; NewTreeleft = Tree; hhhACEBD(a) (b) (c)hh+1BACEDhhh+1CEABDhtemplate void AVLTree:RotateR

59、ight( AVLNode *Tree, AVLNode* &NewTree) NewTree = Treeleft; Treeleft = NewTreeright; NewTreeright = Tree;插入插入template void AVLTree:LeftBalance ( AVLNode * &Tree, int & taller ) AVLNode *leftsub = Treeleft, *rightsub; switch ( leftsubbalance ) case -1 : Treebalance = leftsubbalance = 0; R

60、otateRight ( Tree, Tree ); taller = 0; break; case 0 : cout “樹(shù)已經(jīng)平衡化樹(shù)已經(jīng)平衡化.n; break; case 1 : rightsub = leftsubright; switch ( rightsubbalance ) case -1: Treebalance = 1; leftsubbalance = 0; break; case 0 :Treebalance = leftsubbalance = 0; break; case 1 : Treebalance = 0; leftsubbalance = -1; break; rightsubbalance = 0; RotateLeft ( leftsub, Treeleft ); RotateRight ( Tr