[数据结构与算法]二叉搜索树 PatA1064与A1099

二叉搜索树 PatA1064与A1099

思路

A1064:给出一个序列，要求用其构建一个完全二叉搜索树

A1099：给出一个二叉搜索树的结构。给出一个序列，要求用其构建出题目要求结构的二叉搜索树。

共同点

都要求用给出的序列构建一个题目要求结构的二叉搜索树

关键点

二叉搜索树的中序遍历是递增的。

逆向思维：将一个树中序遍历，并按递增填入数据即可构建一个二叉搜索树

A1064

由于完全二叉树可用数组来方便的表示。因此可以中序遍历完全二叉树，并递增填入给定的序列

A1099

已经给出了树的结构。因此也可用数组静态构建该树。定义一个结构体，存储每个结点的值，左节点序号与右节点序号。

之后就可中序遍历该树，并递增填入数据。

代码

A1064

#include<iostream>
#include<array>
#include<algorithm>
using namespace std;
array<int,1010> datas;
array<int,1010> tree;
int n,pos = 1;
void dfs(int index){
	if(index > n) return;
	dfs(index*2);
	tree.at(index) = datas.at(pos++);
	dfs(index*2+1);
}
int main(){
	cin>>n;
	for(int i=1;i<=n;++i){
		int d = 0;
		cin>>d;
		datas.at(i) = d;
	} 
	sort(datas.begin()+1,datas.begin()+n+1);
	dfs(1);
	int flag = true;
	for(int j=1;j<=n;++j){
		if(flag){
			flag = false;
		}else {
			cout<<" ";
		}
		cout<<tree.at(j);
	}
} 

A1099

#include<iostream>
#include<vector>
#include<array>
#include<queue>
#include<algorithm>
using namespace std;
struct node{
	int data;
	int left;
	int right;
}; 
int n;
array<node,110>tree;
array<int,110> datas;
int pos = 0;
void creat(int index){
	if(index == -1) return;
	creat(tree[index].left);
	tree[index].data = datas.at(pos++);
	creat(tree[index].right);
}
int sum = 0;
void bfs(){
	queue<node> q;
	q.push(tree[0]);
	while(!q.empty()){
		node now = q.front();
		q.pop();
		cout<<now.data;
		sum++;
		if(sum<n) cout<<" ";
		if(now.left != -1) q.push(tree[now.left]);
		if(now.right !=-1) q.push(tree[now.right]);
		
	} 
}

int main(){
	cin>>n;
	for(int i=0;i<n;++i){
		int l =0,r = 0;
		cin>>l>>r;
		tree[i].left = l;
		tree[i].right = r;
	}
	for(int j=0;j<n;++j){
		cin>>datas.at(j);
	}
	sort(datas.begin(),datas.begin()+n);
	creat(0);
	bfs();
}