《算法笔记》9.4小节问题 B: 二叉搜索树

这道题也当做二叉搜索树的建树模板。

这道题其实直接把这颗树建出来后，比较前序序列和中序序列即可，这里我用的数组实现，更好写和查错qwq。

code：

#include <bits/stdc++.h>

using namespace std;

int n , len;

string a , b , c;

char tree[400040] , pd[400040] , st[400040];

void t_insert(int i , char x){

	if(tree[i] == '?'){	//如果查找到了空位置，那么那个位置即为该插入的位置

		tree[i] = x;

		return;

	}

	if(tree[i] > x) t_insert(2 * i , x);	//小左大右

	else t_insert(2 * i + 1 , x);

}

void p_insert(int i , char x){

	if(pd[i] == '?'){

		pd[i] = x;

		return;

	}

	if(pd[i] > x) p_insert(2 * i , x);

	else p_insert(2 * i + 1 , x);

}

void t_print(int i , int f){

	if(tree[i] == '?') return;

	if(!f) a += tree[i];	//前序

	t_print(2 * i , f);

	if(f) b += tree[i];		//中序

	t_print(2 * i + 1 , f);

}

void p_print(int i , int f){

	if(pd[i] == '?') return;

	if(!f) c += pd[i];

	p_print(2 * i , f);

	if(f) c += pd[i];

	p_print(2 * i + 1 , f);

}

int main(){

	while(cin >> n){

		if(n == 0) break;

		cin >> st;

		len = strlen(st);

		fill(tree + 1 , tree + 400040 + 1 , '?');	//初始化

		for(int i = 0; i <= len - 1; i++) t_insert(1 , st[i]);	//建树

		a = "";	//清空

		b = "";

		t_print(1 , 0);	//求序列

		t_print(1 , 1);

		while(n--){	//同上~

			cin >> st;

			fill(pd + 1 , pd + 400040 + 1 , '?');

			for(int i = 0; i <= len - 1; i++) p_insert(1 , st[i]);

			c = "";

			p_print(1 , 0);

			if(a != c){

				cout << "NO" << endl;

				continue;

			}

			c = "";

			p_print(1 , 1);

			if(b != c){

				cout << "NO" << endl;

				continue;

			}

			cout << "YES" << endl;

		}

	}

	return 0;

}

巴特西

《算法笔记》9.4小节问题 B: 二叉搜索树

最新文章

热门文章

巴特西

《算法笔记》9.4小节 问题 B: 二叉搜索树

最新文章

热门文章

《算法笔记》9.4小节问题 B: 二叉搜索树