网站建设排名公司哪家好,企业网站建立要做的准备,编一个公司网址,2022年可以打开的网址将一系列给定数字顺序插入一个初始为空的二叉搜索树#xff08;定义为左子树键值大#xff0c;右子树键值小#xff09;#xff0c;你需要判断最后的树是否一棵完全二叉树#xff0c;并且给出其层序遍历的结果。 输入格式#xff1a; 输入第一行给出一个不超过20的正整数… 将一系列给定数字顺序插入一个初始为空的二叉搜索树定义为左子树键值大右子树键值小你需要判断最后的树是否一棵完全二叉树并且给出其层序遍历的结果。 输入格式 输入第一行给出一个不超过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题意是输入一个n再输入n个数输出按这个序列插入一个左大右小的BST试着去判断这个bst是不是一颗完全的bst符不符合完全树的定义再输出层序遍历序列 如何判断一棵树是否是完全二叉树我们从条件入手
1 完全二叉树倒数第二层以上包括倒数第二层全满。
2 最后一层的最后一个节点左边全满
于是我们不妨先把最大层数找出来然后用搜索带个层数的参数每次搜索判断如果这一层不是最后一层而少点 那么就不是完全二叉树 满足第一点的判断
我们按照先右后左的顺序搜索如果走到最后一层的第一个点一定是最右点 标记一下 再走到后面的这一层的节点时如果不存在 就不是完全二叉树 满足第二点判断
如果刚才两点都没问题 就符合完全二叉树。 code: #includebits/stdc.h
using namespace std;
typedef struct bst
{int d;bst *l,*r;
}NN,*NNN;
int flo;
NNN insert(NNN p,int t,int lev)
{if(p){if(t p-d)p-l insert(p-l,t,lev1);else p-rinsert(p-r,t,lev1);return p;}else{NNN q (NNN)malloc(sizeof(NN));// couttendl;q-dt;q-lq-rNULL;flo max(flo,lev);return q; }
}
bool flag;
bool judge1(NNN p,int lev)
{if(p){if(lev flo)flag1;bool a,b;a judge1(p-r,lev1);b judge1(p-l,lev1);return ab;}else if(levflo-1||(levfloflag))return 0;else return 1;
}
void levelTre(NNN p)
{queueNNNq;q.push(p);while(q.size()){NNN a q.front();q.pop();printf(%d,a-d);if(a-l)q.push(a-l);if(a-r)q.push(a-r);if(q.size())printf( );else puts();}
}
int main()
{int n;cinn;NNN p NULL;for(int i1;in;i){int t;scanf(%d,t);pinsert(p,t,1);}
// coutfloendl;levelTre(p);bool res judge1(p,1);if(res)puts(YES);else puts(NO);return 0;
}