二叉查找树（BST）（算法笔记）_数据结构 bst

本文内容基于《算法笔记》和官方配套练题网站“晴问算法”，是我作为小白的学习记录，如有错误还请体谅，可以留下您的宝贵意见，不胜感激

---

前言

数据结构的目的是用来优化数据的使用效率，这是数据结构的本质。
二叉查找树是一种特殊形态的二叉树，又称为排序二叉树、二叉搜索树、二叉排序树。对树上的每个节点，都满足其左子树上所有结点的数据域均小于或等于根节点的数据域，右子树上所有结点的数据域均大于根结点的数据域。
单独使用一颗普通的二叉树对提高数据使用效率没有太大帮助，因为普通二叉树数据之间不存在明显的逻辑联系，在进行插入时，无法提供性质满足插入位置的确定，即插入位置的选择完全是随机的，所以并不会直接考察普通二叉树的插入和删除操作。这样的数据结构是没有太大意义的。所以衍生了一系列不同形态的二叉树，满足不同问题的需求。

一、BST的递归定义

①要么二叉查找树是一棵空树；
②要么二叉查找树由根结点、左子树、右子树组成，其中左子树和右子树都是二叉查找树，且左子树上所有结点的数据域均小于或等于根结点的数据域，右子树上所有结点的数据域均大于根结点的数据域。

二、BST的查找、插入、创建和删除

（一）、查找

二叉查找树的查找类似普通二叉树的先序遍历，只是BST的左子树、根结点、右子树之间存在左子树<根结点<右子树的性质，这就使得BST的查找可以按照规律来进行，即通过类似剪枝的操作来确定向哪个方向进行查找。

（二）、插入

BST的插入操作和普通二叉树的插入操作模板相同，通过有规律的查找来确定为空结点的根结点位置，就是BST将要插入的位置。

（三）、创建

BST的创建过程就是对空二叉查找树进行插入的过程，对相同的数字，采用不同的序列进行插入，最后构建起来的BST可能不同。

（四）、删除

数据结构删除的本质是让某个满足条件的结点被删除后还能保持其原有的数据结构。书中只给出了两种常用删除方法中最简单易写的一种。
先给出前驱和后继的定义：把BST中结点权值小的最大结点称为该结点的前驱，把BST中结点权值大的最小结点称为该结点的后继。显然，结点的前驱是该结点左子树中的最右结点（也就是从左子树根结点开始不断沿着rchild往下直到rchild为NULL时的结点)，而结点的后继则是该结点右子树中的最左结点（也就是从右子树根结点开始不断沿着lchild往下直到lchild为NULL时的结点)。
删除方法：
①删除root：找到root、找到root的前驱，用前驱覆盖root，然后继续删除前驱；
②删除root：找到root、找到root的后继，用后继覆盖root，然后继续删除后继；
这两个方法是同一种类型，可以看出BST的删除也是一种递归过程，且包括两部分：查找删除位置和删除操作，其中删除操作内又包括了对前驱和后继的删除。
这段删除代码可以进行回溯优化，并且可以对前驱和后继的递归进行优化。
需要注意的是，总是优先删除前驱（或者后继）容易导致树的左右子树高度极度不平衡使得二叉查找树退化成一条链。解决这一问题的办法有两种：一种是每次交替删除前驱或后继；另一种是记求于树高度，总是优先在高度较高的一棵子树里删除结点。

三、小题练习

1.二叉查找树的建立

思路：BST的创建+先序遍历；
实现：静态BST实现
完整代码如下：

#include<cstdio>    //静态BST 
const int MAXN = 50;
int number[MAXN] = {};

struct Node{
	int data;
	int lchild;
	int rchild;
}node[MAXN];
int index = 0;
int n , count = 1;

void rld(int root){   //先序遍历 
	if(root == -1) return;
	printf("%d", node[root].data);
	if(count < n){
		printf(" ");
		count++;
	}
	rld(node[root].lchild);
	rld(node[root].rchild);
}

int newNode(int data){    //新建结点 
	node[index] = {data , -1 , -1};
	return index++;
}

