本文共 2460 字，大约阅读时间需要 8 分钟。

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

输入格式：

输入第一行给出一个不超过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

#include
   
    #include
    
     #include
     
      using namespace std;struct BinTree{
   	int value;	struct BinTree *left,*right;};//根据输入的数据，构建一个二叉树; BinTree *createTree(struct BinTree *root,int value){
   	if(root==nullptr)	{
   		root = new BinTree;		root->value = value; 		root->left=root->right=nullptr;		return root; 	}	else	{
   		if(value>root->value) root->left=createTree(root->left,value);		else root->right=createTree(root->right,value);		}	return root;}//前序遍历: //vector
      
        t;//void preOrder(struct BinTree *root)//{
   //	if(root==nullptr) return;//	t.push_back(root->value);//	preOrder(root->left);//	preOrder(root->right);//}//队列输出实现层序遍历;vector
       
         que; void queueOrder(struct BinTree *root){
   	struct BinTree *temp=nullptr;	queue
        
          q; if(root==nullptr) return; q.push(root);//插入队尾; while(!q.empty()) { temp = q.front();//取出队首元素; q.pop();//弹出队首元素; que.push_back(temp->value); if(temp->left!=nullptr) q.push(temp->left); if(temp->right!=nullptr) q.push(temp->right); }}/*判断条件: 1、树空，直接返回false;2、左子树为空，右子树不为空，直接返回false;3、左子树不为空，右子树为nullptr,或之后的左右节点都为nullptr，空且之后的结点有非叶子节点，则返回false; 4、左右子树都不为空，将左右子树依次插入到队列尾部; */int checked(struct BinTree *root){ if(root==nullptr) return 0; queue
         
           q; struct BinTree *temp=nullptr; q.push(root); while(!q.empty()) { temp = q.front();//取队首元素; q.pop();//弹出队首元素; if(temp->left!=nullptr&&temp->right!=nullptr) { q.push(temp->left); q.push(temp->right); } if(temp->left==nullptr&&temp->right!=nullptr) return 0; //左子树不为空，右子树为空||左右子树都为空， 需要判断后面是否有非叶子结点; if(temp->left!=nullptr&&temp->right==nullptr||temp->left==nullptr&&temp->right==nullptr) { if(temp->left!=nullptr&&temp->right==nullptr) q.push(temp->left);//插入到队尾; //循环该节点之后的结点是否存在非叶子节点; while(!q.empty()) { temp=q.front(); q.pop(); //如果左右子树都为空，则该结点是叶子结点，则pop(),继续判断下一个结点; if(temp->left==nullptr&&temp->right==nullptr) q.pop(); else return 0;//存在非叶子节点; } } } return 1;}int main(){ struct BinTree *root=nullptr; int n=0,m=0,i=0,j=0,num=0; cin>>n; for(i=0;i
          
           >num; root=createTree(root,num); } //层序序列; queueOrder(root); for(i=0;i
          
         
        
       
      
     
    
   

转载地址：http://fevcf.baihongyu.com/