1 /************************************************************************/
  2 /* 二叉寻找树的实现                                                                       */
  3 /************************************************************************/
  4 
  5 template <typename Comparable>
  6 class  BinarySearchTree
  7 {
  8 public:
  9      BinarySearchTree()
 10      {
 11          root = new TreeNode;
 12      }
 13 
 14     ~ BinarySearchTree()
 15     {
 16         makeEmpty(root);
 17     }
 18 
 19     //考贝构造函数
 20     BinarySearchTree(const BinarySearchTree& tree)
 21     {
 22         root = new TreeNode;
 23         *this = tree;
 24     }
 25 
 26     //重载赋值运算符
 27     BinarySearchTree& operator = (const BinarySearchTree & tree)
 28     {
 29         makeEmpty();
 30         root = clone(tree.root);      //通过clone函数完成数据拷贝
 31         return *this;
 32     }
 33 
 34     bool isEmpty() const
 35     {
 36         return (root->left == NULL) || (root->right == NULL);
 37     }
 38 
 39     //寻找最大的元素,递归实现
 40     TreeNode* findmax() const
 41     {
 42         if (root == NULL)
 43         {
 44             return NULL;
 45         }
 46         if (root->right == NULL)
 47         {
 48             return root;
 49         }
 50         root->right->findmax();
 51     }
 52 
 53     //寻找最小的元素，循环实现
 54     TreeNode* findmin() const
 55     {
 56         TreeNode* temp = root;
 57         if (temp == NULL)
 58         {
 59             return NULL;
 60         }
 61         while (temp->left == NULL)
 62         {
 63             temp = temp->left;
 64         }
 65         return temp->element;
 66     }
 67 
 68     bool find(const Comparable & object) const
 69     {
 70         return find(object, root);
 71     }
 72 
 73     void insert(const Comparable & object)
 74     {
 75         return insert(object, root);
 76     }
 77 private:
 78     struct TreeNode       //树节点
 79     {
 80         Comparable element;
 81         TreeNode* left;
 82         TreeNode* right;
 83 
 84         TreeNode(Comparable c = Comparable(), TreeNode* l = NULL, TreeNode* r = NULL)
 85             :element(c), left(l), right(r){ }
 86     };
 87 
 88     TreeNode* root;     //树的根节点指针
 89 
 90     bool find(const Camparable & object, TreeNode* t) const
 91     {
 92         if (t == NULL)
 93         {
 94             return false;
 95         }
 96         if (root->element >object)
 97         {
 98             find(object, root->right);
 99         }
100         else if (root->element < object)
101         {
102             find(object, root->left);
103         }
104         else
105         {
106             return true;
107         }
108     }
109 
110     void insert(const Comparable & object, TreeNode* t)
111     {
112         if (t == NULL)
113         {
114             t = new TreeNode(object);
115             return;
116         }
117         if (root->element > object)
118         {
119             insert(object, t->left);
120         } 
121         else if(root->element < object)
122         {
123             insert(object, t->right);
124         }
125         else
126         {
127             //do nothing
128         }
129     }
130 
131     void remove(const Comparable & object, TreeNode* t)
132     {
133         //先查到对象
134         if (t == NULL)
135         {
136             return;
137         }
138         if (t->element >object)
139         {
140             remove(object, t->right);
141         }
142         else if (t->element < object)
143         {
144             remove(object, t->left);
145         }
146         else if(root->left != NULL && root->right != NULL)   //处理有两个儿子的情况
147         {
148              Comparable ret = findmin(root->right)->element;  //找到右儿子中最小的那个,代替删除的节点
149              t->element = ret;
150              remove(ret, t->right);   //删除那个子节点
151         }
152         else         //处理一个儿子的情况
153         {
154             TreeNode* old = t;
155             t = (t->left != NULL) ? t->left : t->right;
156             delete old;
157         }
158     }
159 
160     void makeEmpty(TreeNode* t)
161     {
162         if (t == NULL)
163         {
164             return;
165         }
166         makeEmpty(t->left);
167         makeEmpty(t->right);
168         delete t;
169         t = NULL;
170     }
171 
172     TreeNode * clone( TreeNode* t) const
173     {
174         if (t == NULL)
175         {
176             return NULL;
177         }
178         return new TreeNode(t->element, t->left, t->right);
179     }
180 };