L2-004 这是二叉搜索树吗? (25 分)
发布日期:2021-06-29 22:18:42
浏览次数:2
分类:技术文章
本文共 2255 字,大约阅读时间需要 7 分钟。
如果使用nullptr控制台报[Error] ‘nullptr’ was not declared in this scope错误信息的话,点击下面链接:
[Error] ‘nullptr‘ was not declared in this scope解决方案 一棵二叉搜索树可被递归地定义为具有下列性质的二叉树:对于任一结点,其左子树中所有结点的键值小于该结点的键值;
其右子树中所有结点的键值大于等于该结点的键值; 其左右子树都是二叉搜索树。 所谓二叉搜索树的“镜像”,即将所有结点的左右子树对换位置后所得到的树。给定一个整数键值序列,现请你编写程序,判断这是否是对一棵二叉搜索树或其镜像进行前序遍历的结果。
输入格式:
输入的第一行给出正整数 N(≤1000)。随后一行给出 N 个整数键值,其间以空格分隔。输出格式:
如果输入序列是对一棵二叉搜索树或其镜像进行前序遍历的结果,则首先在一行中输出 YES ,然后在下一行输出该树后序遍历的结果。数字间有 1 个空格,一行的首尾不得有多余空格。若答案是否,则输出 NO。输入样例 1:
7 8 6 5 7 10 8 11 输出样例 1: YES 5 7 6 8 11 10 8 输入样例 2: 7 8 10 11 8 6 7 5 输出样例 2: YES 11 8 10 7 5 6 8 输入样例 3: 7 8 6 8 5 10 9 11 输出样例 3: NO/*题目语句:判断这是否是对一棵二叉搜索树或其镜像进行前序遍历的结果;理解:判断这是否是对一棵二叉搜索树进行前序遍历的结果、镜像进行前序遍历的结果; */#include#include using namespace std;struct BinTree{ int val; struct BinTree *left,*right; };BinTree *create(struct BinTree *root,int val){ if(root==nullptr) { //在c++当中,可以把结构体当做class来使用的,故可以使用new关键字来创建一个新的地址; //此处用(struct BinTree *)malloc(sizeof(struct BinTree))也是可以的; root = new BinTree; root->val=val; root->left=nullptr; root->right=nullptr; return root; } else { if(root->val>val) root->left = create(root->left,val); else root->right=create(root->right,val); } return root;}/*前序遍历--->根左右;该方法的返回值是void,原因是:只需要获取前序遍历的根节点的val就行,不需要进行构造二叉树; */vector pre;void pre_order(struct BinTree *root){ if(root==nullptr) return ; pre.push_back(root->val); pre_order(root->left); pre_order(root->right); }//后续遍历--->左右根; vector post;void post_order(struct BinTree *root){ if(root==nullptr) return; post_order(root->left); post_order(root->right); post.push_back(root->val); }//镜像--->所有结点的左右子树对换位置后所得到的树;BinTree *mirror_order(struct BinTree *root){ if(root==nullptr) return nullptr;//nullptr空指针; root->left = mirror_order(root->left); root->right = mirror_order(root->right); struct BinTree *temp = root->left; root->left = root->right;//左右子树交换位置; root->right = temp; return root;} int main(){ int n=0,num=0,i=0,m=0,j=0,k=0; //vector定义的变量,在遍历时可以使用[]来取出其中的数据,相当于是数组; vector order; struct BinTree *root=nullptr;//c++中的空指针; cin>>n; for(i=0;i >num; root = create(root,num); order.push_back(num); } int flag=0; //判断输入序列是二叉搜索树前序遍历序列的结果; pre_order(root); for(i=0;i
转载地址:https://dingshijie.blog.csdn.net/article/details/115838668 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
能坚持,总会有不一样的收获!
[***.219.124.196]2024年04月07日 11时51分31秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
oracle往表插入特殊字符&
2019-04-30
oracle中的merge命令
2019-04-30
docker安装mysql
2019-04-30
jfinal排查过滤拦截相关请求
2019-04-30
java文件管道拷贝工具类
2019-04-30
mysql连接信息jdbcUrl的常用写法
2019-04-30
HTML页面meta标签内容详解
2019-04-30
oracle之decode
2019-04-30
oracle列转换成行
2019-04-30
nginx设置开启启动
2019-04-30
linux中设置tomcat自启动
2019-04-30
mysql错误:Row size too large (> 8126).
2019-04-30
umount时目标忙解决办法
2019-04-30
java 判断一个url是否可以访问的方法
2019-04-30
Table 'mysql.user' doesn't exist
2019-04-30
mysql通过frm文件查找表结构定义
2019-04-30
如何在删除ibdata1和ib_logfile的情况下恢复MySQL数据库
2019-04-30
oracle随机数的产生
2019-04-30
oracle分级汇总rollup
2019-04-30