构造二叉搜索树
树的中序遍历,层次遍历
本题考查的点为如何根据一颗已知结构及其中序遍历的树,构造出这颗完整的树
思路:
1.如何选择数据结构存树?
最容易想到的无非就是–>结构体的形式,但是为了快速的破题,可以使用多个数组来模拟结构体的方式,即如下代码:
int l[N], r[N], w[N]; //分别代表左节点,右节点,权值
2.如何存树的结构?
直接在输入的时候循环将左右节点塞入l, r数组即可。
for(int i = 0; i < n; i ++ )
scanf("%d%d", &l[i], &r[i]);
3.如何根据中序遍历及树的骨架恢复这棵树?
首先,二叉搜索树的一大特点即为,其中序遍历的结果为所有节点值的升序排列,所以我们只需要将输入的数组进行升序排列即可得到我们想要的中序遍历序列。
其次,如何根据中序遍历建树呢?
我们可以从传统的中序遍历的思路出发:
void dfs(int u)
{
if(u == -1) return ;
else
{
dfs(l[u]);
cout<<"节点值";
dfs(r[u]);
}
}
不难发现,当我们第一次cout的时候,即为找到中序遍历第一个点的时候,同理也就是我们给第一个节点赋值的时候。按照这个思路我们只需要维护一个数k,记录我们当前遍历到了第几个节点即可给相应的元素赋值。
代码如下:
void dfs(int u, int& k)
{
if(u == -1) return ;
else
{
dfs(l[u], k);
w[u] = a[k ++ ];
dfs(r[u], k);
}
}
4.如何层次遍历?
层次遍历我们只需要使用一个队列,不断地出队,入队即可
解题代码如下:
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110;
int n, l[N], r[N], w[N], q[N];
int a[N];
void dfs(int u, int& k)
{
if(u == -1) return ;
else
{
dfs(l[u], k);
w[u] = a[k++];
dfs(r[u], k);
}
}
void bfs()
{
int hh = 0, tt = 0;
q[0] = 0;
while(hh <= tt)
{
int t = q[hh++];
if(l[t] != -1) q[++tt] = l[t];
if(r[t] != -1) q[++tt] = r[t];
printf("%d ",w[t]);
}
}
int main()
{
scanf("%d", &n);
for(int i = 0; i < n; i ++ )
scanf("%d%d", &l[i], &r[i]);
for(int i = 0; i < n; i ++ )
scanf("%d", &a[i]);
sort(a, a + n);
int k = 0;
dfs(0, k);
bfs();
return 0;
}
非常清晰!
谢谢支持!