一、二叉搜索树概览
二叉搜索树（又名二叉查找树、二叉排序树）是一种可提供良好搜寻效率的树形结构，支持动态集合操作，所谓动态集合操作，就是Search、Maximum、Minimum、Insert、Delete等操作，二叉搜索树可以保证这些操作在对数时间内完成。当然，在最坏情况下，即所有节点形成一种链式树结构，则需要O(n)时间。这就说明，针对这些动态集合操作，二叉搜索树还有改进的空间，即确保最坏情况下所有操作在对数时间内完成。这样的改进结构有AVL(Adelson-Velskii-Landis) tree、RB（红黑）tree和AA-tree。AVL树和红黑树相对应用较多，我们在后面的章节中在做整理。
在二叉搜索树中，任何一个节点的键值一定大于其左子树中的每一个节点的键值，并小于其右子树中每一个节点的键值。我们结合书本的理论对二叉搜索树的动态集合操作做编程实现。其中除了Delete操作稍稍复杂之外，其余的操作都是非常简单的。
二、二叉搜索树动态集合操作
1、查询二叉搜索树
查询包括查找某一个元素，查找最大、最小关键字元素，查找前驱和后继，根据二叉搜索树的性质：左子树 < 根 < 右子树，这样的操作很容易实现。如下：
查找某元素：
1 //@brief 查找元素 2 //@return 是否查找成功 3 bool BinarySearchTree::Search(const int search_value) const 4 { 5 return _Search(m_pRoot, search_value) != NULL; 6 } 7 8 //@brief 真正的查找操作 9 //非递归查找 10 BinarySearchTree::_Node * BinarySearchTree::_Search(_Node *node, const int search_value) const 11 { 12 //递归 13 // if (node == NULL || search_value = node->m_nValue) 14 // return node; 15 // if (search_value < node->m_nValue) 16 // return _Search(node->m_pLeft); 17 // else 18 // return _Search(node->m_pRight); 19 20 //非递归 21 while(node && search_value != node->m_nValue) { 22 if (search_value < node->m_nValue) 23 node = node->m_pLeft; 24 else 25 node = node->m_pRight; 26 } 27 return node; 28 }
查找最大、最小关键字元素：
1 //@brief 得到以node为根节点的子树中的最大关键字节点 2 BinarySearchTree::_Node * BinarySearchTree::_GetMaximum(_Node *node) const 3 { 4 while(node->m_pRight) { 5 node = node->m_pRight; 6 } 7 return node; 8 } 9 10 //@brief 得到以node为根节点的子树中的最小关键字节点 11 BinarySearchTree::_Node * BinarySearchTree::_GetMinimum(_Node *node) const 12 { 13 while(node->m_pLeft) { 14 node = node->m_pLeft; 15 } 16 return node; 17 }
查找前驱和后继：
1 //@brief 得到一个同时存在左右子树的节点node的前驱 2 BinarySearchTree::_Node * BinarySearchTree::_GetPredecessor(_Node *node) const 3 { 4 if (node->m_pLeft) 5 return _GetMinimum(node); 6 7 _Node *pTemp = node->m_pParent; 8 while (pTemp && node == pTemp->m_pLeft) { 9 node = pTemp; 10 pTemp = pTemp->m_pParent; 11 } 12 return pTemp; 13 } 14 15 //@brief 得到一个同时存在左右子树的节点node的后继 16 BinarySearchTree::_Node * BinarySearchTree::_GetSuccessor(_Node *node) const 17 { 18 if(node->m_pRight) 19 return _GetMaximum(node); 20 21 _Node *pTemp = node->m_pParent; 22 while (pTemp && node == pTemp->m_pRight ) { 23 node = pTemp; 24 pTemp = pTemp->m_pParent; 25 } 26 return pTemp; 27 }
2、插入和删除
插入操作：通过不断的遍历，找到待插入元素应该处的位置，即可进行插入，代码如下：包括递归和非递归的版本：
1 //@brief 插入元素 2 //@return 是否插入成功 3 bool BinarySearchTree::Insert(const int new_value) 4 { 5 //非递归 6 if (Search(new_value)) 7 return false; 8 9 _Node *pTemp = NULL; 10 _Node *pCurrent = m_pRoot; 11 while ( pCurrent ) { 12 pTemp = pCurrent; 13 if ( new_value < pCurrent->m_nValue ) 14 pCurrent = pCurrent->m_pLeft; 15 else 16 pCurrent = pCurrent->m_pRight; 17 18 } 19 _Node *pInsert = new _Node(); 20 pInsert->m_nValue = new_value; 21 pInsert->m_pParent = pTemp; 22 23 if ( !pTemp ) //空树 24 m_pRoot = pInsert; 25 else if ( new_value < pTemp->m_nValue ) 26 pTemp->m_pLeft = pInsert; 27 else 28 pTemp->m_pRight = pInsert; 29 return true; 30 } 31 32 //递归 33 BinarySearchTree::_Node * BinarySearchTree::Insert_Recur(_Node *&node, const int new_value) 34 { 35 if ( node == NULL ) { 36 _Node *pInsert = new _Node(); 37 pInsert->m_nValue = new_value; 38 node = pInsert; 39 } 40 else if ( new_value < node->m_nValue ) 41 node->m_pLeft = Insert_Recur( node->m_pLeft, new_value ); 42 else 43 node->m_pRight = Insert_Recur( node->m_pRight, new_value ); 44 return node; 45 }
删除操作：有点小复杂，总共分为四种情况：
1）如果待删除节点没有子节点，则直接删除即可，并更改其父节点的指向；
2）如果待删除的节点只有一个子节点，其中，如果为左子树节点，则用左子树节点替换之；反之用右子树节点替换之；
3）如果待删除节点 z 有两个子节点，这个时候分两种情况考虑，第一种情况：z 的后继即为 z 的右孩子节点，则将 z 的有孩子节点替换之；
4）第二种情况： z 的后继不是 z 的有孩子节点，则首先用 z 的后继的有孩子节点替换 z 的后继，再用 z 的后继替换 z 。
没有图形作为辅助，实属难以表述和透彻理解，详细的过程和分析见书本上。
注意：在《算法导论》前几版的实现中，该过程的实现略有不同，相较上面这个过程，要简单一些，做法是：不是用 z 的后继 y 替换节点 z，而是删除节点 y，但复制 y 的关键字到节点 z 中来实现。但是这种做法，作者在最新这一版中明确提出，那种方法的缺陷是：会造成实际被删除的节点并不是被传递到删除过程中的那个节点，会有一些已删除节点的“过时”指针带来不必要的影响，总之复制删除的方法不是好的。
另外，还有一点是：这里 y 可以选择作为 z 的后继，也可以作为 z 的前驱。有意思的是，习题12.3-6提出一种为两者分配公平策略的机制，来实现较好的性能。何为公平策略，譬如下面图示所示：
左图右子树高度大于左子树，应选择后继替换待删除节点；右图则相反，应选择前驱；这里的公平策略的宗旨就是为了在实现动态集合操作的时候尽可能使树的高度维持在一个较低的高度。
代码实现如下：
//@brief 删除元素 //@return 是否删除成功 bool BinarySearchTree::Delete(const int delete_value) { _Node *delete_node = _Search(m_pRoot, delete_value); //未找到该节点 if (!delete_node) return false; else { _DeleteNode(delete_node); return true; } } //@brief 真正的删除操作 void BinarySearchTree::_DeleteNode(_Node *delete_node) { if (delete_node->m_pLeft == NULL) _Delete_Transplant(delete_node, delete_node->m_pRight); else if (delete_node->m_pRight == NULL) _Delete_Transplant(delete_node, delete_node->m_pLeft); else { _Node *min_node = _GetMinimum(delete_node->m_pRight); if (min_node->m_pParent != delete_node) { _Delete_Transplant(min_node, min_node->m_pRight); min_node->m_pRight = delete_node->m_pRight; min_node->m_pRight->m_pParent = min_node; } _Delete_Transplant(delete_node, min_node); min_node->m_pLeft = delete_node->m_pLeft; min_node->m_pLeft->m_pParent = min_node; } } void BinarySearchTree::_Delete_Transplant(_Node *unode, _Node *vnode) { if (unode->m_pParent == NULL) m_pRoot = vnode; else if (unode == unode->m_pParent->m_pLeft) unode->m_pParent->m_pLeft = vnode; else unode->m_pParent->m_pRight = vnode; if (vnode) vnode->m_pParent = unode->m_pParent; }
这里增加了一个函数Transplant()来实现替换操作，使代码较简洁。
完整的代码如下：
//BinarySearchTree.h #ifndef _BINARY_SEARCH_TREE_ #define _BINARY_SEARCH_TREE_ class BinarySearchTree { private: struct _Node { int m_nValue; _Node *m_pParent; _Node *m_pLeft; _Node *m_pRight; }; public: BinarySearchTree(_Node *pRoot = NULL):m_pRoot(pRoot){} ~BinarySearchTree(); //@brief 插入元素 //@return 是否插入成功 bool Insert(const int new_value); //递归 _Node * Insert_Recur(_Node *&node, const int new_value); //@brief 删除元素 //@return 是否删除成功 bool Delete(const int delete_value); //@brief 查找元素 //@return 是否查找成功 bool Search(const int search_value) const; //@brief 使用dot描述当前二叉查找树 void Display() const; //@brief 树的遍历 void Inorder() const {Inorder_Tree_Walk(m_pRoot);} void Preorder() const {Preorder_Tree_Walk(m_pRoot);} void Postorder() const {Postorder_Tree_Walk(m_pRoot);} private: //@brief 真正的删除操作 void _DeleteNode(_Node *delete_node); void _Delete_Transplant(_Node *unode, _Node *vnode); //@brief 得到以node为根节点的子树中的最大关键字节点 _Node * _GetMaximum(_Node *node) const; //@brief 得到以node为根节点的子树中的最小关键字节点 _Node * _GetMinimum(_Node *node) const; //@brief 得到一个同时存在左右子树的节点node的前驱 _Node * _GetPredecessor(_Node *node) const; //@brief 得到一个同时存在左右子树的节点node的后继 _Node * _GetSuccessor(_Node *node) const; //@brief 真正的查找操作 //非递归查找 _Node * _Search(_Node *node, const int search_value) const; //@brief 显示一棵二叉搜索树 void _Display(/*iostream &ss, */_Node *node) const; //@brief 递归释放节点 void _RecursiveReleaseNode(_Node *node); void ShowGraphvizViaDot(const string &dot) const; //@brief 树的遍历 void Inorder_Tree_Walk(_Node *node) const; void Preorder_Tree_Walk(_Node *node) const; void Postorder_Tree_Walk(_Node *node) const; private: _Node *m_pRoot; }; #endif//_BINARY_SEARCH_TREE_ //BinarySearchTree.cpp #include <iostream> #include <string> #include <iomanip> #include <ctime> using namespace std; #include "BinarySearchTree.h" BinarySearchTree::~BinarySearchTree() { _RecursiveReleaseNode(m_pRoot); } //@brief 插入元素 //@return 是否插入成功 bool BinarySearchTree::Insert(const int new_value) { //非递归 if (Search(new_value)) return false; _Node *pTemp = NULL; _Node *pCurrent = m_pRoot; while ( pCurrent ) { pTemp = pCurrent; if ( new_value < pCurrent->m_nValue ) pCurrent = pCurrent->m_pLeft; else pCurrent = pCurrent->m_pRight; } _Node *pInsert = new _Node(); pInsert->m_nValue = new_value; pInsert->m_pParent = pTemp; if ( !pTemp ) //空树 m_pRoot = pInsert; else if ( new_value < pTemp->m_nValue ) pTemp->m_pLeft = pInsert; else pTemp->m_pRight = pInsert; return true; // //该元素已经存在 // if (Search(new_value)) // return false; // // //空树，插入第1个节点 // if (!m_pRoot) { // m_pRoot = new _Node(); // m_pRoot->m_nValue = new_value; // return true; // } // // //非第一个节点 // _Node *current_node = m_pRoot; // while( current_node ) { // _Node *&next_node_pointer = (new_value < current_node->m_nValue ? current_node->m_pLeft:current_node->m_pRight); // if ( next_node_pointer ) // current_node = next_node_pointer; // else { // next_node_pointer = new _Node(); // next_node_pointer->m_nValue = new_value; // next_node_pointer->m_pParent = current_node; // break; // } // } // return true; } //递归 BinarySearchTree::_Node * BinarySearchTree::Insert_Recur(_Node *&node, const int new_value) { if ( node == NULL ) { _Node *pInsert = new _Node(); pInsert->m_nValue = new_value; node = pInsert; } else if ( new_value < node->m_nValue ) node->m_pLeft = Insert_Recur( node->m_pLeft, new_value ); else node->m_pRight = Insert_Recur( node->m_pRight, new_value ); return node; } //@brief 删除元素 //@return 是否删除成功 bool BinarySearchTree::Delete(const int delete_value) { _Node *delete_node = _Search(m_pRoot, delete_value); //未找到该节点 if (!delete_node) return false; else { _DeleteNode(delete_node); return true; } } //@brief 查找元素 //@return 是否查找成功 bool BinarySearchTree::Search(const int search_value) const { return _Search(m_pRoot, search_value) != NULL; } //@brief 使用dot描述当前二叉查找树 void BinarySearchTree::Display() const { _Display(m_pRoot); } //@brief 树的遍历 //中序 void BinarySearchTree::Inorder_Tree_Walk(_Node *node) const { if (node) { Inorder_Tree_Walk(node->m_pLeft); cout << node->m_nValue << " "; Inorder_Tree_Walk(node->m_pRight); } } //前序 void BinarySearchTree::Preorder_Tree_Walk(_Node *node) const { if (node) { cout << node->m_nValue << " "; Preorder_Tree_Walk(node->m_pLeft); Preorder_Tree_Walk(node->m_pRight); } } //后序 void BinarySearchTree::Postorder_Tree_Walk(_Node *node) const { if (node) { Postorder_Tree_Walk(node->m_pLeft); Postorder_Tree_Walk(node->m_pRight); cout << node->m_nValue << " "; } } //@brief 真正的删除操作 void BinarySearchTree::_DeleteNode(_Node *delete_node) { if (delete_node->m_pLeft == NULL) _Delete_Transplant(delete_node, delete_node->m_pRight); else if (delete_node->m_pRight == NULL) _Delete_Transplant(delete_node, delete_node->m_pLeft); else { _Node *min_node = _GetMinimum(delete_node->m_pRight); if (min_node->m_pParent != delete_node) { _Delete_Transplant(min_node, min_node->m_pRight); min_node->m_pRight = delete_node->m_pRight; min_node->m_pRight->m_pParent = min_node; } _Delete_Transplant(delete_node, min_node); min_node->m_pLeft = delete_node->m_pLeft; min_node->m_pLeft->m_pParent = min_node; } } void BinarySearchTree::_Delete_Transplant(_Node *unode, _Node *vnode) { if (unode->m_pParent == NULL) m_pRoot = vnode; else if (unode == unode->m_pParent->m_pLeft) unode->m_pParent->m_pLeft = vnode; else unode->m_pParent->m_pRight = vnode; if (vnode) vnode->m_pParent = unode->m_pParent; } //@brief 得到以node为根节点的子树中的最大关键字节点 BinarySearchTree::_Node * BinarySearchTree::_GetMaximum(_Node *node) const { while(node->m_pRight) { node = node->m_pRight; } return node; } //@brief 得到以node为根节点的子树中的最小关键字节点 BinarySearchTree::_Node * BinarySearchTree::_GetMinimum(_Node *node) const { while(node->m_pLeft) { node = node->m_pLeft; } return node; } //@brief 得到一个同时存在左右子树的节点node的前驱 BinarySearchTree::_Node * BinarySearchTree::_GetPredecessor(_Node *node) const { if (node->m_pLeft) return _GetMinimum(node); _Node *pTemp = node->m_pParent; while (pTemp && node == pTemp->m_pLeft) { node = pTemp; pTemp = pTemp->m_pParent; } return pTemp; } //@brief 得到一个同时存在左右子树的节点node的后继 BinarySearchTree::_Node * BinarySearchTree::_GetSuccessor(_Node *node) const { if(node->m_pRight) return _GetMaximum(node); _Node *pTemp = node->m_pParent; while (pTemp && node == pTemp->m_pRight ) { node = pTemp; pTemp = pTemp->m_pParent; } return pTemp; } //@brief 真正的查找操作 //非递归查找 BinarySearchTree::_Node * BinarySearchTree::_Search(_Node *node, const int search_value) const { //递归 // if (node == NULL || search_value = node->m_nValue) // return node; // if (search_value < node->m_nValue) // return _Search(node->m_pLeft); // else // return _Search(node->m_pRight); //非递归 while(node && search_value != node->m_nValue) { if (search_value < node->m_nValue) node = node->m_pLeft; else node = node->m_pRight; } return node; } //@brief 显示一棵二叉搜索树 void BinarySearchTree::_Display(/*iostream &ss, */_Node *node) const { if ( node ) { cout << node->m_nValue << " "; if ( node->m_pLeft ) { _Display( node->m_pLeft ); } if ( node->m_pRight ) { _Display( node->m_pRight ); } } } //@brief 递归释放节点 void BinarySearchTree::_RecursiveReleaseNode(_Node *node) { if (node) { _RecursiveReleaseNode(node->m_pLeft); _RecursiveReleaseNode(node->m_pRight); delete node; } } int main() { srand((unsigned)time(NULL)); BinarySearchTree bst; //用随机值生成一棵二叉查找树 for (int i= 0; i < 10; i ++) { bst.Insert( rand() % 100 ); } bst.Display(); cout << endl; //中序遍历 // bst.Inorder(); // cout << endl; //删除所有的奇数值结点 for ( int i = 1; i < 100; i += 2 ) { if( bst.Delete( i ) ) { cout << "### Deleted [" << i << "] ###" << endl; } } //验证删除的交换性 // bst.Delete(2); // bst.Delete(1); // bst.Display(); // cout << endl; //查找100以内的数，如果在二叉查找树中，则显示 cout << endl; for ( int i = 0; i < 10; i += 1 ) { if ( bst.Search( i ) ) { cout << "搜索[" << i << "]元素：\t成功" << endl; } } cout << endl; //中序遍历 bst.Inorder(); return 0; }