基于非链式(数组)结点结构的二叉树的前(先)序输入创建以及遍历

news/2024/5/20 20:53:07

点击链接返回标题->基于非链式(数组)结点结构的二叉树的层序、先序、中序、后序输入创建以及层序、先序、中序、后序输出-CSDN博客


我们采用递归的思想,不断去找空结点(值为-1的结点),在找空结点这个过程中,将输入的x的值(即有效结点)“顺路”插入树中,直到发现输入的值是-1,也就是来到了空结点的位置,延递归路线返回即可,并遵循“先递归左子树,再递归右子树”的顺序,也就是先序的根左右

#include<iostream>
using namespace std;
typedef int datatype;
const int MAX = 8;
struct binTree {datatype tree[2 * MAX + 7];//该数组的最大容量必须超过最大结点数的两倍,用以存放空结点!int size;//当前有效结点个数
};void create_tree_pre(binTree* tree, int i = 1) {//按先序创建二叉树int x;cin >> x;if (x != -1) {tree->tree[i] = x;tree->size++;}else return;//如果当前插入结点是-1的话,显然当前递归路线该返回了create_tree_pre(tree, i * 2);create_tree_pre(tree, i * 2 + 1);
}void travse_pre(binTree* tree, int i = 1) {//二叉树的先序遍历if (tree->tree[i] == -1) return;//访问到空结点,该递归路线需要返回//根,左,右printf("%d	", tree->tree[i]);travse_pre(tree, i * 2);travse_pre(tree, i * 2 + 1);
}

完整测试代码如下:

样例输入:

1 2 4 -1 -1 5 -1 -1 3 6 -1 -1 7 -1 -1

样例输出:

层序遍历结果——1       2       3       4       5       6       7
先序遍历结果——1       2       4       5       3       6       7
中序遍历结果——4       2       5       1       6       3       7
后序遍历结果——4       5       2       6       7       3       1

#include<iostream>
using namespace std;
typedef int datatype;
const int MAX = 8;
struct binTree {datatype tree[2 * MAX + 7];//该数组的最大容量必须超过最大结点数的两倍,用以存放空结点!int size;//当前有效结点个数
};void create_tree_pre(binTree* tree, int i = 1) {//按先序创建二叉树int x;cin >> x;if (x != -1) {tree->tree[i] = x;tree->size++;}else return;//如果当前插入结点是-1的话,显然当前递归路线该返回了create_tree_pre(tree, i * 2);create_tree_pre(tree, i * 2 + 1);
}void travse_seq(binTree* tree) {//二叉树的层序遍历int len = tree->size, i = 1;while (len) {if (tree->tree[i] != -1) {//访问到的不是空结点就输出,并让len自减,len为0时所有有效结点均被输出printf("%d	", tree->tree[i++]);len--;}}
}
void travse_pre(binTree* tree, int i = 1) {//二叉树的先序遍历if (tree->tree[i] == -1) return;//访问到空结点,该递归路线需要返回//根,左,右printf("%d	", tree->tree[i]);travse_pre(tree, i * 2);travse_pre(tree, i * 2 + 1);
}
void travse_mid(binTree* tree, int i = 1) {//二叉树的中序遍历if (tree->tree[i] == -1) return;//左,根,右travse_mid(tree, i * 2);printf("%d	", tree->tree[i]);travse_mid(tree, i * 2 + 1);
}
void travse_nex(binTree* tree, int i = 1) {//二叉树的后序遍历if (tree->tree[i] == -1) return;//左,右,根travse_nex(tree, i * 2);travse_nex(tree, i * 2 + 1);printf("%d	", tree->tree[i]);
}
void test(binTree* tree) {create_tree_pre(tree);cout << "层序遍历结果——";travse_seq(tree);cout << endl;cout << "先序遍历结果——";travse_pre(tree);cout << endl;cout << "中序遍历结果——";travse_mid(tree);cout << endl;cout << "后序遍历结果——";travse_nex(tree);cout << endl;
}
int main() {binTree tree;tree.size = 0;memset(tree.tree, -1, sizeof(tree.tree));//初始化树的相关信息test(&tree);
}


https://www.xjx100.cn/news/3092569.html

相关文章

golang学习笔记——接口和继承比较1

继承 Go 语言的设计之初&#xff0c;就不打算支持面向对象的编程特性&#xff0c;因此 Go 不支持面向对象的三大特性之一——继承。但是 Go 可以通过组合的思想去实现 “继承”。继承是面向对象的三大特性之一&#xff0c;继承是从已有的类中派生出新的类&#xff0c;新的类能…

UEC++ day7

敌人NPC机制 敌人机制分析与需求 新建一个character类来作为敌人&#xff0c;直接建蓝图设置骨骼网格&#xff0c;因为敌人可能多种就不规定死&#xff0c;然后这个敌人肯定需要两个触发器&#xff0c;一个用于大范围巡逻&#xff0c;一个用于是否达到主角近点进行攻击 注意我…

ChatGPT/GPT4科研实践应用与AI绘图技术及论文高效写作

2023年随着OpenAI开发者大会的召开&#xff0c;最重磅更新当属GPTs&#xff0c;多模态API&#xff0c;未来自定义专属的GPT。微软创始人比尔盖茨称ChatGPT的出现有着重大历史意义&#xff0c;不亚于互联网和个人电脑的问世。360创始人周鸿祎认为未来各行各业如果不能搭上这班车…

详解Python安装requests库的实例代码

文章目录 前言基本用法基本的get请求带参数的GET请求解析json关于Python技术储备一、Python所有方向的学习路线二、Python基础学习视频三、精品Python学习书籍四、Python工具包项目源码合集①Python工具包②Python实战案例③Python小游戏源码五、面试资料六、Python兼职渠道 前…

2021年03月 Scratch(二级)真题解析#中国电子学会#全国青少年软件编程等级考试

Scratch等级考试(1~4级)全部真题・点这里 一、单选题(共25题,每题2分,共50分) 第1题 小猫在沙漠中旅行好不容易找到了一杯水,初始位置如下图所示,下面哪个程序可以帮助它成功喝到水? A: B: C: D:

ES学习看这一篇文章就够了

ES学习看这一篇文章就够了 ES学习看这一篇文章就够了-CSDN博客

webpack 创建typescript项目

【视频链接】尚硅谷TypeScript教程&#xff08;李立超老师TS新课&#xff09; 创建webpack 项目 IDE&#xff1a;webstorm 新建一个空的项目运行npm init初始化项目目录结构 1. 安装 webpack&#xff1a;构建工具webpack-cli&#xff1a; webpack的命令行工具typescript&am…

【机器学习】032_多种神经网络层类型

一、密集层 每一层神经元都是上一层神经元的函数&#xff0c;每层每个神经元都从前一层获得所有激活的输入。 整个神经网络前一层与后一层连接在一起&#xff0c;构造的网络密集。 二、卷积层 假设有一张大小为axb像素的图片&#xff0c;上面标着一些手写数字&#xff0c…