前言
本文将用C/C++实现二叉搜索树的基本操作：插入、搜索、删除，以及详细的原理介绍。
二叉搜索树
二叉搜索树是基于二叉树的一种更加有利于搜索的简单数据结构。其实，相比于二叉树来说，他的数据更具有规律，简单的来说一个节点的左节点小于该节点，右节点则大于它。
一个节点的示意
有了这个概念，那么我们构建二叉搜索树将会变得异常简单。
构建
先写个节点吧。
typedef struct Node
{
int data;
Node *pLeft;
Node *pRight;
} Node;
这样，名为Node的节点便被定义好了。
为了方便储存root节点，那就再定义一个Tree，专门来储存root节点吧。
typedef struct Node *Tree;
构建树的关键就在元素的插入上，所以我们来写一个插入函数。
Node *createNode(int data) // 初始化一个节点
{
Node *n = (Node*) malloc(sizeof(Node));
n -> data = data;
n -> pLeft = NULL;
n -> pRight = NULL;
return n;
}
void insert(int data, Tree *tree) // 向一棵树中插入数据
{
if (*tree == NULL) // 如果树是空的，那就直接创建节点
{
*tree = createNode(data); // 创建节点
} else {
Node *current = *tree; // 记录当前遍历到的节点
while (1) // 其实也能用递归写，但是循环比较好理解
{
if (data >= current -> data) { // 如果待插入的数据比已存在的数据大
if (current -> pRight != NULL) current = current -> pRight; // 如果已存在数据，那就继续往下遍历吧
else
{
current -> pRight = createNode(data); // 到末尾了，那就新建一个节点吧
break; // 跳出寻找空节点
}
}
else { // 如果待插入的数据比已存在的数据小
if (current -> pLeft != NULL) current = current -> pLeft; // 如果已存在数据，那就继续往下遍历吧
else
{
current -> pLeft = createNode(data); // 到末尾了，那就新建一个节点吧
break; // 跳出寻找空节点
}
}
}
}
}
那么在主程序中使用就是这样的：
int main()
{
printf("Construct tree (. means end):"); // 输入数据，以“.”结束
Tree tree = NULL; // 首先设置root节点的指针为空
int data; // 数据
int hasNum; // 是否有数字
char c; // 读入的字符
while (1) // 始终读入
{
data = 0; // 初始化数字 = 0
hasNum = 0; // 一开始读入并没有数字
while ((c = getchar()) != EOF && !((c == ' ' || c == '\n') && hasNum)) // 遇到“空格”或者“回车符”的时候，如果有数字，那就跳出当前数字的输入
{
if (c >= '0' && c <= '9') { // 遇到了数字
data = data * 10 + c - '0'; // 添加至数据
hasNum = 1; // 有数字了
}
if (c == '.') // 遇到了结束输入的标志
{
if (hasNum) insert(data, &tree); // 加入还有数字输入，那就加入树中
break; // 跳出循环
}
}
if (c == '.') break; // 遇到结束输入标志就跳出输入
insert(data, &tree); // 插入数据至树
}
printf("%p\n",tree); // 输出root节点的地址
printTree_h(tree, 0, NULL, 0); // 打印树
}
順便附上《C/C++ 二叉树》中的那個print_binTree();的源碼。
struct ps {
int dps;
int length;
int type;
};
void print_binTree(Node *root, int d, int lr, vector<ps> dps)
{
if (root == NULL) return;
ps p = {d, (int) log10(root -> data) + 1, root -> right != NULL && lr == 0};
if (dps.size() <= d) dps.push_back(p);
else dps[d] = p;
print_binTree(root -> right,d + 1, 1, dps);
for (vector<ps>::iterator i = dps.begin();i != dps.end() - 1;i ++)
{
if (i -> type && i -> dps != 0) printf("|");
else printf(".");
for (int j = 0;j < i -> length + ((i -> dps) != 0) * 2;j ++)
{
printf(".");
}
}
if (d != 0) printf("|-");
printf("%d",root -> data);
if (root -> left != NULL || root -> right != NULL) printf("-|");
printf("\n");
dps[d].type = root -> left != NULL && lr;
print_binTree(root -> left,d + 1, 0, dps);
}
这样，一颗二叉搜索树就构建完成了。
操作
之前的构建过程中我们其实已经将插入操作实现好了，那么现在我们就来实现一下查找的操作吧。
如果大家了解过二分法，那么你会发现，他其实隐性地使用了二叉查找树。我们的查找实现也和二分法有一些相似。
搜索
// 搜索节点
Node* findNode(Tree root, int n)
{
Node *current = root; // 当前节点
while (current != NULL) // 如果当前节点不为空，那就继续往下搜索
{
if (n > current -> data) current = current -> pRight; // 如果数据大于当前节点，那就继续往右搜寻
else if (n < current -> data) current = current -> pLeft; // 如果数据小于当前节点，那就继续往左搜寻
else return current; // 如果数据相等，那就找到了，返回找到的节点指针
}
return NULL; // 没找到
}
删除
正如所有数据结构中的删除操作一样，二叉搜索树中的删除操作也是所有操作中最复杂的。
我们可以想一下删除的过程，由于叶子的位置可以不同，所以就有很多种情况。
一颗二叉搜索树
情况1：叶子下面没有任何子叶子
如果是这样的话，那就直接删除该叶子节点，并将其父节点的指针变量指向NULL。
比如，要删除8这个数字，那就直接从9那边移除8这个节点的指针，然后再free掉8这个节点就行了。
图示
所以，在删除之前，我们应先定位到8这个节点以及它的父节点9，以便我们操作。
所以先来实现一个比较高级的查找函数：
Node* findNodeWithParent(Tree &root, int data, Node** &parent)
{
Node *current = root; // 当前节点先置为root节点
Node **p = &root; // 取出root节点的地址
while (current != NULL)
{
if (data > current -> data) { // 和普通搜索一样，找大小
p = ¤t -> pRight; // 将其子节点的指针的指针给p，方便修改这个指针变量
current = current -> pRight;
}
else if (data < current -> data) {
p = ¤t -> pLeft;
current = current -> pLeft;
}
else {
parent = p; // 赋值给parent
return current; // 返回找到的当前节点
}
}
return NULL; // 没找着
}
这样就能即找到要删除的节点本身，以及该节点的父节点指向这个节点的指针变量的指针了，只有用二次指针我才能修改这个指针变量的值。
同样的，我们再写一个删除函数。
void delNode(Node* &del, Node** &parent)
{
if (del == NULL) printf("NF\n"); // 如果没找到，那就打印NF
else
{
// 直接删除：
if (del -> pLeft == NULL && del -> pRight == NULL) { // 如果要删除的节点没有子节点
*parent = NULL; // 直接将其父节点指向它的指针变量置为NULL
free(del); // 释放要删除的元素的内存
}
}
}
那么如何调用他们俩呢：
int num_del; // 定义一个读入待删除的数
scanf("%d",&num_del); // 读入
Node **parent; // 定义准备寻找的待删除节点的父亲节点中 指向待删除节点的指针变量 的指针
parent = NULL;
Node *del; // 定义待删除节点
del = findNodeWithParent(tree, num_del, parent); // 找节点
delNode(del, parent); // 删除节点
printTree_h(tree, 0, NULL, 0); // 打印删除之后的树
这样，简单的删除就完成了。
情况2：叶子下面有且仅有一片子叶子
比如删除我们的4号节点。
图示
过程：和图中画的一样。
- 我们先记录下4节点的子节点——3号节点；
- 把4号从它的父节点2号那移除；
- 将2号节点中空出来的那个指针变量重新指向4号下方的3号。
这也是一种比较简单的删除方式，代码实现如下：
if (del -> pLeft != NULL && del -> pRight == NULL) { // 如果要删除的节点有且仅有子左节点
*parent = del -> pLeft; // 将其父节点指向它的子节点
free(del); // 释放要删除的元素的内存
}
else if (del -> pLeft == NULL && del -> pRight != NULL) { // 如果要删除的节点有且仅有子右节点
*parent = del -> pRight; // 将其父节点指向它的子节点
free(del); // 释放要删除的元素的内存
}
和之前的函数整合起来就是这样：
void delNode(Node* &del, Node** &parent)
{
if (del == NULL) printf("NF\n"); // 如果没找到，那就打印NF
else
{
// 直接删除：
if (del -> pLeft == NULL && del -> pRight == NULL) { // 如果要删除的节点没有子节点
*parent = NULL; // 直接将其父节点指向它的指针变量置为NULL
free(del); // 释放要删除的元素的内存
}
// 只有一边
else if (del -> pLeft != NULL && del -> pRight == NULL) { // 如果要删除的节点有且仅有子左节点
*parent = del -> pLeft; // 将其父节点指向它的子节点
free(del); // 释放要删除的元素的内存
}
else if (del -> pLeft == NULL && del -> pRight != NULL) { // 如果要删除的节点有且仅有子右节点
*parent = del -> pRight; // 将其父节点指向它的子节点
free(del); // 释放要删除的元素的内存
}
}
}
情况3：叶子下面有两片子叶子
这种情况是最复杂的，同时也有两种删除方式。下面则介绍了这两种删除方式的操作：
- 从待删除节点的左节点开始，找到其余最大的子节点，并将其数值给待删除的节点，删除这个最大的子节点。
- 从待删除节点的右节点开始，找到其余最小的子节点，并将其数值给待删除的节点，删除这个最小的子节点。
还是图解比较清晰。
图示
上图中，我们要删除5号元素，因此我们可以有两个方案，首先先找到左节点下最大的子节点4，把它给5号节点，这样5号就消失了，接下来，我们在删除重复的4号元素。值得注意的是，最大的子节点最多还有一个子节点，并不会再次出现同时拥有两个节点的情况，所以，删除这个最大或者是最小子节点只要用前两种情况中的删除方式就行了。另外一个方案其实也十分类似，大家类比一下就好了，没有区别的。
不过关于两个方案的选择我还是提一下，如果你的二叉搜索树没有严格的关系的话，两种方式均可，如果有允许相同元素存在的话，那就看情况选择往左删还是往右删。
完整实现代码：
void delNode(Node* &del, Node** &parent)
{
if (del == NULL) printf("NF\n"); // 如果没找到，那就打印NF
else
{
// 直接删除：
if (del -> pLeft == NULL && del -> pRight == NULL) { // 如果要删除的节点没有子节点
*parent = NULL; // 直接将其父节点指向它的指针变量置为NULL
free(del); // 释放要删除的元素的内存
}
// 只有一边
else if (del -> pLeft != NULL && del -> pRight == NULL) { // 如果要删除的节点有且仅有子左节点
*parent = del -> pLeft; // 将其父节点指向它的子节点
free(del); // 释放要删除的元素的内存
}
else if (del -> pLeft == NULL && del -> pRight != NULL) { // 如果要删除的节点有且仅有子右节点
*parent = del -> pRight; // 将其父节点指向它的子节点
free(del); // 释放要删除的元素的内存
}
// 两边都有
else
{
printf("Which mode?(l=left,r=right,other=cancel):\n");
char b;
scanf(" %c",&b);
switch (b)
{
case 'l':
Node *left;
left = del -> pLeft;
Node *big;
Node **maxP;
maxP = &del -> pLeft;
big = findMaxWithParent(left, maxP);
del -> data = big -> data;
delNode(big, maxP);
break;
case 'r':
Node *right;
right = del -> pRight;
Node *small;
Node **minP;
minP = &del -> pRight;
small = findMinWithParent(right, minP);
del -> data = small -> data;
delNode(small, minP);
break;
default:
goto cancel;
break;
}
}
}
cancel:
return;
}
我的代码里实现了选择用哪种删除方式，实际运用时可以不必这么搞，看情况就行了。
上边需要用到的两个找最大最小值的函数：
Node* findMaxWithParent(Node *n, Node** &parent)
{
Node *current = n;
Node **p = parent;
while (1)
{
if (current -> pRight != NULL) {
p = ¤t -> pRight;
current = current -> pRight;
} else {
parent = p;
break;
}
}
return current;
}
Node* findMinWithParent(Node *n, Node** &parent)
{
Node *current = n;
Node **p = parent;
while (1)
{
if (current -> pLeft != NULL) {
p = ¤t -> pLeft;
current = current -> pLeft;
} else {
parent = p;
break;
}
}
return current;
}
到此为止，我们就已经实现了二叉搜索树的基本操作了，下面是完整代码。
完整代码
//
// main.cpp
// BinarySearchTree
//
// Created by 李弘辰 on 2019/8/9.
// Copyright © 2019 李弘辰. All rights reserved.
//
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <math.h>
using namespace std;
typedef struct Node
{
int data;
Node *pLeft;
Node *pRight;
} Node;
typedef struct Node *Tree;
Node *createNode(int data) // 初始化一个节点
{
Node *n = (Node*) malloc(sizeof(Node));
n -> data = data;
n -> pLeft = NULL;
n -> pRight = NULL;
return n;
}
void insert__(int data, Tree *tree) // 向一棵树中插入数据
{
if (*tree == NULL) // 如果树是空的，那就直接创建节点
{
*tree = createNode(data); // 创建节点
} else {
Node *current = *tree; // 记录当前遍历到的节点
while (1) // 其实也能用递归写，但是循环比较好理解
{
if (data >= current -> data) { // 如果待插入的数据比已存在的数据大
if (current -> pRight != NULL) current = current -> pRight; // 如果已存在数据，那就继续往下遍历吧
else
{
current -> pRight = createNode(data); // 到末尾了，那就新建一个节点吧
break; // 跳出寻找空节点
}
}
else { // 如果待插入的数据比已存在的数据小
if (current -> pLeft != NULL) current = current -> pLeft; // 如果已存在数据，那就继续往下遍历吧
else
{
current -> pLeft = createNode(data); // 到末尾了，那就新建一个节点吧
break; // 跳出寻找空节点
}
}
}
}
}
void insert(int data, Tree *node) // 向一棵树中插入数据，采用递归
{
if (*node == NULL)
{
*node = createNode(data);
} else {
if (data >= (*node) -> data)
{
insert(data, &((*node) -> pRight));
} else {
insert(data, &((*node) -> pLeft));
}
}
}
void printTree_h(Node *n,int h,vector<int> *l,int hasNext)
{
if (n == NULL) return;
for (int i = 0;i < h;i ++)
{
if (i == h - 1)
{
if (hasNext) printf("├── ");
else {
printf("└── ");
(*l)[i] = 0;
}
} else
{
if ((*l)[i]) printf("│ ");
else printf(" ");
}
}
printf("%d\n",n -> data);
int b = n -> pLeft != NULL;
if (l == NULL)
{
vector<int> arr;
l = &arr;
}
if (l -> size() <= h) l -> push_back(b);
else (*l)[h] = b;
// printTree(n -> pRight,h + 1,l,b); // 正常输出
printTree_h(n -> pRight,h + 1,l,1); // 可以显示左右节点：├为右，└为左
printTree_h(n -> pLeft,h + 1,l,0);
}
struct ps {
int dps;
int length;
int type;
};
void print_binTree(Node *root, int d, int lr, vector<ps> dps)
{
if (root == NULL) return;
ps p = {d, (int) log10(root -> data) + 1, root -> pRight != NULL && lr == 0};
if (dps.size() <= d) dps.push_back(p);
else dps[d] = p;
print_binTree(root -> pRight,d + 1, 1, dps);
for (vector<ps>::iterator i = dps.begin();i != dps.end() - 1;i ++)
{
if (i -> type && i -> dps != 0) printf("|");
else printf(".");
for (int j = 0;j < i -> length + ((i -> dps) != 0) * 2;j ++)
{
printf(".");
}
}
if (d != 0) printf("|-");
printf("%d",root -> data);
if (root -> pLeft != NULL || root -> pRight != NULL) printf("-|");
printf("\n");
dps[d].type = root -> pLeft != NULL && lr;
print_binTree(root -> pLeft,d + 1, 0, dps);
}
// 搜索节点
Node* findNode(Tree root, int n)
{
Node *current = root; // 当前节点
while (current != NULL) // 如果当前节点不为空，那就继续往下搜索
{
if (n > current -> data) current = current -> pRight; // 如果数据大于当前节点，那就继续往右搜寻
else if (n < current -> data) current = current -> pLeft; // 如果数据小于当前节点，那就继续往左搜寻
else return current; // 如果数据相等，那就找到了，返回找到的节点指针
}
return NULL; // 没找到
}
Node* findNodeWithParent(Tree &root, int data, Node** &parent)
{
Node *current = root; // 当前节点先置为root节点
Node **p = &root; // 取出root节点的地址
while (current != NULL)
{
if (data > current -> data) { // 和普通搜索一样，找大小
p = ¤t -> pRight; // 将其子节点的指针的指针给p，方便修改这个指针变量
current = current -> pRight;
}
else if (data < current -> data) {
p = ¤t -> pLeft;
current = current -> pLeft;
}
else {
parent = p; // 赋值给parent
return current; // 返回找到的当前节点
}
}
return NULL; // 没找着
}
Node* findMaxWithParent(Node *n, Node** &parent)
{
Node *current = n;
Node **p = parent;
while (1)
{
if (current -> pRight != NULL) {
p = ¤t -> pRight;
current = current -> pRight;
} else {
parent = p;
break;
}
}
return current;
}
Node* findMinWithParent(Node *n, Node** &parent)
{
Node *current = n;
Node **p = parent;
while (1)
{
if (current -> pLeft != NULL) {
p = ¤t -> pLeft;
current = current -> pLeft;
} else {
parent = p;
break;
}
}
return current;
}
void delNode(Node* &del, Node** &parent)
{
if (del == NULL) printf("NF\n"); // 如果没找到，那就打印NF
else
{
// 直接删除：
if (del -> pLeft == NULL && del -> pRight == NULL) { // 如果要删除的节点没有子节点
*parent = NULL; // 直接将其父节点指向它的指针变量置为NULL
free(del); // 释放要删除的元素的内存
}
// 只有一边
else if (del -> pLeft != NULL && del -> pRight == NULL) { // 如果要删除的节点有且仅有子左节点
*parent = del -> pLeft; // 将其父节点指向它的子节点
free(del); // 释放要删除的元素的内存
}
else if (del -> pLeft == NULL && del -> pRight != NULL) { // 如果要删除的节点有且仅有子右节点
*parent = del -> pRight; // 将其父节点指向它的子节点
free(del); // 释放要删除的元素的内存
}
// 两边都有
else
{
printf("Which mode?(l=left,r=right,other=cancel):\n");
char b;
scanf(" %c",&b);
switch (b)
{
case 'l':
Node *left;
left = del -> pLeft;
Node *big;
Node **maxP;
maxP = &del -> pLeft;
big = findMaxWithParent(left, maxP);
del -> data = big -> data;
delNode(big, maxP);
break;
case 'r':
Node *right;
right = del -> pRight;
Node *small;
Node **minP;
minP = &del -> pRight;
small = findMinWithParent(right, minP);
del -> data = small -> data;
delNode(small, minP);
break;
default:
goto cancel;
break;
}
}
}
cancel:
return;
}
int main()
{
printf("Construct tree (. means end):"); // 输入数据，以“.”结束
Tree tree = NULL; // 首先设置root节点的指针为空
int data; // 数据
int hasNum; // 是否有数字
char c; // 读入的字符
while (1) // 始终读入
{
data = 0; // 初始化数字 = 0
hasNum = 0; // 一开始读入并没有数字
while ((c = getchar()) != EOF && !((c == ' ' || c == '\n') && hasNum)) // 遇到“空格”或者“回车符”的时候，如果有数字，那就跳出当前数字的输入
{
if (c >= '0' && c <= '9') { // 遇到了数字
data = data * 10 + c - '0'; // 添加至数据
hasNum = 1; // 有数字了
}
if (c == '.') // 遇到了结束输入的标志
{
if (hasNum) insert(data, &tree); // 加入还有数字输入，那就加入树中
break; // 跳出循环
}
}
if (c == '.') break; // 遇到结束输入标志就跳出输入
insert(data, &tree); // 插入数据至树
}
printf("%p\n",tree); // 输出root节点的地址
// printTree_h(tree, 0, NULL, 0); // 打印树
print_binTree(tree,0,1,vector<ps>()); // 打印树
while (true) {
printf("Operate? (i=insert,d=delete,f=find,p=print,other=exit):");
char choose;
scanf(" %c",&choose);
switch (choose) {
case 'i':
printf("num:");
int m;
scanf("%d",&m);
insert(m, &tree);
// printTree_h(tree, 0, NULL, 0);
print_binTree(tree,0,1,vector<ps>());
break;
case 'd':
printf("num:");
int num_del; // 定义一个读入待删除的数
scanf("%d",&num_del); // 读入
Node **parent; // 定义准备寻找的待删除节点的父亲节点中 指向待删除节点的指针变量 的指针
parent = NULL;
Node *del; // 定义待删除节点
del = findNodeWithParent(tree, num_del, parent); // 找节点
delNode(del, parent); // 删除节点
// printTree_h(tree, 0, NULL, 0); // 打印删除之后的树
print_binTree(tree,0,1,vector<ps>());
break;
case 'f':
printf("num:");
int n;
scanf("%d",&n);
printf("%d\n", findNode(tree, n) != NULL);
break;
case 'p':
// printTree_h(tree, 0, NULL, 0);
print_binTree(tree,0,1,vector<ps>());
break;
default:
goto end;
break;
}
}
end:
return 0;
}
