蒟蒻の二叉搜索树（二叉排序树、二叉查找树）学习总结

定义

二叉搜索树 ,它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。

解决问题

二叉搜索树作为一种经典的数据结构，它既有链表的快速插入与删除操作的特点，又有数组快速查找的优势；所以应用十分广泛，例如在文件系统和数据库系统一般会采用这种数据结构进行高效率的排序与检索操作。

模板

#include <bits/stdc++.h>
using namespace std;
int n;
char a[10001],tree[10001]; //a是字符串，tree循环建树 
string pre,in,pres,ins; 
/*pre和in存储基础字符串的先序和中序；pres和ins存储待判断字符串的先序和中序 */

inline void insert(int i,char x) { //边读入边建树 
	if(tree[i]=='@') {
		tree[i]=x;
		return ;
	}
	if(x>tree[i]) insert(2*i+1,x);
	else insert(2*i,x); 
}

inline void preorder(int i) { //基础字符串的先序 
	if(tree[i]=='@') return ;
	pre+=tree[i];
	preorder(2*i);
	preorder(2*i+1);
}

inline void inorder(int i) { //基础字符串的中序 
	if(tree[i]=='@') return ;
	inorder(2*i);
	in+=tree[i];
	inorder(2*i+1);
}

inline void preorders(int i) { //待判断字符串的先序 
	if(tree[i]=='@') return ;
	pres+=tree[i];
	preorders(2*i);
	preorders(2*i+1);
}

inline void inorders(int i) { //待判断字符串的中序 
	if(tree[i]=='@') return ;
	inorders(2*i);
	ins+=tree[i];
	inorders(2*i+1);
}

int main() {
	while(scanf("%d",&n)) {
		if(n==0) break;
		cin>>a;
		fill(tree+1,tree+1+10001,'@'); //初始化 
		pre=""; //清空 
		in="";
		for(register int i=0;i<strlen(a);i++) insert(1,a[i]); //建树 
		preorder(1);
		inorder(1);
//		cout<<pre<<endl<<in<<endl;
		for(register int i=1;i<=n;i++) {
			fill(tree+1,tree+1+10001,'@'); //初始化 
			cin>>a;
			for(register int j=0;j<strlen(a);j++) insert(1,a[j]);
			preorders(1);
			inorders(1);
//			cout<<pres<<" "<<ins<<endl;
			if(pres==pre&&ins==in) puts("YES");
			else puts("NO");
			pres=""; //清空 
			ins="";
		}
	}
	
	return 0;
}

例题(转载自)

一、二叉搜索树

思路

（1）要判断两棵树是否相同，只需要判断两棵树的先序和中序（后序+中序或层序+中序都可以，但是先序+中序更简单qwq）是否都相同，是的话说明两棵树相同，反之一定不相同（因为根据某序+中序可以确定唯一的树）

（2）对于每一组数据（一个n为一组数据）：
每输入一个基础字符串就建树一次，然后用两个string：pre和in分别存储基础字符串建树后的先序和中序

以下依次输入n个待判断字符串，也每次建树一次，然后用两个string：pres和ins分别存储待判断字符串的先序和中序，再跟基础字符串的pre和in作比较，满足条件就输出“YES”，反之输出“NO”

（3）注意：因为变量是循环利用，所以每一次使用之后都要清零（初始化）

代码

#include <bits/stdc++.h>
using namespace std;
int n;
char a[10001],tree[10001]; //a是字符串，tree循环建树 
string pre,in,pres,ins; 
/*pre和in存储基础字符串的先序和中序；pres和ins存储待判断字符串的先序和中序 */

inline void insert(int i,char x) { //边读入边建树 
	if(tree[i]=='@') {
		tree[i]=x;
		return ;
	}
	if(x>tree[i]) insert(2*i+1,x);
	else insert(2*i,x); 
}

inline void preorder(int i) { //基础字符串的先序 
	if(tree[i]=='@') return ;
	pre+=tree[i];
	preorder(2*i);
	preorder(2*i+1);
}

inline void inorder(int i) { //基础字符串的中序 
	if(tree[i]=='@') return ;
	inorder(2*i);
	in+=tree[i];
	inorder(2*i+1);
}

inline void preorders(int i) { //待判断字符串的先序 
	if(tree[i]=='@') return ;
	pres+=tree[i];
	preorders(2*i);
	preorders(2*i+1);
}

inline void inorders(int i) { //待判断字符串的中序 
	if(tree[i]=='@') return ;
	inorders(2*i);
	ins+=tree[i];
	inorders(2*i+1);
}

int main() {
	while(scanf("%d",&n)) {
		if(n==0) break;
		cin>>a;
		fill(tree+1,tree+1+10001,'@'); //初始化 
		pre=""; //清空 
		in="";
		for(register int i=0;i<strlen(a);i++) insert(1,a[i]); //建树 
		preorder(1);
		inorder(1);
//		cout<<pre<<endl<<in<<endl;
		for(register int i=1;i<=n;i++) {
			fill(tree+1,tree+1+10001,'@'); //初始化 
			cin>>a;
			for(register int j=0;j<strlen(a);j++) insert(1,a[j]);
			preorders(1);
			inorders(1);
//			cout<<pres<<" "<<ins<<endl;
			if(pres==pre&&ins==in) puts("YES");
			else puts("NO");
			pres=""; //清空 
			ins="";
		}
	}
	
	return 0;
}