对 二叉搜索树 的定义是:
一棵深度为k的有n个结点的二叉树,对树中的结点按从上至下、从左到右的顺序进行编号,如果编号为i(1 ≤ i ≤ n )的结点与满二叉树中编号为i的结点在二叉树中的位置相同,则这棵二叉树称为 完全二叉树 。
给出二叉搜索树的层次 遍历,并判断是否为完全二叉搜索树
可以参考PTA 链接
将一系列给定数字顺序插入一个初始为空的二叉搜索树(定义为左子树键值大,右子树键值小),你需要判断最后的树是否一棵完全二叉树,并且给出其层序遍历的结果。
输入格式:
输入第一行给出一个不超过20的正整数N;第二行给出N个互不相同的正整数,其间以空格分隔。
输出格式:
将输入的N个正整数顺序插入一个初始为空的二叉搜索树。在第一行中输出结果树的层序遍历结果,数字间以1个空格分隔,行的首尾不得有多余空格。第二行输出YES,如果该树是完全二叉树;否则输出NO。
输入样例1:
9
38 45 42 24 58 30 67 12 51
输出样例1:
38 45 24 58 42 30 12 67 51
YES
输入样例2:
8
38 24 12 45 58 67 42 51
输出样例2:
38 45 24 58 42 12 67 51
NO
假如我们将二叉搜索树的根节点编号为root = 1
,左孩子节点的编号为root<<1
,右孩子节点的编号为root<<1|1
那么说我们将得到一颗这样的树形结构(下图为完美二叉树):
所以说在我们的存储过程中,在数组中存储一定是连续的
也就是说:我们将数组初始化为0,有值的部分一定是连续的从1 → n
并不可能出现1 → n 中有的部分为0
Code:
int n,m,k; int a[1LL<<21]; void build(int id,int x) { if(a[id] == 0) a[id] = x; else if(x > a[id]) build(id<<1,x); else if(x < a[id]) build(id<<1|1,x); } int main() { n = read; for(int i=1; i<=n; i++) { int x = read; build(1,x); } int flag = 0; for(int i=1; i<=n; i++) { if(!a[i]) { flag = 1; break; } } if(!flag) { for(int i=1; i<=n; i++) { printf("%d%c",a[i],(i == n ? '\n':' ')); } } else { int cnt = 0; for(int i=1; i; i++) { if(a[i]) { cnt ++; printf("%d%c",a[i],(cnt == n?'\n':' ')); if(cnt == n) break; } } } printf("%s",flag?"NO":"YES"); return 0; } /** 8 38 24 12 45 58 67 42 51 **/