L3-010 是否完全二叉搜索树 (30 分)
发布日期:2021-06-29 22:18:47
浏览次数:3
分类:技术文章
本文共 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月21日 07时08分20秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
Borland C++Builder 3 VS Delphi 3
2019-04-30
用 C++Builder 编制文本编辑器
2019-04-30
C++Builder中大尺寸图像的显示技巧
2019-04-30
C++Builder中各种资源的利用
2019-04-30
画控件的几个函数
2019-04-30
C++Builder的基本功能
2019-04-30
C++Builder及VC的DLL相互调用解决方案
2019-04-30
用C++ Builder XE 10编译生成EXE运行问题
2019-04-30
BUilder高效率代码
2019-04-30
Builder聊天
2019-04-30
Builder中使用Access数据库
2019-04-30
C++ Builder VCL库函数简介
2019-04-30
DistanceInEarth
2019-04-30
earth
2019-04-30
pb6.5技巧
2019-04-30
详解Oracle数据库备份恢复
2019-04-30
诺基亚新动作!自创开源Linux内存分析器—Memory Profiler
2019-04-30
人工智能-OpenCV+Python实现人脸识别(视频人脸检测)
2019-04-30
【数据统计分析】详解Oracle分组函数之CUBE
2019-04-30
起泡法的使用
2019-04-30