二叉查找树_代码

二叉查找树_代码_详细注释

  1 #include <iostream>
  2 #include <ctime>
  3 using namespace std;
  4 
  5 template<typename T>
  6 struct BinaryNode
  7 {
  8     T element;
  9     BinaryNode<T> *left;
 10     BinaryNode<T> *right;
 11 
 12     BinaryNode(const T &theElement, BinaryNode *lt, BinaryNode *rt)
 13         : element(theElement), left(lt), right(rt) {}
 14 };
 15 
 16 
 17 template<typename T>
 18 class BinarySearchTree
 19 {
 20 public:
 21     BinarySearchTree() {
 22         root = nullptr;
 23     }
 24     BinarySearchTree(const BinarySearchTree& rhs) {  //复制构造函数
 25         root = clone(rhs.root);
 26     }
 27     ~BinarySearchTree();
 28 
 29     const T &findMin() const {
 30         return findMin(root)->element;
 31     }
 32     const T &findMax() const {
 33         return findMax(root)->element;
 34     }
 35     bool contains(const T& x) const;
 36     bool isEmpty() const {
 37         if (root == nullptr)
 38             return true;
 39         return false;
 40     }
 41     void printTree() const {
 42         printTree(root);
 43     }
 44 
 45     void makeEmpty();
 46     void insert(const T &x);
 47     void remove(const T &x);
 48 
 49     const BinarySearchTree& operator = (const BinarySearchTree& rhs);
 50 
 51 private:
 52 
 53     BinaryNode<T> *root;                      //指向树根结点的指针
 54 
 55     void insert(const T & x, BinaryNode<T> * & t);  
 56     void remove(const T & x, BinaryNode<T> * & t);
 57     BinaryNode<T> * findMin(BinaryNode<T> *t) const;
 58     BinaryNode<T> * findMax(BinaryNode<T> *t ) const;
 59     bool contains(const T & x, BinaryNode<T> *t) const;
 60     void makeEmpty( BinaryNode<T> * & t );
 61     void printTree( BinaryNode<T> * t ) const;
 62     BinaryNode<T> * clone( BinaryNode<T> * t ) const;
 63 };
 64 
 65 template<typename T>
 66 bool BinarySearchTree<T>::contains(const T& x) const
 67 {
 68     return contains(x, root);
 69 }
 70 
 71 template<typename T>
 72 bool BinarySearchTree<T>::contains(const T & x, BinaryNode<T> *t) const
 73 {
 74     if (t == nullptr)
 75         return false;
 76     else if (x < t->element)          // x 小， 说明应该在左边找
 77         return contains(x, t->left);
 78     else if (t->element < x)          // x 大， 说明应该在右面找
 79         return contains(x, t->right);
 80     else 
 81         return true;
 82 }
 83 
 84 //findMin--返回指向树中包含最小元的结点的指针
 85 template<typename T>
 86 BinaryNode<T> * BinarySearchTree<T>::findMin(BinaryNode<T> *t) const
 87 {
 88     if (t == nullptr)
 89         return  nullptr;
 90     if (t->left == nullptr)
 91         return t;
 92     return findMin(t->left);
 93 }
 94 
 95 template<typename T>
 96 BinaryNode<T>* BinarySearchTree<T>::findMax(BinaryNode<T> *t) const
 97 {
 98     if (t != nullptr)
 99         while (t->right != nullptr) {
100             t = t->right;
101         }
102     return t;
103 }
104 
105 template<typename T>
106 void BinarySearchTree<T>::insert(const T &x)
107 {
108     insert(x, root);
109 }
110 
111 /************************************************************************/
112 /* x is the item to insert        */
113 /* t is the node that roots the subtree*/
114 /* Set the new root of the subtree*/
115 ///* 只有当一个新树叶生成时候，t才改变.
116 ///* t 是到p->left或p->right的引用.==> 意味着p->left或p->right将会改变为指向新结点.
117 /************************************************************************/
118 template<typename T>
119 void BinarySearchTree<T>::insert(const T & x, BinaryNode<T> * & t)
120 {
121     if (t == nullptr)         //没有结点，在该位置处添加新结点
122         t = new BinaryNode<T>(x, nullptr, nullptr);
123     else if (x < t->element)  //x 小， 在左子树查询
124         insert(x, t->left);  
125     else if (t->element < x)  //x 大， 在右子树查询
126         insert(x, t->right);
127     else;                     //Duplicate, do nothing;
128 }
129 
130 template<typename T>
131 void BinarySearchTree<T>::remove(const T &x)
132 {
133     remove(x, root);
134 }
135 
136 ///************************************************************************/
137 ///* x is item to remove 
138 /////* t is the node that roots the subtree
139 /////* Set the new root of the subtree
140 ///* 1.结点是一片树叶时 -- 可被立即删除
141 ///* 2.结点有一个儿子, 则该结点可以在其父节点调整他的链 以绕过该结点后被删除
142 ///* 3.结点有两个儿子, 则其右子树的最小数据代替该结点的数据，并递归删除那个结点
143 ///* 注: 右子树中的最小的结点不可能有左结点
144 ///************************************************************************/
145 template<typename T>
146 void BinarySearchTree<T>::remove(const T &x, BinaryNode<T> * & t)
147 {
148     if (t == nullptr) return;     //Item not found; do nothing
149     if (x < t->element)           //x 小，在左子树递归查找
150         remove(x, t->left);
151     else if (t->element < x)      //x 大，在右子树递归查找
152         remove(x, t->right); 
153     else if (t->left != nullptr && t->right != nullptr)  //two children
154     {
155         //在右子树中查找最小数据代替该结点数据.;
156         t->element = findMin(t->right)->element;
157         remove(t->element, t->right);                    //删除该结点
158     }
159     else                         //只有一个结点或是树叶. 调整它的链,以绕过该结点后被删除.
160     {                          
161         BinaryNode<T> *oldNode = t;
162         t = (t->left != nullptr) ? t->left : t->right;
163         delete oldNode;
164     }
165 }
166 
167 /************************************************************************/
168 ///* Destructor for the tree
169 /************************************************************************/
170 template<typename T>
171 BinarySearchTree<T>::~BinarySearchTree()
172 {
173     makeEmpty();
174 }
175 
176 template<typename T>
177 void BinarySearchTree<T>::makeEmpty()       //公有函数
178 {
179     makeEmpty(root);
180 }
181 
182 /************************************************************************/
183 ///* Internal method to make subtree empty -- 私有函数
184 /************************************************************************/
185 template<typename T>
186 void BinarySearchTree<T>::makeEmpty(BinaryNode<T> * & t)   
187 {
188     if (t != nullptr)
189     {
190         makeEmpty(t->left);
191         makeEmpty(t->right);
192         delete t;
193     }
194     t = nullptr;
195 }
196 
197 /************************************************************************/
198 ///* Deep copy
199 /************************************************************************/
200 template<typename T>
201 const BinarySearchTree<T>& BinarySearchTree<T>::operator = (const BinarySearchTree &rhs)
202 {
203     if (this != &rhs) {
204         makeEmpty();
205         root = clone(rhs.root);
206     }
207     return *this;
208 }
209 
210 /************************************************************************/
211 ///* Internal method to clone subtree.  --  递归复制结点
212 /************************************************************************/
213 template<typename T>
214 BinaryNode<T>* BinarySearchTree<T>::clone(BinaryNode<T> * t) const
215 {
216     if (t == nullptr)
217         return nullptr;
218     return new BinaryNode<T>( t->element, clone(t->left), clone(t->right) );
219 }
220 
221 /************************************************************************/
222 ///* printTree  
223 /************************************************************************/
224 template<typename T>
225 void BinarySearchTree<T>::printTree(BinaryNode<T> * t) const
226 {
227     
228     if (t != nullptr) {
229         cout << t->element << ' ';
230         printTree(t->left);
231         printTree(t->right);
232     }
233 }
234 
235 int main()
236 {
237     srand((unsigned)time(nullptr));
238     int testData, t = 0;
239     BinarySearchTree<int> test;
240     cout << "输入数字个数: 
";
241     cin >> t;
242     cout << "输入数字: 
";
243     while (t--)
244     {
245         testData = rand() % 1000 + 1;
246         test.insert(testData);
247     }
248     cout << "
全部元素为: 
";
249     test.printTree();
250     cout << "
Max = " << test.findMax() << endl;
251     cout << "Min = " << test.findMin() << endl;
252     cout << "输入查找元素: 
";
253     cin >> testData;
254     cout << "是否包含 " << testData  << " : " << test.contains(testData) << endl; 
255     test.printTree();
256     cout << endl;
257     cout << "输入删除元素: 
";
258     cin >> testData;
259     test.remove(testData);
260     test.printTree();
261     cout << endl;
262     return 0;
263 }