L3-010 是否完全二叉搜索树 (30 分)
发布日期:2021-06-29 22:18:47
浏览次数:2
分类:技术文章
本文共 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
转载地址:https://dingshijie.blog.csdn.net/article/details/115932186 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
关注你微信了!
[***.104.42.241]2024年04月04日 09时43分58秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
MySQL 简介
2019-04-30
SQL语言
2019-04-30
数据库访问接口
2019-04-30
启动 MySQL服务
2019-04-30
登录MySQL数据库
2019-04-30
MySQL 常用图形管理工具
2019-04-30
MySQL 创建数据库
2019-04-30
查看MySQL数据库定义信息
2019-04-30
MySQL 查看存储引擎
2019-04-30
MySQL 删除数据库
2019-04-30
TypeScript 安装
2019-04-30
TypeScript 基础类型
2019-04-30
typescript 用name作为变量名报错的原因
2019-04-30
TypeScript 变量声明
2019-04-30
typeScript 变量作用域
2019-04-30
TypeScript 运算符
2019-04-30
TypeScript 条件语句
2019-04-30
微信小程序 响应的数据绑定
2019-04-30
微信小程序框架
2019-04-30
微信小程序 场景值
2019-04-30