04-树6 Complete Binary Search Tree(30 分)

题目链接

题目大意

给出n个节点,构造一棵完全二叉搜索树。
最后按层次遍历输出这棵树。

分析

搜索二叉树的中序遍历是按照由小到大的顺序遍历的。
而完全二叉树,知道树的结点后就可以唯一确定树的结构,因此知道树的结点数后,中序遍历并将结点由小到大给树赋值,就可以构建出树。

###AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>
using namespace std;
int b[1023], a[1023];
int j=0, N;
void inOrder(int x){
if(x<=N){
//遍历左子树
inOrder(x + x);
//更新根节点
b[x] = a[j++];
//遍历右子树
inOrder(x+x+1);
}
}
int main(int argc, char const *argv[])
{
int i;
cin >> N;
for(i = 0; i<N; i++)
cin >> a[i];
sort(a, a + N);
inOrder(1);
cout << b[1];
for(i = 2; i<=N; i++)
cout << ' ' << b[i];
return 0;
}

本文标题:04-树6 Complete Binary Search Tree(30 分)

文章作者:admin

发布时间:2017年11月12日 - 14:11

最后更新:2017年11月12日 - 20:11

原始链接:https://kxp555.coding.me/2017/11/12/CBST/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。