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 subtree139 /////* Set the new root of the subtree140 ///* 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 nothing149     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 children154     {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 tree169 /************************************************************************/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 copy199 /************************************************************************/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) const215 {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) const226 {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 << "输入数字个数: \n";241     cin >> t;242     cout << "输入数字: \n";243     while (t--)244     {245         testData = http://www.mamicode.com/rand() % 1000 + 1;246         test.insert(testData);247     }248     cout << "\n全部元素为: \n";249     test.printTree();250     cout << "\nMax = " << test.findMax() << endl;251     cout << "Min = " << test.findMin() << endl;252     cout << "输入查找元素: \n";253     cin >> testData;254     cout << "是否包含 " << testData  << " : " << test.contains(testData) << endl; 255     test.printTree();256     cout << endl;257     cout << "输入删除元素: \n";258     cin >> testData;259     test.remove(testData);260     test.printTree();261     cout << endl;262     return 0;263 }