【二叉树】基础
2021-03-29 12:19:00 # ACM

在没有重复权值的基础上建立的二叉搜索树；

这是不平衡的；

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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#include <bits/stdc++.h>
//#include <ext/pb_ds/priority_queue.hpp>
//#pragma GCC optimize("O2")
using namespace std;
//using namespace __gnu_pbds;
#define Combine Pair, greater<Pair>, pairing_heap_tag
#define LL long long
#define ll long long
#define Pair pair<double,LL>
#define ULL unsigned long long
#define ls rt<<1
#define rs rt<<1|1
#define one first
#define two second
#define MS 1000009
#define INF 1e9
#define DBINF 1e100
#define Pi acos(-1.0)
#define eps 1e-9
#define mod 99999997
#define mod1 39989
#define mod2 1000000000

int n,m;
struct node{
	int l,r;
	int val;
}p[MS];
int tot,root;

int add(int val){ // 返回节点编号 
	p[++tot] = {0,0,val}; // 新建节点左右孩子为 0 
	return tot;
}

void build(){ // 初始化两个节点，正负无穷大 
	root = add(-INF);
	p[root].r = add(INF);
}

int search(int rt,int val){ // 递归搜索返回节点编号 
	if(rt == 0) return 0;
	if(p[rt].val == val) return rt;
	if(val < p[rt].val) return search(p[rt].l,val);
	if(val > p[rt].val) return search(p[rt].r,val);
}

void insert(int &rt,int val){
	if(rt == 0){ // 无该节点则新建 
		rt = add(val);
		return;
	}
	if(val == p[rt].val) return; // 存在则无操作 
	if(val > p[rt].val) insert(p[rt].r,val);
	if(val < p[rt].val) insert(p[rt].l,val);
}

int getfront(int rt,int val){ // 查询前驱节点编号 
	int ans = 1;
	while(rt){
		if(val == p[rt].val){ // 若查到该值 
			if(p[rt].l != 0){ // 寻找该点左子树最大值 
				rt = p[rt].l;
				while(p[rt].r != 0) rt = p[rt].r;
				ans = rt;
			}
			break;
		}
		if(p[ans].val < p[rt].val && p[rt].val < val) ans = rt; // 一边递归一边更新 
		if(val < p[rt].val) rt = p[rt].l;
		else rt = p[rt].r;
	}
	return ans;
}

int getnext(int rt,int val){ // 查询后继节点编号 
	int ans = 2;
	while(rt){
		if(val == p[rt].val){ // 若查到该值 
			if(p[rt].r != 0){ // 寻找该点右子树最小值 
				rt = p[rt].r;
				while(p[rt].l != 0) rt = p[rt].l;
				ans = rt;
			}
			break;
		}
		if(val < p[rt].val && p[rt].val < p[ans].val) ans = rt;// 一边递归一边更新 
		if(val < p[rt].val) rt = p[rt].l;
		else rt = p[rt].r;
	}
	return ans;
}

void remove(int &rt,int val){
	if(rt == 0) return; // 若不存在则无操作 
	if(p[rt].val == val){ // 找到该值 
		if(p[rt].l == 0) rt = p[rt].r; // 无左子树则 fa[rt]的左或右指针 指向 右子树 （rt为引用则可看作 fa[rt]） 
		else if(p[rt].r == 0) rt = p[rt].l; // 同理 
		else{ // 左右子树同时存在，这里寻找右子树的最小值代替被删节点 
			int nxt = p[rt].r;
			while(p[nxt].l != 0) nxt = p[nxt].l; // 找到最小节点 
			remove(p[rt].r,val); // 移除最小节点 
			// 令节点nxt代替rt的位置 
			p[nxt].l = p[rt].l; 
			p[nxt].r = p[rt].r;
			rt = nxt; //fa[rt]的左或右指针 指向 右子树 （rt为引用则可看作 fa[rt]） 
		}
		return;
	}
	if(val < p[rt].val) remove(p[rt].l,val);
	if(val > p[rt].val) remove(p[rt].r,val);
}

void mid_order(int rt){ // 中序遍历 
	if(rt == 0) return;
	mid_order(p[rt].l);
	printf("%d ",p[rt].val);
	mid_order(p[rt].r);
}

int main() {
	ios::sync_with_stdio(false);
	build();
	int ert;
	insert(ert = root,5);
	insert(ert = root,3);
	insert(ert = root,2);
	insert(ert = root,1);
	insert(ert = root,4);
	insert(ert = root,8);
	mid_order(ert = root);
	printf("\n");
	printf("%d\n",p[getfront(ert = root,4)].val);
	printf("%d\n",p[getnext(ert = root,4)].val);


	return 0;
}
Prev
2021-03-29 12:19:00 # ACM
Next