又是一次的毕业季,羡慕嫉妒啊....
二叉查找树类的框架:
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 }