当前位置：网站首页>二叉树的4种遍历的递归与非递归实现
二叉树的4种遍历的递归与非递归实现
2022-07-21 05:03:00 【萝卜炖着吃】
二叉树的4种遍历的递归与非递归实现
前言
数据结构老师又开始水了，不对，是一直水！只好自学了。代码里面有关键步骤的注释，发个帖子记录一下。
创建一个二叉树
构造一个二叉树
#include<iostream>
using namespace std;
const int max = 100;
typedef char datatype;
typedef struct node {
//二叉树结点
datatype data;
node* left;
node* right;
}*bitree; //bitree为结点指针
//创建二叉树时要用结点指针的引用或指针，不然就是简单的指针拷贝，无法创建二叉树
void createBitree(bitree& t) {
char ch;
cin >> ch;
if (ch == '#') //#为空结点
t = nullptr;
else {
t = new node;
t->data = ch;
createBitree(t->left);
createBitree(t->right);
}
}
创建存放二叉树指针的栈
typedef struct seqstack {
//顺序栈
bitree array[max]; //保存二叉树结点指针
int top;
}*pstack;
void push(pstack s, bitree t) {
if (s->top == max)
cout << "栈已满！\n";
else
s->array[++s->top] = t;
}
void pop(pstack s,bitree &t) {
if (s->top == -1)
cout << "栈已空！\n";
else
t= s->array[s->top--];
}
创建存放二叉树指针的队列
typedef struct seqqueue {
//顺序队
bitree array[max];
int front;
int rear;
}*pqueue;
void push(pqueue q, bitree t) {
if (q->rear == max)
cout << "队已满！\n";
else
q->array[q->rear++] = t;
}
void pop(pqueue q, bitree& t) {
if (q->front == q->rear)
cout << "队已空！\n";
else
t = q->array[q->front++];
}
递归版前序遍历
void preTraverse(bitree t) {
if (!t)
return;
cout << t->data;
preTraverse(t->left);
preTraverse(t->right);
}
非递归版前序遍历
void Non_re_preTraverse(bitree t) {
seqstack s;
s.top = -1;
if(!t)
cout << "这是空树!";
else {
while (t || s.top != -1) {
while (t) {
//当这个结点非空时输出并入栈保存，以便左子节点为空时回溯父节点
cout << t->data;
push(&s, t);
t = t->left;
}
pop(&s,t); //左子节点为空，回溯找到父节点
t = t->right; //进入右子节点
}
}
}
递归版中序遍历
void inTraverse(bitree t) {
if (!t)
return;
inTraverse(t->left);
cout << t->data;
inTraverse(t->right);
}
非递归版中序遍历
void Non_re_inTraverse(bitree t) {
seqstack s;
s.top = -1;
if (!t)
cout << "这是空树!";
else {
while (t || s.top != -1) {
while (t) {
//当这个结点非空时入栈保存，以便左子节点为空时回溯父节点
push(&s, t);
t = t->left;
}
pop(&s,t); //左子节点为空，回溯找到父节点
cout << t->data; //输出
t = t->right; //进入右子节点
}
}
}
递归版后序遍历
void postTraverse(bitree t) {
if (!t)
return;
postTraverse(t->left);
postTraverse(t->right);
cout << t->data;
}
非递归版后序遍历
//一个鸡贼的方法,把前序遍历变种，所有的left,right互换就得到后序遍历的逆序，再逆序输出得到后序遍历结果
void Non_re_postTraverse(bitree t) {
datatype array[max]; //保存后序遍历的逆序
int i = -1; //方便使用++i
seqstack s;
s.top = -1;
if (!t)
cout << "这是空树!";
else {
while (t || s.top != -1) {
while (t) {
//当这个结点非空时保存数据并入栈保存，以便右子节点为空时回溯父节点
array[++i]=t->data;
push(&s, t);
t = t->right;
}
pop(&s,t); //右子节点为空，回溯找到父节点
t = t->left; //进入左子节点
}
while (i >= 0) {
cout << array[i--]; //倒序输出
}
}
}
层序遍历
void levelTraverse(bitree t) {
seqqueue q;
q.front = 0;
q.rear = 0;
if(!t)
cout << "这是空树!";
else {
push(&q, t); //根结点入队
while(q.front!=q.rear){
//只要队头队尾不等就输出
pop(&q, t);
cout << t->data;
if (t->left) //有左子结点就入队
push(&q, t->left);
if (t->right) //有右子结点就入队
push(&q, t->right);
}
}
}
测试数据
int main() {
//测试数据AB#C##DE###，以#表示空结点，当然也可以换其他的，只需要在相应函数一并修改符号
bitree t;
cout << "请输入数据：";
createBitree(t);
cout << "\n前序遍历：";
preTraverse(t);
cout << "\n中序遍历：";
inTraverse(t);
cout << "\n后序遍历：";
postTraverse(t);
cout << "\n非递归前序遍历：";
Non_re_preTraverse(t);
cout << "\n非递归中序遍历：";
Non_re_inTraverse(t);
cout << "\n非递归后序遍历：";
Non_re_postTraverse(t);
cout << "\n层序遍历：";
levelTraverse(t);
return 0;
}
完整代码
#include<iostream>
using namespace std;
const int max = 100;
typedef char datatype;
typedef struct node {
datatype data;
node* left;
node* right;
}*bitree; //bitree为结点指针
typedef struct seqstack {
//顺序栈
bitree array[max]; //保存二叉树结点指针
int top;
}*pstack;
void push(pstack s, bitree t) {
if (s->top == max)
cout << "栈已满！\n";
else
s->array[++s->top] = t;
}
void pop(pstack s,bitree &t) {
if (s->top == -1)
cout << "栈已空！\n";
else
t= s->array[s->top--];
}
typedef struct seqqueue {
//顺序队
bitree array[max];
int front;
int rear;
}*pqueue;
void push(pqueue q, bitree t) {
if (q->rear == max)
cout << "队已满！\n";
else
q->array[q->rear++] = t;
}
void pop(pqueue q, bitree& t) {
if (q->front == q->rear)
cout << "队已空！\n";
else
t = q->array[q->front++];
}
//创建二叉树时要用结点指针的引用或指针，不然就是简单的指针拷贝，无法创建二叉树
void createBitree(bitree& t) {
char ch;
cin >> ch;
if (ch == '#') //#表示为空结点
t = nullptr;
else {
t = new node;
t->data = ch;
createBitree(t->left);
createBitree(t->right);
}
}
void Non_re_preTraverse(bitree t) {
seqstack s;
s.top = -1;
if(!t)
cout << "这是空树!";
else {
while (t || s.top != -1) {
while (t) {
//当这个结点非空时输出并入栈保存，以便左子节点为空时回溯父节点
cout << t->data;
push(&s, t);
t = t->left;
}
pop(&s,t); //左子节点为空，回溯找到父节点
t = t->right; //进入右子节点
}
}
}
void Non_re_inTraverse(bitree t) {
seqstack s;
s.top = -1;
if (!t)
cout << "这是空树!";
else {
while (t || s.top != -1) {
while (t) {
//当这个结点非空时入栈保存，以便左子节点为空时回溯父节点
push(&s, t);
t = t->left;
}
pop(&s,t); //左子节点为空，回溯找到父节点
cout << t->data; //输出
t = t->right; //进入右子节点
}
}
}
//一个鸡贼的方法,把前序遍历变种，所有的left,right互换就得到后序遍历的逆序，再逆序输出得到后序遍历结果
void Non_re_postTraverse(bitree t) {
datatype array[max]; //保存后序遍历的逆序
int i = -1; //方便使用++i
seqstack s;
s.top = -1;
if (!t)
cout << "这是空树!";
else {
while (t || s.top != -1) {
while (t) {
//当这个结点非空时保存数据并入栈保存，以便右子节点为空时回溯父节点
array[++i]=t->data;
push(&s, t);
t = t->right;
}
pop(&s,t); //右子节点为空，回溯找到父节点
t = t->left; //进入左子节点
}
while (i >= 0) {
cout << array[i--]; //倒序输出
}
}
}
void levelTraverse(bitree t) {
seqqueue q;
q.front = 0;
q.rear = 0;
if(!t)
cout << "这是空树!";
else {
push(&q, t); //根结点入队
while(q.front!=q.rear){
//只要队头队尾不等就输出
pop(&q, t);
cout << t->data;
if (t->left) //有左子结点就入队
push(&q, t->left);
if (t->right) //有右子结点就入队
push(&q, t->right);
}
}
}
void preTraverse(bitree t) {
if (!t)
return;
cout << t->data;
preTraverse(t->left);
preTraverse(t->right);
}
void inTraverse(bitree t) {
if (!t)
return;
inTraverse(t->left);
cout << t->data;
inTraverse(t->right);
}
void postTraverse(bitree t) {
if (!t)
return;
postTraverse(t->left);
postTraverse(t->right);
cout << t->data;
}
int main() {
//测试数据AB#C##DE###，以#表示空结点，当然也可以换其他的，只需要在相应函数一并修改符号
bitree t;
cout << "请输入数据：";
createBitree(t);
cout << "\n前序遍历：";
preTraverse(t);
cout << "\n中序遍历：";
inTraverse(t);
cout << "\n后序遍历：";
postTraverse(t);
cout << "\n非递归前序遍历：";
Non_re_preTraverse(t);
cout << "\n非递归中序遍历：";
Non_re_inTraverse(t);
cout << "\n非递归后序遍历：";
Non_re_postTraverse(t);
cout << "\n层序遍历：";
levelTraverse(t);
return 0;
}
结尾
各位大佬如果觉得这篇文章对你有帮助的话，不妨给卑微博主点个赞吧。
边栏推荐
- 基于GeoServer开发的地理场景可视化系统
- CentOS 8中Docker安装MySQL8
- Development tools supporting data + code generation, yyds
- How to successfully get offers from ant, jd.com, Xiaomi, Tencent and other major manufacturers
- Linux redis-6.2.6 stand alone deployment
- LeetCode 76. Minimum covering substring sliding window method
- One of the project optimization: the installation and use of redis cache database in the project, and strengthen the project reading operation
- Nacos-配置中心原理解析
- 学习IO由浅入深
- Rewrite hashcode() to compare whether the classes are the same
猜你喜欢
随机推荐
数据库针对上面的salaries表emp_no字段创建索引idx_emp_no
Service层和Dao层真的有必要每个类都加上接口吗
MySQL之DQL（数据查询语言）- 表连接查询
类加载器及双亲委派机制
flutter自定义form表单，封装form表单组件
Wechat public number Development Access, Application for Test number for Local Development Using Wechat public Platform
Judge whether there are duplicate values in the "string []" array, and use the HashSet feature to check
Web. Config custom class reading
fastJson数据类型中，解析JSONObject出现$ref: “$.list[0]“问题
以独占的方式锁定此配置文件失败。另一个正在运行的VMware进程可能正在使用配置文件。
Six relationships between UML models and classes
RSA公私钥加密工具类
NIO三大核心详解
self-attention注意力原理
对项目优化之一：redis缓存数据库的安装与项目中使用，加强项目读取操作
数据库删除emp_no重复的记录，只保留最小的id对应的记录
Three paradigms of database design in MySQL
高并发常用辅助类
Linux redis-6.2.6 stand alone deployment
Address Book Implementation