NTFS权限 Mxnet 建网站 状态模式 forms debugging join post mvvm Momentjs 河南省普通话考试官网 it教学视频 jquery获取最后一个子元素 css获取最后一个元素 录音棚设备一套多少钱 matlab颜色代码 kubernetes入门 python数据 python中文 python怎么配置环境 python的开发工具 python基础知识 python写入文件 python设置环境变量 filejava java初级 java读取文件内容 java学习课程 java中continue java怎么安装 java配置jdk javalist转数组 linux用户管理 微信python退出程序 苹果手机老是自动重启 pr转场特效下载 php抓取网页数据 福昕阅读器绿色版 mpg格式转换 一羽月土米水日古余打一成语
当前位置: 首页 > 学习教程  > 编程语言

【CCCC】L3-010 是否完全二叉搜索树 (30分),完全二叉树判断+层次遍历(奇怪的方法)

2020/10/8 20:07:32 文章标签:

problem L3-010 是否完全二叉搜索树 (30分) 将一系列给定数字顺序插入一个初始为空的二叉搜索树(定义为左子树键值大,右子树键值小),你需要判断最后的树是否一棵完全二叉树,并且给出其层序遍历的结果。 输入格式&…

problem

L3-010 是否完全二叉搜索树 (30分)
将一系列给定数字顺序插入一个初始为空的二叉搜索树(定义为左子树键值大,右子树键值小),你需要判断最后的树是否一棵完全二叉树,并且给出其层序遍历的结果。

输入格式:
输入第一行给出一个不超过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
作者
陈越
单位
浙江大学
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB

  • 给定一个序列,建立一棵二叉搜索树
  • 输出层次遍历,并判断是否是完全二叉树

solution

  • 直接当做完全二叉树去建树,如果最后节点编号超过n(即,有奇怪的形状),那么就是NO
  • 层次遍历直接扫描序列,有就输出即可。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1010;

int Tree[maxn];
void update(int root, int val){
	if(!Tree[root])
		Tree[root] = val;
	else if(val > Tree[root])
		update(root*2, val);
	else 
		update(root*2+1,val);
}

int main(){
	int n;  cin>>n;
	for(int i = 1; i <= n; i++){
		int x;  cin>>x;  update(1,x);
	}
	int ok = 0, cnt = 0;
	for(int i = 1; i < maxn; i++){
		if(Tree[i]){
			if(ok)cout<<" ";
			else ok = 1;
			cout<<Tree[i];
			cnt = i;
		}
	}
	if(cnt > n)cout<<"\nNO\n";
	else cout<<"\nYES\n";
	return 0;
}



本文链接: http://www.dtmao.cc/news_show_250212.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?