本文共 2254 字，大约阅读时间需要 7 分钟。
题目：
将一系列给定数字顺序插入一个初始为空的二叉搜索树（定义为左子树键值大，右子树键值小），你需要判断最后的树是否一棵完全二叉树，并且给出其层序遍历的结果。
输入格式： 输入第一行给出一个不超过20的正整数N；第二行给出N个互不相同的正整数，其间以空格分隔。
输出格式： 将输入的N个正整数顺序插入一个初始为空的二叉搜索树。在第一行中输出结果树的层序遍历结果，数字间以1个空格分隔，行的首尾不得有多余空格。第二行输出YES，如果该树是完全二叉树；否则输出NO。
输入样例1： 938 45 42 24 58 30 67 12 51
输出样例1：
38 45 24 58 42 30 12 67 51YES
输入样例2：
838 24 12 45 58 67 42 51
输出样例2：
38 45 24 58 42 12 67 51NO
#include using namespace std;typedef struct NODE{ int data; struct NODE *left; struct NODE *right;} NODE,*TREE;bool first=true;TREE build(TREE tree,int x){ if(!tree) { tree=(NODE*)malloc(sizeof(NODE)); tree->data=x; tree->left=NULL; tree->right=NULL; } else if(tree->data left=build(tree->left,x); else tree->right=build(tree->right,x); return tree;}int GetHeight( TREE BT ){ if(BT==NULL) return 0; int l=0,r=0; if(BT->left!=NULL) l=GetHeight(BT->left); if(BT->right!=NULL) r=GetHeight(BT->right); return l>r?l+1:r+1;}void dfs(TREE BT,int i,int c){ if(BT==NULL) return; if(c==i) { if(first) cout< data; else cout<<' '< data; first=false; return; } dfs(BT->left,i,c+1); dfs(BT->right,i,c+1);}int LevelorderTraversal(TREE BT ){ int h=GetHeight(BT); for(int i=0; i left==NULL&&tree->right==NULL)// { // h=i;// flag=false;// }// }// return judge(tree->left,h,i+1,flag)&&judge(tree->right,h,i+1,flag);//}bool judge(TREE T){ if (T == NULL) return false; queue Q; Q.push(T); while (!Q.empty()) { TREE p = Q.front(); Q.pop(); if (p->left && p->right) { Q.push(p->left); Q.push(p->right); } else if(p->right && p->left == NULL) return false; else { if(p->left && p->right == NULL) Q.push(p->left); while(!Q.empty()) { p = Q.front(); Q.pop(); if(p->left || p->right) return false; } } } return true;}int main(){ //freopen("in.txt","r",stdin); int n; cin>>n; int a[21]; TREE base_tree=NULL; for(int i=0; i >a[i]; base_tree=build(base_tree,a[i]); } int h=LevelorderTraversal(base_tree); bool flag=true; cout<
更多PTA代码请到我的博客里参考
ps：代码仅供参考，请勿抄袭
转载地址：http://pmqbi.baihongyu.com/