# 20120919-二叉树 数据结构《数据结构与算法分析》

 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);
}

 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 }

~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 }

|
12天前
|

【数据结构】二叉树全攻略，从实现到应用详解

38 13
|
9天前
|

25 6
|
9天前
|

14 3
|
9天前
|

17 2
|
1月前
|

【初阶数据结构篇】二叉树算法题

15 0
|
1月前
|

【初阶数据结构篇】实现链式结构二叉树（二叉链）下篇

19 0
|
1月前
|

【初阶数据结构篇】实现链式结构二叉树（二叉链）上篇

22 0
|
1月前
|

【初阶数据结构篇】实现顺序结构二叉树（堆的实现方法）

14 0
|
1月前
|

【初阶数据结构篇】单链表算法题进阶

14 0
|
1月前
|

【初阶数据结构篇】顺序表和链表算法题

16 0