【二叉搜索树】基础

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

这是不平衡的；

#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();
	insert(root,5);
	insert(root,3);
	insert(root,2);
	insert(root,1);
	insert(root,4);
	insert(root,8);
	mid_order(root);
	printf("\n");
	printf("%d\n",p[getfront(root,4)].val);
	printf("%d\n",p[getnext(root,4)].val);


	return 0;
}

【二叉搜索树】基础

原文：https://www.cnblogs.com/Tecode/p/14591821.html