二叉搜索树
在计算机术语中，二叉搜索树又叫二叉查找树、二叉排序树。
二叉搜索树（Binary Search Tree）的定义： 它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉搜索树。 这个是百度百科上的一个定义，个人认为还是比较易懂的，简单点来说二叉搜索树就是要么是一个空空树，要么是一棵二叉树，如果存在左子树，那么左子树上的所有节点的值都小于根节点的值，如果存在右子树，那么右子树的所有节点的值都大于根节点的值，并且左右子树都是二叉搜索树。 好吧，不管我解释的清不清楚，下面来看一张图就知道了：
这里写图片描述
一个典型的二叉搜索树。对照定义看看就很清楚了，那么，问题来了，怎么构造二叉搜索树呢？根据定义，我们应该能猜出个大概：比较当前节点，如果小于当前节点的值，那么对左子树进行比较，如果大于，那么对右子树进行比较。 下面给出代码：
void insert(int n) { // 插入一个节点值为 n 的新节点
if(!root) { // 如果根节点为空，那么新建一个节点作为根节点
root = new Node;
root->parent = root->left = root->right = NULL;
root->key = n;
return ;
}
Node *now = root;
Node *parent = NULL;
while(now) {
parent = now;
if(n < now->key) { // 如果要寻找的值小于当前节点的值，那么插入到左节点
now = now->left;
} else if(n > now->key) { // 如果要寻找的值大于当前节点的值，那么插入到右节点
now = now->right;
} else { // 如果等于那么证明二叉搜索树中存在这个值的节点
return ;
}
}
now = new Node;
now->parent = parent;
now->left = NULL;
now->right = NULL;
now->key = n; // 新建一个节点并且对其赋值
if(n < parent->key) { // 新建的节点作为左子节点或者右子节点
parent->left = now;
} else {
parent->right = now;
}
}那么对二叉搜索树中的节点值进行搜索呢？这个跟插入是差不多的，分别搜索当前节点、左右子树、直到找到或者没找到，返回对应的值：
// 查找节点值为 n 的节点并且返回（没找到返回NULL）
Node *find(int n) {
Node *now = root;
while(now) {
if(now->key == n) { // 等于则直接返回这个节点
return now;
}
else if(now->key > n) { // 小于则找左节点
now = now->left;
} else { // 大于则找右节点
now = now->right;
}
}
return NULL; // 如果没找到返回 NULL
}如果要对二叉搜索树中的节点节点值进行删除呢？其实核心思想也是对节点的值进行寻找，如果找到了就删除这个节点并且连接对应节点，那么怎么确定这个“对应节点”呢？我们要注意定义中说明的：一个二叉搜索树的左右子树也是二叉搜索树（如果存在）。这里我们可以使用这个节点的左子树中的“最大值”所在的节点或者这个节点的右子树中的“最小值”所在的节点来代替这个要删除的节点的位置。但是这里要注意的是要删除的节点的情况：没有子节点、只有一个节点、有两个节点，我们要对这三种情况都要考虑到并进行对应的处理，下面在代码中说明：
// 删除节点值为 n 的节点，成功就返回 true，否则返回 false
bool erase(int n) {
Node *now = root;
Node *find = NULL; // 代替要删除的节点的位置的节点
while(now) {
if(now->key == n) { // 如果找到这个值所在节点
if(now->left) { // 如果左子树不为空
find = now->left; // 找到左子树
// 寻找左子树中值最大的节点(最右边的)
while(find->right) {
find = find->right;
}
} else if(now->right) { // 如果右子树不为空
find = now->right; // 找到右子树
// 寻找右子树中值最小的节点(最左边的)
while(find->left) {
find = find->left;
}
}
if(now->parent) { // 如果这个节点有父节点
if(now->parent->left == now) {
now->parent->left = find;
} else {
now->parent->right = find;
}
}
if(find) { // 如果删除的节点是叶子节点（无左右子树），那么要考虑 find 是否为空
find->parent = now->parent; // 替换节点内容
}
if(root == now) { // 如果删除的是根结点
root = find;
}
if(now->left == find) { // 连接 find 节点和 now 的另外一个子节点
find->right = now->right;
find->right->parent = find;
} else {
find->left = now->left;
find->left->parent = find;
}
delete now;
now = NULL;
return true; // 找到值并且删除成功返回 true
} else if(now->key > n) {
now = now->left;
} else {
now = now->right;
}
}
return false; // 没删除成功返回 false
}Ok，基本原理和操作都讲完了，下面上完整代码：
#include <iostream>
using namespace std;
struct Node { // 储存二叉树节点信息的结构体
struct Node *parent;
struct Node *left;
struct Node *right;
int key;
};
Node *root = NULL;
void insert(int n) { // 插入一个节点值为 n 的新节点
if(!root) { // 如果根节点为空，那么新建一个节点作为根节点
root = new Node;
root->parent = root->left = root->right = NULL;
root->key = n;
return ;
}
Node *now = root;
Node *parent = NULL;
while(now) {
parent = now;
if(n < now->key) { // 如果要寻找的值小于当前节点的值，那么插入到左节点
now = now->left;
} else if(n > now->key) { // 如果要寻找的值大于当前节点的值，那么插入到右节点
now = now->right;
} else { // 如果等于那么证明二叉搜索树中存在这个值的节点
return ;
}
}
now = new Node;
now->parent = parent;
now->left = NULL;
now->right = NULL;
now->key = n; // 新建一个节点并且对其赋值
if(n < parent->key) { // 新建的节点作为左子节点或者右子节点
parent->left = now;
} else {
parent->right = now;
}
}
// 删除节点值为 n 的节点，成功就返回 true，否则返回 false
bool erase(int n) {
Node *now = root;
Node *find = NULL; // 代替要删除的节点的位置的节点
while(now) {
if(now->key == n) { // 如果找到这个值所在节点
if(now->left) { // 如果左子树不为空
find = now->left; // 找到左子树
// 寻找左子树中值最大的节点(最右边的)
while(find->right) {
find = find->right;
}
} else if(now->right) { // 如果右子树不为空
find = now->right; // 找到右子树
// 寻找右子树中值最小的节点(最左边的)
while(find->left) {
find = find->left;
}
}
if(now->parent) { // 如果这个节点有父节点
if(now->parent->left == now) {
now->parent->left = find;
} else {
now->parent->right = find;
}
}
if(find) { // 如果删除的节点是叶子节点（无左右子树），那么要考虑 find 是否为空
find->parent = now->parent; // 替换节点内容
}
if(root == now) { // 如果删除的是根结点
root = find;
}
if(now->left == find) { // 连接 find 节点和 now 的另外一个子节点
find->right = now->right;
find->right->parent = find;
} else {
find->left = now->left;
find->left->parent = find;
}
delete now;
now = NULL;
return true; // 找到值并且删除成功返回 true
} else if(now->key > n) {
now = now->left;
} else {
now = now->right;
}
}
return false; // 没删除成功返回 false
}
// 查找节点值为 n 的节点并且返回（没找到返回NULL）
Node *find(int n) {
Node *now = root;
while(now) {
if(now->key == n) { // 等于则直接返回这个节点
return now;
}
else if(now->key > n) { // 小于则找左节点
now = now->left;
} else { // 大于则找右节点
now = now->right;
}
}
return NULL; // 如果没找到返回 NULL
}
void inOrder(Node *now) { // 中序遍历，即为从小到大输出节点值
if(now) {
inOrder(now->left);
cout << now->key << " ";
inOrder(now->right);
}
}
int main() {
int n, key;
cin >> n;
for(int i = 0; i < n; i++) {
cin >> key;
insert(key);
}
cout << "当前二叉搜索树：" << endl;
inOrder(root);
cout << endl << "输入要删除的值：" << endl;
cin >> key;
if(erase(key)) {
cout << "删除成功" << endl;
} else {
cout << "删除失败" << endl;
}
cout << "当前二叉搜索树：" << endl;
inOrder(root);
cout << endl << "输入要查找的值：";
cin >> key;
Node *f = find(key);
if(f) {
cout << "找到节点的值：";
cout << f->key << endl;
} else {
cout << "没找到该节点！" << endl;
}
return 0;
} 运行结果：
这里写图片描述
对于测试数据，和我们的预期结果还是一样的。小伙伴们有兴趣可以试试别的数据检测一下。这里提一下，二叉搜索树这种数据结构被广泛应用于 C++ STL 中的一些容器中（set、map），当然，它们的内部实现肯定不止这一种数据结构，有兴趣的小伙伴可以看一下这些容器的源码。
如果博客中有什么不正确的地方，还请多多指点。如果觉得我写的不错，那么请点个赞支持我吧。
谢谢观看。。。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017年03月19日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读