又是一次的毕业季，羡慕嫉妒啊....
二叉查找树类的框架：
1 template <typename Comparable> 2 class BinarySearchTree 3 { 4 public: 5 BinarySearchTree(); 6 BinarySearchTree(const BinarySearchTree & rhs) 7 ~BinarySearchTree(); 8 9 const Comparable & findMin() const; 10 const Comparable & findMax() const; 11 12 bool contains(const Comparable & x ) const; 13 bool isEmpty() const; 14 void printTree() const; 15 16 void makeEmpty(); 17 void insert(const Comparable & x); 18 void remove(const Comparable & x); 19 20 const BinarySearchTree & operator = (const BinarySearchTree & rhs); 21 22 private: 23 struct BinaryNode 24 { 25 Comparable element; 26 BinaryNode *left; 27 BinaryNode *right; 28 29 BinaryNode(const Comparable & theElement,BinaryNode *lt,BinaryNode *rt):element(theElement),left(lt),right(rt){} 30 }; 31 32 BinaryNode *root; 33 34 void insert (const Comparable & x,BinaryNode * & t) const; 35 void remove (const Comparable & x ,BinaryNode * & t) const; 36 BinaryNode * findMin(BinaryNode *t) const; 37 BinaryNode * findMax(BinaryNode *t) const; 38 bool contains( const Comparable & x,BinaryNode * t) const; 39 void makeEmpty( BinaryNode * & t); 40 void printTree(BinaryNode *t) const; 41 BinaryNode * clone(BinaryNode *t) const; 42 };
contains insert remove三种操作递归列表：
bool contains (const Comparable & x) const { return contains(x,root) } void insert(const Comparable & x) { insert (x,root); } void remove(const Comparable & x) { remove(x,root); }
二叉查找树的contains操作：
1 bool contains(const Comparable & x,BinaryNode * t) const 2 { 3 if( t == NUll ) 4 return false; 5 else if ( x < t->element ) 6 return contains(x,t->left ); 7 else if (t->element < t) 8 return contains(x,t->right); 9 else 10 return true; 11 }
使用函数对象 实现 二叉查找树：
template <typename Object,typename Comparator = less<Object>> class BinarySearchTree { public: private: BinaryNode * root; Comparable isLessThan; bool contains( const Object & x,BinaryNode *t ) const { if(t == NULL) return false; else if (isLessThan(x,t->element)) return contains(x,t->left); else if (isLessThan(t->element,x)) return contains(x,t->right); else return true; } };
findMin方法的递归实现：
1 BinaryNode * findMin( BinaryNode * t) const 2 { 3 if( t == NULL) 4 return NULL; 5 if(t->left == NULL) 6 return t; 7 return findMin(t->left); 8 }
findMax方法的递归实现：
1 BinaryNode * findMax(BinaryNode * t) const 2 { 3 if(t != NULL) 4 while( t ->right !=NULL) 5 t = t->right; 6 return t; 7 }
二叉查找树插入操作：
1 void insert( const Comparable & x,BinaryNode * & t ) 2 { 3 if( t== NULL) 4 t = new BinaryNode(x,NULL,NULL); 5 else if (x<t->element) 6 insert(x,t->left); 7 else if (t->element < x) 8 insert(x,t->right); 9 else 10 ; 11 }
二叉查找树 删除操作:
1 void remove (const Comparable & x,BinaryNode * & t) 2 { 3 if( t == NULL) 4 return; 5 if( x < t->element) 6 remove( x,t->left); 7 else if ( t->element < x) 8 remove(x,t->right); 9 else if (t->left != NULL && t->right!=NULL ) 10 { 11 t->element = findMin( t->right)->element; 12 remove(t->element , t->right); 13 } 14 else 15 { 16 BinaryNode *oldNode = t; 17 t = ( t->left !=NULL) ? t->left : t->right; 18 delete oldNode; 19 } 20 }
析构函数递归实现makeEmpty
~BinarySearchTree() { makEmpty(); } void makeEmpty(BinaryNode * & t) { if( t != NULL) { makeEmpty(t->left); makeEmpty(t->right); delete t; } t = NULL; }
operator= 递归实现clone：
1 const BinarySearchTree & operator=( const BianrySearchTree & rhs) 2 { 3 if(this != &rhs) 4 { 5 makeEmpty(); 6 root = clone(rhs.root); 7 } 8 return *this; 9 } 10 11 BinaryNode * clone( BinaryNode * t) const 12 { 13 if( t == NULL) 14 return NULL; 15 return new BinaryNode ( t->element,clone(t->left),clone(t->right)); 16 }
本文转自博客园xingoo的博客，原文链接：20120919-二叉树 数据结构《数据结构与算法分析》，如需转载请自行联系原博主。
