1. 二叉查找树
二叉查找树（Binary Search Tree），也称为二叉搜索树、有序二叉树（ordered binary tree）或排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树：
- 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
- 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
- 任意节点的左、右子树也分别为二叉查找树；
- 没有键值相等的节点。
2. 节点类
class BSTNode{
public:
int data;
BSTNode *left;
BSTNode *right;
BSTNode(int x):
data(x), left(NULL), right(NULL){}
};
在写代码的过程中发现有的类方法需要经常使用某节点的父节点，所以可以考虑在数据成员中添加父节点 BSTNode* parents ，本文是在BSTree的方法中添加了函数 BSTNode* BSTree::getParents(int value)
3. 二叉搜索树类
class BSTree{
public:
BSTNode *root;
BSTree():
root(NULL){}
~BSTree(){destory(root);}
// 是否为空
bool isEmpty();
// 深度
int depth(BSTNode *&proot);
// 节点数
int size(BSTNode *&proot);
// 叶子节点数
int leafsize(BSTNode *&proot);
// 前序遍历
void preOrder(BSTNode* &pRoot);
// 中序遍历
void inOrder(BSTNode* &pRoot);
// 后序遍历
void postOrder(BSTNode* &pRoot);
// 层序遍历
void levelOrder(BSTNode* &pRoot);
// 查找
bool search(int value);
// 插入
void insert(int value);
// 删除
void remove(int value);
// 寻找前驱节点
BSTNode* predecessor(int value);
// 寻找后继节点
BSTNode* successor(int value);
// 最小值
int minimum();
// 最大值
int maximum();
// 销毁BST
void destory(BSTNode *&proot);
private:
// 获取value节点的地址
BSTNode* getAddr(int value);
// 获取value父节点的地址
BSTNode* getParents(int value);
};
4. 主要方法
对于基本的方法，如深度、节点数、叶子节点数没什么难点；
对于三种遍历方法使用的是经典的递归方法；
对于BST的最大/最小值，主要记住最小值永远在根节点的最左边，最大值永远在根节点的最右边，只需要不停的向最左或最优遍历即可，直到空节点结束（最大最小值也可能是根节点）；
BST的难点可能就在节点删除的部分，以下图所示的树为对象，讲一下节点删除：
/*
* 62
* / \
* 58 88
* / / \
* 47 73 99
* / \ /
* 35 51 93
* / \ / \
* 29 37 49 56
* / / \
* 36 48 50
*
*/
被删除的节点可能是一下3种情况之一：
1. 叶子节点 2. 只含有左子树或只含有右子树的节点 3. 同时含有左右子树的节点
细分：
1. 叶子节点
1.1 树只含有一个节点,删除叶子节点
如果树只有一个节点，则该节点即是根节点又是叶节点，删除时需要将root置空
1.2 树含有至少2个节点,删除叶子节点
如图上的 29 36 73等，删除叶子节点对BST没有影响，删除即可，同时需要维护指针；
2. 仅有左或者右子树的节点
2.1 仅有左子树的节点，同时该节点是根节点
2.2 仅有左子树的节点，同时该节点非根节点
2.3 仅有右子树的节点，同时该节点是根节点
2.4 仅有右子树的节点，同时该节点非根节点
上述四种情况只需要将待删节点的左右孩子放到待删节点的位置即可，同时注意是不是需要维护根节点
3. 左右子树都有的节点
首先寻找待删节点的直接前驱，然后用直接前驱代替待删节点。如删除47，47的前驱是37，那么将37节点的数据复制到47节点，释放37，同时将35的右孩子指向36，原47节点的右子树不动。
以上具体细节见完整代码
5. 完整代码
#include<iostream>
#include<vector>
#include<queue>
using namespace std; class BSTNode{
public:
int data;
BSTNode *left;
BSTNode *right;
BSTNode(int x):
data(x), left(NULL), right(NULL){}
}; class BSTree{
public:
BSTNode *root;
BSTree():
root(NULL){}
~BSTree(){destory(root);} // 是否为空
bool isEmpty();
// 深度
int depth(BSTNode *&proot);
// 节点数
int size(BSTNode *&proot);
// 叶子节点数
int leafsize(BSTNode *&proot); // 前序遍历
void preOrder(BSTNode* &pRoot);
// 中序遍历
void inOrder(BSTNode* &pRoot);
// 后序遍历
void postOrder(BSTNode* &pRoot);
// 层序遍历
void levelOrder(BSTNode* &pRoot); // 查找
bool search(int value);
// 插入
void insert(int value);
// 删除
void remove(int value); // 寻找前驱节点
BSTNode* predecessor(int value);
// 寻找后继节点
BSTNode* successor(int value); // 最小值
int minimum();
// 最大值
int maximum(); // 销毁BST
void destory(BSTNode *&proot); private:
// 获取value节点的地址
BSTNode* getAddr(int value);
// 获取value父节点的地址
BSTNode* getParents(int value);
}; bool BSTree::isEmpty(){
return root==NULL;
} int BSTree::depth(BSTNode *&proot){
if(proot == NULL)
return ;
int left = depth(proot->left);
int right = depth(proot->right);
if(left > right)
return left + ;
else
return right + ;
} int BSTree::size(BSTNode *&proot){
if(proot == NULL)
return ;
int left = size(proot->left);
int right = size(proot->right);
return left + right + ;
} int BSTree::leafsize(BSTNode *&proot){
if(proot == NULL)
return ;
if(proot->left == NULL && proot->right == NULL)
return ;
int leftLeaf = leafsize(proot->left);
int rightLeaf = leafsize(proot->right);
return leftLeaf + rightLeaf;
} BSTNode* BSTree::getParents(int value){
if(BSTree::search(value) == true){
BSTNode* pRoot = root;
BSTNode* parents; // 用于存储value节点的父节点
while(pRoot->data!=value){
parents = pRoot;
if(pRoot->data > value)
pRoot = pRoot->left;
else
pRoot = pRoot->right;
}
if(pRoot == root){
//cout<<"the value is root of the tree, NO PARENTS."<<endl;
return NULL;
}
else
return parents;
}
else{
cout<<"the value is not in the tree."<<endl;
return NULL;
}
} BSTNode* BSTree::getAddr(int value){
if(BSTree::search(value) == true){
BSTNode* pRoot = root;
while(pRoot->data!=value){
if(pRoot->data > value)
pRoot = pRoot->left;
else
pRoot = pRoot->right;
}
return pRoot;
}
else{
cout<<"the value is not in the tree."<<endl;
return NULL;
}
} // 若value不在树内或者value没有前驱，返回null，否则，返回前驱节点地址
BSTNode* BSTree::predecessor(int value){
if(!search(value)){
cout<<"the value is not in the tree."<<endl;
return NULL;
}
else if(BSTree::minimum() == value){
cout<<"节点"<<value<<"没有前驱节点"<<endl;
return NULL;
}
else{
BSTNode* pRoot = getAddr(value);// 用于存储value节点的地址
BSTNode* parents = getParents(value); // 用于存储value的父节点地址
// 含左子树的节点
if(pRoot->left != NULL){
BSTNode* pre = pRoot->left;
while(pre->right != NULL){
pre = pre->right;
}
return pre;
}
//没有左子树的节点
else{
if(parents->right == pRoot)
return parents;
else if(parents->left == pRoot){
while(parents->data > value)
parents = getParents(parents->data);
return parents;
}
}
}
} // 若value不在树内或者value没有后继，返回null，否则，返回前后继节点地址
BSTNode* BSTree::successor(int value){
if(!search(value)){
cout<<"the value is not in the tree."<<endl;
return NULL;
}
else if(BSTree::maximum() == value){
cout<<"节点"<<value<<"没有后继节点"<<endl;
return NULL;
}
else{
BSTNode* pRoot = getAddr(value);// 用于存储value节点的地址
BSTNode* parents = getParents(value); // 用于存储value的父节点地址
// 含右子树的节点
if(pRoot->right != NULL){
BSTNode* pre = pRoot->right;
while(pre->left != NULL){
pre = pre->left;
}
return pre;
}
//没有右子树的节点
else{
if(parents->left == pRoot)
return parents;
else if(parents->right == pRoot){
while(parents->data < value)
parents = getParents(parents->data);
return parents;
}
}
}
} int BSTree::minimum(){
BSTNode* proot = root;
while(proot->left != NULL){
proot = proot->left;
}
return proot->data;
} int BSTree::maximum(){
BSTNode* proot = root;
while(proot->right != NULL){
proot = proot->right;
}
return proot->data;
} /*
* 62
* / \
* 58 88
* / / \
* 47 73 99
* / \ /
* 35 51 93
* / \ / \
* 29 37 49 56
* / / \
* 36 48 50
*
* 删除节点的3种情况：
* 1. 叶子节点
* 1.1 树只含有一个节点,删除叶子节点
* 1.2 树含有至少2个节点,删除叶子节点
* 2. 仅有左或者右子树的节点
* 2.1 仅有左子树的节点，删除根节点
* 2.2 仅有左子树的节点，删除非根节点
* 2.3 仅有右子树的节点，删除根节点
* 2.4 仅有右子树的节点，删除非根节点
* 3. 左右子树都有的节点
*
*/ void BSTree::remove(int value){
if(!search(value)){
cout<<"the value is not in the tree. please check."<<endl;
return ;
}
else{
// 查找value节点
BSTNode* pRoot = getAddr(value);// 用于存储value节点的地址
BSTNode* parents = getParents(value); // 用于存储待删除节点的父节点
// 删除value节点
// 1.叶节点
// 1.1 树只含有一个节点
if(pRoot == root && pRoot->left == NULL && pRoot->right == NULL){
root = NULL;
free(pRoot);
}
// 1.2 树含有至少2个节点
else if(pRoot != root && pRoot->left == NULL && pRoot->right == NULL){
// 待删节点是父节点的右孩子
if(parents->right != NULL && parents->right->data == value){
parents->right = NULL;
free(pRoot);
}
// 待删节点是父节点的左孩子
else{
parents->left = NULL;
free(pRoot);
}
}
// 2. 仅有左子树或右子树的节点
// 2.1 仅有左子树，且删除根节点
else if(pRoot == root && pRoot->left != NULL && pRoot->right == NULL){
root = pRoot->left;
free(pRoot);
}
// 2.2 仅有左子树的节点，删除非根节点
else if(pRoot != root && pRoot->left != NULL && pRoot->right == NULL){
// 待删节点是父节点的右孩子
if(parents->right != NULL && parents->right->data == value){
parents->right = pRoot->left;
free(pRoot);
}
// 待删节点是父节点的左孩子
else{
parents->left = pRoot->left;
free(pRoot);
}
}
// 2.3 仅有右子树的节点，删除根节点
else if(pRoot == root && pRoot->left == NULL && pRoot->right != NULL){
root = pRoot->right;
free(pRoot);
}
// 2.4 仅有右子树的节点， 删除非根节点
else if(pRoot != root && pRoot->left == NULL && pRoot->right != NULL){
// 待删节点是父节点的右孩子
if(parents->right != NULL && parents->right->data == value){
parents->right = pRoot->right;
free(pRoot);
}
// 待删节点是父节点的左孩子
else{
parents->left = pRoot->right;
free(pRoot);
}
}
// 3. 左右子树都有的节点
else{
// 寻找待删除节点的直接前驱
BSTNode* pre = predecessor(value);// pre存储直接前驱
pRoot->data = pre->data;// 数据覆盖
// 寻找直接前驱的左/右节点
if(pre->right != NULL){
BSTNode *pRootNext = pRoot->right;
BSTNode *temp = pre->right;
if(pre == pRootNext)
pRoot->right = temp;
else
pRootNext->left = temp;
free(pre);
}
else if(pre->left != NULL){
BSTNode *pRootNext = pRoot->left;
BSTNode *temp = pre->left;
if(pre == pRootNext)
pRoot->left = temp;
else
pRootNext->right = temp;
free(pre);
}
else if(pre->left == NULL && pre->right == NULL){
pRoot->left = NULL;
free(pre);
}
}
}
} bool BSTree::search(int value){
BSTNode* pRoot = root;
while(pRoot!=NULL && pRoot->data!=value){
if(pRoot->data > value)
pRoot = pRoot->left;
else
pRoot = pRoot->right;
}
if(pRoot == NULL)
return false;
else
return true;
} void BSTree::insert(int value){
// value节点已经存在
if(BSTree::search(value) == true){
cout<<"the value "<<value<<" in the tree already."<<endl;
return ;
}
// value节点不存在
else{
BSTNode* pRoot = root;
// 空树
if(pRoot == NULL)
root = new BSTNode(value);
// 非空
else{
BSTNode* temp;
while(pRoot!= NULL && pRoot->data!=value){
temp = pRoot;
if(pRoot->data > value)
pRoot = pRoot->left;
else
pRoot = pRoot->right;
}
pRoot = temp;
if(pRoot->data>value)
pRoot->left = new BSTNode(value);
else
pRoot->right = new BSTNode(value);
}
}
cout<<"the value "<<value<<" is inserted."<<endl;
} void BSTree::preOrder(BSTNode* &pRoot){
if(pRoot == NULL)
return ;
cout<<pRoot->data<<' ';
preOrder(pRoot->left);
preOrder(pRoot->right);
} void BSTree::inOrder(BSTNode* &pRoot){
if(pRoot == NULL)
return ;
inOrder(pRoot->left);
cout<<pRoot->data<<' ';
inOrder(pRoot->right);
} void BSTree::postOrder(BSTNode* &pRoot){
if(pRoot == NULL)
return ;
postOrder(pRoot->left);
postOrder(pRoot->right);
cout<<pRoot->data<<' ';
} void BSTree::levelOrder(BSTNode *&pRoot){
queue<BSTNode*> p;
if(pRoot == NULL)
return ;
p.push(pRoot);
while (!p.empty()){
BSTNode *temp = p.front();
cout<<temp->data<<' ';
p.pop();
if(temp->left)
p.push(temp->left);
if(temp->right)
p.push(temp->right);
}
} void BSTree::destory(BSTNode *&proot){
if (proot== NULL)
return ;
destory(proot->left);
destory(proot->right);
cout<<"free value "<<proot->data<<endl;
free(proot);
proot = NULL;
} int main(int argc, char const *argv[])
{
BSTree tree;
int arr[] = {, , , , ,
, , , , ,
, , , , , };
for(int i=; i<; i++)
tree.insert(arr[i]); cout<<"前序遍历: ";
tree.preOrder(tree.root);
cout<<endl;
cout<<"中序遍历: ";
tree.inOrder(tree.root);
cout<<endl;
cout<<"最小值: "<<tree.minimum()<<endl;
cout<<"最大值: "<<tree.maximum()<<endl; cout<<"深度: "<<tree.depth(tree.root)<<endl;
cout<<"节点数: "<<tree.size(tree.root)<<endl;
cout<<"叶子节点数: "<<tree.leafsize(tree.root)<<endl; int index = ;
BSTNode *pre = tree.predecessor(arr[index]);
if(pre != NULL)
cout<<"节点"<<arr[index]<<"的前驱节点是"<<pre->data<<endl; BSTNode *suc = tree.successor(arr[index]);
if(suc != NULL)
cout<<"节点"<<arr[index]<<"的后继节点是"<<suc->data<<endl; cout<<"删除节点: "<<arr[index]<<endl;
tree.remove(arr[index]); cout<<"前序遍历: ";
tree.preOrder(tree.root);
cout<<endl;
cout<<"中序遍历: ";
tree.inOrder(tree.root);
cout<<endl; tree.destory(tree.root);
return ;
}
6. 运行结果
6.1 测试使用的二叉搜索树
/*
* 62
* / \
* 58 88
* / / \
* 47 73 99
* / \ /
* 35 51 93
* / \ / \
* 29 37 49 56
* / / \
* 36 48 50
*
*/
6.2 运行结果
the value is inserted.
the value is inserted.
the value is inserted.
the value is inserted.
the value is inserted.
the value is inserted.
the value is inserted.
the value is inserted.
the value is inserted.
the value is inserted.
the value is inserted.
the value is inserted.
the value is inserted.
the value is inserted.
the value is inserted.
the value is inserted.
前序遍历:
中序遍历:
最小值:
最大值:
深度:
节点数:
叶子节点数:
节点47的前驱节点是37
节点47的后继节点是48
删除节点:
前序遍历:
中序遍历:
free value
free value
free value
free value
free value
free value
free value
free value
free value
free value
free value
free value
free value
free value
free value
[Finished in .1s]