在计算机术语中,二叉搜索树又叫二叉查找树、二叉排序树。
二叉搜索树(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),当然,它们的内部实现肯定不止这一种数据结构,有兴趣的小伙伴可以看一下这些容器的源码。
如果博客中有什么不正确的地方,还请多多指点。如果觉得我写的不错,那么请点个赞支持我吧。
谢谢观看。。。