2 是否完全二叉搜索树 (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
好久没敲代码了，竟然连完全二叉树的定义都忘了，
完全二叉树的判别：
完全二叉树：只有最下面的两层结点度能够小于2，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树
所以说：
完全二叉树的特点是：
1）只允许最后一层有空缺结点且空缺在右边，即叶子结点只能在层次最大的两层上出现；
2）对任一结点，如果其右子树的深度为j，则其左子树的深度必为j或j+1。 即度为1的点只有1个或0个
对于一颗完全二叉树采用广度优先遍历，从根节点开始，入队列，如果队列不为空，循环。遇到第一个没有左儿子或者右儿子的节点，设置标志位，如果之后再遇到有左/右儿子的节点，那么这不是一颗完全二叉树。这个方法需要遍历整棵树，复杂度为O(N)，N为节点的总数。
#include<bits/stdc++.h>
using namespace std;
double a[11000];
struct node{
int val;
node *lc;
node *rc;
};
node *create(){
node *p=new node;
p->lc=NULL;
p->rc=NULL;
return p;
}
void Build(node *&p,int ele){
if(p==NULL){
p=create();
p->val=ele;
return ;
}
if(p->val>=ele){
Build(p->rc,ele);
}
else{
Build(p->lc,ele);
}
return ;
}
queue<node *>Q;int n;
int first=0;
int judge(node *p){
if(p){
if(!first){
return 1;
}
else{
return 0;
}
}
else{
first=1;
}
return 1;
}
void solve(node *p){
Q.push(p);
int biao=0;
int flag=0;
while(!Q.empty()){
node *tm=Q.front();
Q.pop();
if(tm==NULL){
return ;
}
if(flag==0)flag=1;
else printf(" ");
printf("%d",tm->val);
if(tm->lc){
Q.push(tm->lc);
}
if(tm->rc){
Q.push(tm->rc);
}
if(!judge(tm->lc)){
biao=1;
}
if(!judge(tm->rc)){
biao=1;
}
}
if(biao==1){
puts("\nNO");
}
else{
puts("\nYES");
}
}
int main(){
cin>>n;
node *root=create();
root=NULL;
for(int i=0;i<n;i++){
int t;
scanf("%d",&t);
Build(root,t);
}
// mid(root);
solve(root);
return 0;
}
转载请注明原文地址: https://ju.6miu.com/read-37545.html