void insert(int &root , int data){ //第一次引用root用来更改根结点，修改的是create中循环的root值 
	if(root == -1) {               //第二次之后引用root用来更改根结点内的左右子树的地址 
		root = newNode(data);
		return;
	}
	if(node[root].data > data) insert(node[root].lchild , data);
	else insert(node[root].rchild , data);
}

void create(){    //创建树 
	int root = -1;
	for(int i = 0; i <= n - 1; i++) insert(root , number[i]);
}

int main(){
	scanf("%d", &n);
	for(int i = 0; i <= n - 1; i++)
		scanf("%d", number + i);
	create();
	rld(0);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

2.二叉查找树的判定

思路：运用BST的性质，中序遍历为递增序列即为BST；
实现：边输入边判断；
完整代码如下：

#include<cstdio>
#include<algorithm>
using namespace std;

int main(){
	int n , cmp = 0;
	bool flag = true;
	scanf("%d", &n);
	for(int i = 0; i <= n - 1; i++){
		int temp;
		scanf("%d", &temp);
		if(temp > cmp) cmp = temp;
		else {
			flag = false;
			break;
		}
	}
	if(flag == true) printf("Yes");
	else printf("No");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

3.还原二插查找树

思路：这一题和上一结二叉树的还原有点不同，只给出了先序序列。回忆二叉树的还原，先序序列提供根结点，中序序列提供左右子树的结点数量。根据BST的性质，在确定根结点的情况下，遍历先序序列，找到第一个大于根结点的结点，这个结点右边（包括这个结点）的全部结点就是根结点的右子树，左边的全部结点（不包括根结点）就是根结点的左子树，反复重复上一步骤，直到区间左下标超过右下标；
实现：静态BST+分治法
问题分解：分区递归确定每个根结点的左右子节点位置（和快排的partition很相似）；
递归边界：区间左下标超过右下标；
完整代码如下：
也可以采用将结点元素散列为地址的做法，这样就不需要新建结点，更快；

#include<cstdio>
const int MAXN = 50;
int BSTrld[MAXN] = {};

struct Node{
	int data;
	int lchild;
	int rchild;
}node[MAXN];
int count = 1 , n;
int index = 0;

int newNode(int data){    //新建结点 
	node[index] = {data , -1 , -1};
	return index++;
}

int build(int l , int r){
	if(l > r) return -1;
	int root = newNode(BSTrld[l]);   //新建根结点 
	for(int i = l + 1; i <= r; i++){
		if(BSTrld[i] > BSTrld[l]) {    
			node[root].lchild = build(l + 1 , i - 1);  //左子树不存在的情况包含在了里面
			node[root].rchild = build(i , r);
			break;
		}
		if(i == r) node[root].lchild = build(l + 1 , r);  //右子树不存在 
	}
	return root;
}

void ldr(int root){
	if(root == -1) return;
	ldr(node[root].lchild);
	ldr(node[root].rchild);
	printf("%d", node[root].data);
	if(count < n){
		printf(" ");
		count++;
	}
}

int main(){
	scanf("%d", &n);
	for(int i = 0; i <= n - 1; i++)
		scanf("%d", BSTrld + i);
	ldr(build(0 , n - 1));
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

4.填充二叉查找树

思路：运用二叉查找树的性质，即中序序列为递增序列，中序遍历BST，将当前整数中的最小值填入BST的数据域中（中序遍历的结果是唯一的，这样可以满足填充需求）；
实现：静态BST+中序遍历+整数排序+先序遍历；
完整代码如下：

#include<cstdio>
#include<algorithm>
using namespace std;

const int MAXN = 50;
int data[MAXN] = {};
struct Node{
	int data;
	int lchild;
	int rchild;
}node[MAXN];
int countr = 1 , n;
int index = 0;

void lrdinsert(int root){   //中序填充
	if(root == -1) return;   //空树 
	lrdinsert(node[root].lchild);
	if(node[root].data == -1) node[root].data = data[index++];  //未填充 
	lrdinsert(node[root].rchild);
}

void rld(int root){
	if(root == -1) return;
	printf("%d", node[root].data);
	if(countr < n) {
		printf(" ");
		countr++;
	}
	rld(node[root].lchild);
	rld(node[root].rchild);
}

int main(){
	scanf("%d", &n);
	for(int i = 0; i <= n - 1; i++)
		scanf("%d", data + i);
	sort(data , data + n);
	for(int i = 0; i <= n - 1; i++){
		scanf("%d%d", &node[i].lchild , &node[i].rchild);
		node[i].data = -1;   //初始化数据域 
	}
	lrdinsert(0);
	rld(0);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

5.基于问题1的删除操作（补充）
官网内没有针对删除的练习，这里把第1题改一改，在删除树的根结点后输出BST的先序序列。
完整代码如下：

#include<cstdio>    //静态BST 
const int MAXN = 50;
int number[MAXN] = {};

struct Node{
	int data;
	int lchild;
	int rchild;
}node[MAXN];
int index = 0;
int n , count = 1;

void rld(int root){   //先序遍历 
	if(root == -1) return;
	printf("%d", node[root].data);
	if(count < n){
		printf(" ");
		count++;
	}
	rld(node[root].lchild);
	rld(node[root].rchild);
}

int newNode(int data){    //新建结点 
	node[index] = {data , -1 , -1};
	return index++;
}

void insert(int &root , int data){ //第一次引用root用来更改根结点，修改的是create中循环的root值 
	if(root == -1) {               //第二次之后引用root用来更改根结点内的左右子树的地址，注意递归函数内的变量作用域 
		root = newNode(data);
		return;
	}
	if(node[root].data > data) insert(node[root].lchild , data);
	else insert(node[root].rchild , data);
}

void create(){    //创建树 
	int root = -1;
	for(int i = 0; i <= n - 1; i++) insert(root , number[i]);
}

int findMAX(int root){    //找前驱 
	while(node[root].rchild != -1) root = node[root].rchild;
	return root;
}

int findMIN(int root){    //找后继 
	while(node[root].lchild != -1) root = node[root].lchild;
	return root;
}

void del(int &root , int x){    //注意这里root也要引用，因为要更改树的结构 
	if(root == -1) return;
	if(node[root].data == x){   //删除操作 
		if(node[root].lchild == -1 && node[root].rchild == -1) root = -1;  //叶节点，父节点引用不到它,就是这里更改了树的结构 
		else if(node[root].lchild != -1){    //左子树非空，两种方法用一种即可 
			int pre = findMAX(node[root].lchild);  //找root前驱
			node[root].data = node[pre].data;      //覆盖 
			del(node[root].lchild , node[pre].data);             //继续删除前驱 
		} 
		else {    //右子树非空 
			int next = findMIN(node[root].rchild);   //找root后继 
			node[root].data = node[next].data;       //覆盖 
			del(node[root].rchild , node[next].data);             //继续删除后继 
		}
	}
	else if(node[root].data > x) del(node[root].lchild , x);   //查找操作 
	else if(node[root].data < x) del(node[root].rchild , x);
}

int main(){
	scanf("%d", &n);
	for(int i = 0; i <= n - 1; i++)
		scanf("%d", number + i);
	create();
	int root = 0;
	del(root , number[0]);
	rld(root);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

备注

1.二分查找的过程其实就是查找一颗BST的过程，因为二分查找要求数据必须是递增或递减的，所以在选择向mid（中点）左方向还是右方向查找的过程，其实就是BST中选择左子树还是右子树的过程，所以这就体现了算法和数据结构的联系（自己发现的，有点兴奋，嘿嘿）；
2.对BST进行中序序列遍历，结果是有序的，其实就等同于对一个递增序列的顺序遍历；
3.注意体会二叉树插入时对root的引用操作；
4.我在写删除的的过程中出现了逻辑错误，注意if—else的结构，这是在两个条件下选择一个进行执行的结构，如果两个条件是对立的，那么写两个if也可以正确运行。但有时候两个条件并不是完全对立的，在写的时候就容易因省略else而产生错误。