二叉查找树(二)之 C++的实现
?
概要
上一章介紹了"二叉查找樹的相關理論知識，并通過C語言實現了二叉查找樹"。這一章給出二叉查找樹的C++版本。這里不再對樹的相關概念進行介紹，若遇到不明白的概念，可以在上一章查找。
目錄
1.?二叉樹查找樹
2.?二叉查找樹的C++實現
3.?二叉查找樹的C++實現(完整源碼)
4.?二叉查找樹的C++測試程序
轉載請注明出處：http://www.cnblogs.com/skywang12345/p/3576373.html
更多內容:?數據結構與算法系列 目錄?
(01)?二叉查找樹(一)之 圖文解析 和 C語言的實現
(02)?二叉查找樹(二)之 C++的實現
?
二叉查找樹簡介
二叉查找樹(Binary Search Tree)，又被稱為二叉搜索樹。
它是特殊的二叉樹：對于二叉樹，假設x為二叉樹中的任意一個結點，x節點包含關鍵字key，節點x的key值記為key[x]。如果y是x的左子樹中的一個結點，則key[y] <= key[x]；如果y是x的右子樹的一個結點，則key[y] >= key[x]。那么，這棵樹就是二叉查找樹。如下圖所示：
在二叉查找樹中：
(01) 若任意節點的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值；
(02) 任意節點的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值；
(03) 任意節點的左、右子樹也分別為二叉查找樹。
(04) 沒有鍵值相等的節點（no duplicate nodes）。
?
二叉查找樹的C++實現
1. 節點和二叉查找樹的定義
1.1 二叉查找樹節點
template <class T> class BSTNode{public:T key; // 關鍵字(鍵值)BSTNode *left; // 左孩子BSTNode *right; // 右孩子BSTNode *parent;// 父結點 BSTNode(T value, BSTNode *p, BSTNode *l, BSTNode *r):key(value),parent(),left(l),right(r) {} };BSTNode是二叉查找樹的節點，它包含二叉查找樹的幾個基本信息：
(01) key -- 它是關鍵字，是用來對二叉查找樹的節點進行排序的。
(02) left -- 它指向當前節點的左孩子。
(03) right -- 它指向當前節點的右孩子。
(04) parent -- 它指向當前節點的父結點。
?
1.2 二叉樹操作
template <class T> class BSTree {private:BSTNode<T> *mRoot; // 根結點public:BSTree();~BSTree();// 前序遍歷"二叉樹"void preOrder();// 中序遍歷"二叉樹"void inOrder();// 后序遍歷"二叉樹"void postOrder();// (遞歸實現)查找"二叉樹"中鍵值為key的節點BSTNode<T>* search(T key);// (非遞歸實現)查找"二叉樹"中鍵值為key的節點BSTNode<T>* iterativeSearch(T key);// 查找最小結點：返回最小結點的鍵值。 T minimum();// 查找最大結點：返回最大結點的鍵值。 T maximum();// 找結點(x)的后繼結點。即，查找"二叉樹中數據值大于該結點"的"最小結點"。BSTNode<T>* successor(BSTNode<T> *x);// 找結點(x)的前驅結點。即，查找"二叉樹中數據值小于該結點"的"最大結點"。BSTNode<T>* predecessor(BSTNode<T> *x);// 將結點(key為節點鍵值)插入到二叉樹中void insert(T key);// 刪除結點(key為節點鍵值)void remove(T key);// 銷毀二叉樹void destroy();// 打印二叉樹void print();private:// 前序遍歷"二叉樹"void preOrder(BSTNode<T>* tree) const;// 中序遍歷"二叉樹"void inOrder(BSTNode<T>* tree) const;// 后序遍歷"二叉樹"void postOrder(BSTNode<T>* tree) const;// (遞歸實現)查找"二叉樹x"中鍵值為key的節點BSTNode<T>* search(BSTNode<T>* x, T key) const;// (非遞歸實現)查找"二叉樹x"中鍵值為key的節點BSTNode<T>* iterativeSearch(BSTNode<T>* x, T key) const;// 查找最小結點：返回tree為根結點的二叉樹的最小結點。BSTNode<T>* minimum(BSTNode<T>* tree);// 查找最大結點：返回tree為根結點的二叉樹的最大結點。BSTNode<T>* maximum(BSTNode<T>* tree);// 將結點(z)插入到二叉樹(tree)中void insert(BSTNode<T>* &tree, BSTNode<T>* z);// 刪除二叉樹(tree)中的結點(z)，并返回被刪除的結點BSTNode<T>* remove(BSTNode<T>* &tree, BSTNode<T> *z);// 銷毀二叉樹void destroy(BSTNode<T>* &tree);// 打印二叉樹void print(BSTNode<T>* tree, T key, int direction); };BSTree是二叉樹。它包含二叉查找樹的根節點和二叉查找樹的操作。二叉查找樹的操作中有許多重載函數，例如insert()函數，其中一個是內部接口，另一個是提供給外部的接口。
?
2 遍歷
這里講解前序遍歷、中序遍歷、后序遍歷3種方式。
2.1 前序遍歷
若二叉樹非空，則執行以下操作：
(01) 訪問根結點；
(02) 先序遍歷左子樹；
(03) 先序遍歷右子樹。
前序遍歷代碼
?
2.2 中序遍歷
若二叉樹非空，則執行以下操作：
(01) 中序遍歷左子樹；
(02) 訪問根結點；
(03) 中序遍歷右子樹。
中序遍歷代碼
template <class T> void BSTree<T>::inOrder(BSTNode<T>* tree) const {if(tree != NULL){inOrder(tree->left);cout<< tree->key << " " ;inOrder(tree->right);} }template <class T> void BSTree<T>::inOrder() {inOrder(mRoot); }?
2.3 后序遍歷
若二叉樹非空，則執行以下操作：
(01) 后序遍歷左子樹；
(02) 后序遍歷右子樹；
(03) 訪問根結點。
后序遍歷代碼
template <class T> void BSTree<T>::postOrder(BSTNode<T>* tree) const {if(tree != NULL){postOrder(tree->left);postOrder(tree->right);cout<< tree->key << " " ;} }template <class T> void BSTree<T>::postOrder() {postOrder(mRoot); }?
?
看看下面這顆樹的各種遍歷方式：
對于上面的二叉樹而言，
(01) 前序遍歷結果：?3 1 2 5 4 6
(02) 中序遍歷結果：?1 2 3 4 5 6?
(03) 后序遍歷結果：?2 1 4 6 5 3
?
3. 查找
遞歸版本的代碼
template <class T> BSTNode<T>* BSTree<T>::search(BSTNode<T>* x, T key) const {if (x==NULL || x->key==key)return x;if (key < x->key)return search(x->left, key);elsereturn search(x->right, key); }template <class T> BSTNode<T>* BSTree<T>::search(T key) {search(mRoot, key); }非遞歸版本的代碼
template <class T> BSTNode<T>* BSTree<T>::iterativeSearch(BSTNode<T>* x, T key) const {while ((x!=NULL) && (x->key!=key)){if (key < x->key)x = x->left;elsex = x->right;}return x; }template <class T> BSTNode<T>* BSTree<T>::iterativeSearch(T key) {iterativeSearch(mRoot, key); }
4. 最大值和最小值
查找最大值的代碼
template <class T> BSTNode<T>* BSTree<T>::maximum(BSTNode<T>* tree) {if (tree == NULL)return NULL;while(tree->right != NULL)tree = tree->right;return tree; }template <class T> T BSTree<T>::maximum() {BSTNode<T> *p = maximum(mRoot);if (p != NULL)return p->key;return (T)NULL; }查找最小值的代碼
template <class T> BSTNode<T>* BSTree<T>::minimum(BSTNode<T>* tree) {if (tree == NULL)return NULL;while(tree->left != NULL)tree = tree->left;return tree; }template <class T> T BSTree<T>::minimum() {BSTNode<T> *p = minimum(mRoot);if (p != NULL)return p->key;return (T)NULL; }?
5. 前驅和后繼
節點的前驅：是該節點的左子樹中的最大節點。
節點的后繼：是該節點的右子樹中的最小節點。
查找前驅節點的代碼
查找后繼節點的代碼
6. 插入
插入節點的代碼
注：本文實現的二叉查找樹是允許插入相同鍵值的節點的。若想禁止二叉查找樹中插入相同鍵值的節點，可以參考"二叉查找樹(一)之 圖文解析 和 C語言的實現"中的插入函數進行修改。
?
7. 刪除
刪除節點的代碼
/* * 刪除結點(z)，并返回被刪除的結點** 參數說明：* tree 二叉樹的根結點* z 刪除的結點*/ template <class T> BSTNode<T>* BSTree<T>::remove(BSTNode<T>* &tree, BSTNode<T> *z) {BSTNode<T> *x=NULL;BSTNode<T> *y=NULL;if ((z->left == NULL) || (z->right == NULL) )y = z;elsey = successor(z);if (y->left != NULL)x = y->left;elsex = y->right;if (x != NULL)x->parent = y->parent;if (y->parent == NULL)tree = x;else if (y == y->parent->left)y->parent->left = x;elsey->parent->right = x;if (y != z) z->key = y->key;return y; }/* * 刪除結點(z)，并返回被刪除的結點** 參數說明：* tree 二叉樹的根結點* z 刪除的結點*/ template <class T> void BSTree<T>::remove(T key) {BSTNode<T> *z, *node; if ((z = search(mRoot, key)) != NULL)if ( (node = remove(mRoot, z)) != NULL)delete node; }?
8. 打印
打印二叉查找樹的代碼
/** 打印"二叉查找樹"** key -- 節點的鍵值 * direction -- 0，表示該節點是根節點;* -1，表示該節點是它的父結點的左孩子;* 1，表示該節點是它的父結點的右孩子。*/ template <class T> void BSTree<T>::print(BSTNode<T>* tree, T key, int direction) {if(tree != NULL){if(direction==0) // tree是根節點cout << setw(2) << tree->key << " is root" << endl;else // tree是分支節點cout << setw(2) << tree->key << " is " << setw(2) << key << "'s " << setw(12) << (direction==1?"right child" : "left child") << endl;print(tree->left, tree->key, -1);print(tree->right,tree->key, 1);} }template <class T> void BSTree<T>::print() {if (mRoot != NULL)print(mRoot, mRoot->key, 0); }?
9. 銷毀
銷毀二叉查找樹的代碼
/** 銷毀二叉樹*/ template <class T> void BSTree<T>::destroy(BSTNode<T>* &tree) {if (tree==NULL)return ;if (tree->left != NULL)return destroy(tree->left);if (tree->right != NULL)return destroy(tree->right);delete tree;tree=NULL; }template <class T> void BSTree<T>::destroy() {destroy(mRoot); }?
二叉查找樹的C++實現(完整源碼)
二叉查找樹的C++實現文件(BSTree.h)
?View Code二叉查找樹的C++測試程序(BSTreeTest.cpp)
?View Code關于二叉查找樹的C++實現有兩點需要補充說明的:
第1點：采用了STL模板。因此，二叉查找樹支持任意數據類型。
第2點：將二叉查找樹的"聲明"和"實現"都位于BSTree.h中。這是因為，在二叉查找樹的實現采用了模板；而C++編譯器不支持對模板的分離式編譯！
?
二叉查找樹的C++測試程序
上面的BSTreeTest.c是二叉查找樹樹的測試程序，運行結果如下：
== 依次添加: 1 5 4 3 2 6 == 前序遍歷: 1 5 4 3 2 6 == 中序遍歷: 1 2 3 4 5 6 == 后序遍歷: 2 3 4 6 5 1 == 最小值: 1 == 最大值: 6 == 樹的詳細信息: 1 is root5 is 1's right child4 is 5's left child3 is 4's left child2 is 3's left child6 is 5's right child== 刪除根節點: 3 == 中序遍歷: 1 2 4 5 6?
下面對測試程序的流程進行分析！
(01) 新建"二叉查找樹"root。
(02) 向二叉查找樹中依次插入1,5,4,3,2,6 。如下圖所示：
?
(03) 遍歷和查找
插入1,5,4,3,2,6之后，得到的二叉查找樹如下：
前序遍歷結果:?1 5 4 3 2 6?
中序遍歷結果:?1 2 3 4 5 6?
后序遍歷結果:?2 3 4 6 5 1?
最小值是1，而最大值是6。
?
(04) 刪除節點4。如下圖所示：
?
(05) 重新遍歷該二叉查找樹。
中序遍歷結果:?1 2 4 5 6
總結
以上是生活随笔為你收集整理的二叉查找树(二)之 C++的实现的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 二叉查找树(一)之 C语言的实现
- 下一篇： 九大排序算法总结