【1】二叉排序树
二叉排序树，又称为二叉查找树。
它或者是一棵空树，或者具有下列性质：
1. 若它的左子树不空，则左子树上所有的结点的值均小于它的根结点的值；
2. 若它的右子树不空，则右子树上所有的结点的值均大于它的根结点的值；
3. 它的左右子树也分别为二叉排序树。
【2】二叉排序树的代码实现
结合下图以及实现代码分析
（1）构建二叉排序树
（2）实现代码
1 #include2 using namespace std; 3 4 template class BST; 5 6 template 7 class BstNode 8 { 9 friend class BST ; 10 Type data; 11 BstNode *leftChild, *rightChild; 12 public: 13 BstNode():leftChild(NULL), rightChild(NULL) 14 {} 15 BstNode(const Type &x,BstNode *left = NULL, BstNode *right = NULL) 16 : data(x) 17 , leftChild(left) 18 , rightChild(right) 19 {} 20 ~BstNode() 21 {} 22 Type & GetData() { return data;} 23 const Type & GetData() const { return data;} 24 BstNode *&GetLeft() { return leftChild;} 25 BstNode * const&GetLeft() const { return leftChild;} 26 BstNode * &GetRight() { return rightChild;} 27 BstNode * const &GetRight() const { return rightChild;} 28 }; 29 template 30 class BST 31 { 32 private: 33 BstNode *root; 34 private: 35 ///私有方法部分 36 bool insert(BstNode *&ptr, const Type &x); 37 bool insertElem(BstNode *&ptr, const Type &x); 38 BstNode * find(BstNode * ptr, const Type &x); 39 BstNode * findRecursive(BstNode * ptr, const Type &x); 40 BstNode * findPre(BstNode *ptr, const Type &x); 41 BstNode * max(BstNode *ptr) const; 42 BstNode * min(BstNode *ptr) const; 43 bool remove(BstNode *&ptr, const Type &x); 44 bool removeRecursive(BstNode *&ptr, const Type &x); 45 void InOrder(BstNode *ptr) const; 46 void LevelOrder(BstNode *t) const; 47 public: 48 BST(): root(NULL) 49 { } 50 BST(Type x): root(NULL) 51 { } 52 ~BST() 53 { } 54 BstNode * GetRoot() 55 { 56 return root; 57 } 58 void SetRoot(BstNode * pRoot) 59 { 60 root = pRoot; 61 } 62 int Insert(const Type &x) 63 { 64 return insert(root, x); 65 } 66 BstNode * Find(const Type &x) 67 { 68 return find(root, x); 69 } 70 void InOrder() 71 { 72 InOrder(root); 73 cout << endl; 74 } 75 BstNode * Min() const 76 { 77 return min(root); 78 } 79 BstNode * Max() const 80 { 81 return max(root); 82 } 83 int Remove(const Type &x) 84 { 85 return remove(root, x); 86 } 87 void LevelOrder() 88 { 89 LevelOrder(root); 90 } 91 }; 92 // 插入数据元素方法1 (递归实现) 93 template 94 bool BST ::insert(BstNode *&ptr, const Type &x) 95 { 96 if (NULL == ptr) 97 { // 为空时就需要创建新节点 98 ptr = new BstNode (x); 99 if (NULL == ptr)100 {101 cerr << "out of space" << endl;102 return false;103 }104 return true;105 }106 else if (x < ptr->data) 107 { // 小, 插入其左边108 return insert(ptr->leftChild, x);109 }110 else if (x > ptr->data)111 { // 大, 插入其右边112 return insert(ptr->rightChild, x);113 }114 else115 { // 两者相等116 cout << "数据" << x << "重复,请重新输入..." << endl;117 return false;118 }119 }120 // 插入数据元素方法2 （非递归实现）121 template 122 bool BST ::insertElem(BstNode *&ptr, const Type &x)123 {124 if (NULL == ptr)125 {126 ptr = new BstNode (x);127 if (NULL == ptr)128 {129 cout << "out of space !" << endl;130 return false;131 }132 return true;133 }134 BstNode * p = ptr, *q = NULL;135 while (p != NULL)136 {137 q = p;138 if (x == p->data)139 {140 cout << "数据重复" << endl;141 return false;142 }143 if (x > p->data)144 {145 p = p->rightChild;146 }147 else if (x < p->data)148 {149 p = p->leftChild;150 }151 }152 p = new BstNode (x);153 if (x < q->data)154 q->leftChild = p;155 if (x > q->data)156 q->rightChild = p;157 return true;158 }159 // 查找某个数据元素的节点指针 （递归实现）160 template 161 BstNode * BST ::findRecursive(BstNode *ptr, const Type &x)162 {163 if (NULL == ptr)164 return NULL;165 else if (x < ptr->data)166 return find(ptr->leftChild, x);167 else if (x > ptr->data)168 return find(ptr->rightChild, x);169 else170 return ptr;171 }172 // 查找某个数据元素的节点指针 (非递归实现)173 template 174 BstNode * BST ::find(BstNode *ptr, const Type &x)175 {176 while (ptr != NULL)177 {178 if (x == ptr->data) 179 return ptr;180 else if (ptr->data > x)181 ptr = ptr->leftChild;182 else183 ptr = ptr->rightChild;184 }185 return NULL;186 }187 // 查找某个数据元素的父节点指针 (非递归实现)188 // 记录父节点，当孩子值与查找的数据元素值相同，返回父节点即可。189 template 190 BstNode * BST ::findPre(BstNode *ptr, const Type &x)191 {192 BstNode * q = NULL;193 while (ptr != NULL)194 {195 if (x == ptr->data) 196 {197 return q;198 }199 else if (ptr->data > x)200 {201 q = ptr;202 ptr = ptr->leftChild;203 }204 else205 {206 q = ptr;207 ptr = ptr->rightChild;208 }209 }210 return NULL;211 }212 // 按元素值删除某个节点 （递归实现）213 // 具体删除思路请参考注释214 template 215 bool BST ::removeRecursive(BstNode *&ptr, const Type &x)216 {217 BstNode * tmp = NULL;218 if (ptr != NULL)219 { 220 if (x < ptr->data) // 小于，转向左子树221 return remove(ptr->leftChild, x);222 else if (x > ptr->data) // 大于，转向右子树223 return remove(ptr->rightChild, x);224 // 相等时即找到 然后判断左右子树情况225 else if (ptr->leftChild != NULL && ptr->rightChild != NULL) 226 { 227 // 1. 左右均不空228 tmp = min(ptr->rightChild); // 找到右子树的最小值结点229 ptr->data = tmp->data; // 数值更换230 return remove(ptr->rightChild, ptr->data); // 递归再删除那个最小值结点231 }232 else 233 { // 2. 左为空 || 右为空 || 左右子树均为空234 tmp = ptr;235 if (NULL == ptr->leftChild) // 先考虑左子树236 ptr = ptr->rightChild; // 衔接其右节点237 else if (NULL == ptr->rightChild) // 再考虑右子树238 ptr = ptr->leftChild; // 衔接其左节点239 240 delete tmp;241 tmp = NULL; 242 return true;243 }244 }245 return false;246 }247 // 按元素值删除某个节点 （非递归实现）248 // 具体删除思路请参考注释249 template 250 bool BST ::remove(BstNode *&ptr, const Type &x)251 {252 BstNode * pself = find(ptr, x); // 欲删除结点自身253 BstNode * parent = findPre(ptr, x); // 欲删除结点的父节点254 BstNode * pDelete = pself; // 最终删除结点255 if (NULL == pself)256 {257 cout << "删除数据不存在！" << endl;258 return false;259 }260 // 满足以下情况时需要转换一下实际删除节点261 if (pself->leftChild != NULL && pself->rightChild != NULL) 262 { 263 pDelete = min(pself->rightChild); // 找到右子树的最小值结点，将来删除它即可264 pself->data = pDelete->data; // 数值更换265 parent = findPre(pself->rightChild, pself->data); // 重新确定实际删除对象的父节点266 if (NULL == parent)267 {268 // 当删除右子树的根节点 (只有可能右子树存在)269 ptr->rightChild = pDelete->rightChild; // 衔接右子树即可270 // 执行删除 释放内存271 delete pDelete;272 pDelete = NULL;273 return true;274 }275 }276 // 当欲删除父节点 且其孩子为空277 if (NULL == parent)278 {279 if (NULL == pself->leftChild && 280 NULL == pself->rightChild)281 { // 当树只有一个根节点 两孩子都为空282 delete ptr;283 ptr = NULL;284 return true;285 }286 else if (NULL == pself->leftChild)287 { // 右孩子存在288 ptr = pself->rightChild;289 }290 else if (NULL == pself->rightChild)291 { // 左孩子存在292 ptr = pself->leftChild;293 }294 }295 else296 {297 // 衔接结点298 if (parent->data < pDelete->data)299 { // 右孩子300 if (NULL == pDelete->leftChild) 301 parent->rightChild = pDelete->rightChild;302 else if (NULL == pDelete->rightChild) 303 parent->rightChild = pDelete->leftChild; 304 }305 else306 { // 左孩子307 if (NULL == pDelete->leftChild) 308 parent->leftChild = pDelete->rightChild; 309 else if (NULL == pDelete->rightChild) 310 parent->leftChild = pDelete->leftChild;311 }312 }313 // 执行删除 释放内存314 delete pDelete;315 pDelete = NULL;316 return true;317 }318 // 打印二叉搜索树的数据 (中序遍历)319 // 思路分析：320 // 先遍历左子树321 // 再遍历根节点322 // 最后遍历右子树323 template 324 void BST ::InOrder(BstNode *ptr) const325 {326 if (ptr != NULL)327 {328 InOrder(ptr->leftChild);329 cout << ptr->data << " ";330 InOrder(ptr->rightChild);331 }332 }333 // 求二叉搜索树某一个子树的最小元素指针334 // 思路分析：335 // 一直向左子树递进即为最小336 template 337 BstNode * BST ::min(BstNode *ptr) const338 {339 BstNode *p = ptr;340 while (p != NULL && p->leftChild != NULL)341 {342 p = p->leftChild;343 }344 return p;345 }346 // 求二叉搜索树某一个子树的最大元素指针347 // 思路分析：348 // 一直向右子树递进即为最大349 template 350 BstNode * BST ::max(BstNode *ptr) const351 {352 BstNode *p = ptr;353 while (p != NULL && p->rightChild != NULL) // 保证p不等于空!354 {355 p = p->rightChild;356 }357 return p;358 }359 360 void main()361 {362 BST bst;363 int a[12] = { 53,17,9,45,23,40,38,78,65,87,81,94};364 for (int i = 0; i < 12; ++i)365 {366 bst.Insert(a[i]);367 }368 cout << "中序遍历的结果如下：" << endl;369 bst.InOrder();370 371 int data = 0;372 cout << "请输入要查找的数据:";373 cin >> data;374 if (bst.Find(data) != NULL)375 cout << "查找成功！" << endl;376 else377 cout << "未查找到！" << endl;378 379 cout << "请输入要删除的数据:";380 for (; ;)381 {382 int num = 0;383 while (cin >> num, num != -1)384 {385 if (-1 == num) 386 break;387 bst.Remove(num);388 cout << "删除后数据打印：" << endl;389 bst.InOrder();390 cout << "请输入要删除的数据(-1结束):";391 }392 break;393 }394 }
Good Good Study, Day Day Up.
顺序 选择 循环 总结