当前位置: 首页 > news >正文

【二叉树】C非递归算法实现二叉树的先序、中序、后序遍历

引言:

遍历二叉树:指按某条搜索路径巡访二叉树中每个结点,使得每个结点均被访问一次,而且仅被访问一次。
除了层次遍历外,二叉树有三个重要的遍历方法:先序遍历、中序遍历、后序遍历。
1、递归算法实现先序、中序、后序遍历:

(1)先序遍历:

void PreOrderTraverse(BiTree T)
{if(T){cout<<T->data;PreOrderTraverse(T->lchild);PreOrderTraverse(T->rchild);}
}

(2)中序遍历:

void InOrderTraverse(BiTree T)
{   if(T){InOrderTraverse(T->lchild);cout<<T->data;InOrderTraverse(T->rchild);}
} 

(3)后序遍历

void PostOrderTraverse(BiTree T)
{   if(T){  PostOrderTraverse(T->lchild); PostOrderTraverse(T->rchild); cout<<T->data;   }
} 

2.非递归算法实现先序、中序、后序遍历:

采用非递归算法则需要利用栈来实现对二叉树的遍历:
(1)先序遍历非递归算法

void  PreOrder_non_recursion(BiTree T)//先序遍历的非递归算法 
{LinkStack S;InitStack (S);   BiTree p,q;p=T;while(p||!StackEmpty(S)){if(p){Push(S,*p); cout<<p->data; //访问根节点 p=p->lchild;   //遍历左子树 }else{Pop(S,*q);p=q->rchild;   //遍历右子树 }}
}

(2)中序遍历非递归算法

void  InOrder_non_recursion(BiTree T)//中序遍历的非递归算法 
{LinkStack S;InitStack (S);   BiTree p;    BiTree q; p=T;while(p||!StackEmpty(S)){if(p){Push(S,*p); p=p->lchild;   //遍历左子树 }else{Pop(S,*q);cout<<q->data; //访问根节点 p=q->rchild;   //遍历右子树 }}
}

(3)后序遍历非递归算法
(采用非递归算法实现对二叉树的后序遍历,会稍微复杂一些,本算法借用了两个栈结构)

void  PostOrder_non_recursion(BiTree T)//后序遍历的非递归算法 
{LinkStack l_S,r_S;InitStack (l_S);InitStack (r_S);BiTree p,q;    p=T;Push(l_S,*p);while(!StackEmpty(l_S)){Pop(l_S, *q);Push(r_S,*q);if(q->lchild){Push(l_S, *q->lchild);}if(q->rchild){Push(l_S,*q->rchild);}}while(!StackEmpty(r_S)){Pop(r_S,*q);cout<<q->data;}
}

3.完整代码

1、采用按照先序遍历的顺序建立二叉链表,用‘#’表示空树。如图所示:
在这里插入图片描述
2、先序遍历的递归与非递归算法的对比:

#include<iostream>
#define OK 1
#define ERROR 0
#define OVERFLOW -2
using namespace std;
typedef char TElemType;
typedef int Status;typedef struct BiTNode{  //二叉树的存储结构TElemType   data;	// 数据域struct  BiTNode *lchild; //左孩子指针struct  BiTNode *rchild; //右孩子指针
}BiTNode, *BiTree;typedef struct StackNode {  //栈的存储结构BiTNode data;       //栈数据元素类型为树结点型 struct StackNode *next;
} StackNode, *LinkStack;Status InitStack(LinkStack &S) { //栈初始化S = NULL;return OK;
}Status Push(LinkStack &S, BiTNode e) { //入栈LinkStack p;p = new StackNode; //生成新结点if (!p) {return OVERFLOW;}p->data = e; //将新结点数据域置为ep->next = S; //将新结点插入栈顶S = p; //修改栈顶指针为preturn OK;
}Status Pop(LinkStack &S, BiTNode &e) {  //出栈LinkStack p;if (S == NULL)return ERROR; //栈空e = S->data; //将栈顶元素赋给ep = S; //用p临时保存栈顶元素空间,以备释放S = S->next; //修改栈顶指针delete p; //释放原栈顶元素的空间return OK;
}bool StackEmpty(LinkStack S) {  //判断是否空栈if (!S)return true;return false;
}void CreateBiTree_PreOrder(BiTree &T){ //以先序次序创建二叉树 char ch; cin>>ch;if(ch=='#')T=NULL; else{T=new BiTNode;  //生成根结点T->data=ch; //根结点的数据域置为chCreateBiTree_PreOrder(T->lchild);//构造左子树CreateBiTree_PreOrder(T->rchild); //构造右子树}}void PreOrder(BiTree T){   //先序遍历的递归递归算法if(T){cout<<T->data;PreOrder(T->lchild);PreOrder(T->rchild);}
}void  PreOrder_non_recursion(BiTree T)//先序遍历的非递归算法 
{LinkStack S;InitStack (S);   BiTree p,q;p=T;while(p||!StackEmpty(S)){if(p){Push(S,*p); cout<<p->data; //访问根节点 p=p->lchild;   //遍历左子树 }else{Pop(S,*q);p=q->rchild;   //遍历右子树 }}
}int main() {BiTree T;cout<<"以先序次序创建二叉链表,以#表示空子树:"<<endl;CreateBiTree_PreOrder(T);cout<<"先序序列(递归算法):"; PreOrder(T); cout<<"\n先序序列(非递归算法):"; PreOrder_non_recursion(T);return 0;
}

实验结果:
在这里插入图片描述
3、中序遍历的递归与非递归算法的对比:

#include<iostream>
#define OK 1
#define ERROR 0
#define OVERFLOW -2
using namespace std;
typedef char TElemType;
typedef int Status;typedef struct BiTNode{  //二叉树的存储结构TElemType   data;	// 数据域struct  BiTNode *lchild; //左孩子指针struct  BiTNode *rchild; //右孩子指针
}BiTNode, *BiTree;typedef struct StackNode {  //栈的存储结构BiTNode data;       //栈数据元素类型为树结点型 struct StackNode *next;
} StackNode, *LinkStack;Status InitStack(LinkStack &S) { //栈初始化S = NULL;return OK;
}Status Push(LinkStack &S, BiTNode e) { //入栈LinkStack p;p = new StackNode; //生成新结点if (!p) {return OVERFLOW;}p->data = e; //将新结点数据域置为ep->next = S; //将新结点插入栈顶S = p; //修改栈顶指针为preturn OK;
}Status Pop(LinkStack &S, BiTNode &e) {  //出栈LinkStack p;if (S == NULL)return ERROR; //栈空e = S->data; //将栈顶元素赋给ep = S; //用p临时保存栈顶元素空间,以备释放S = S->next; //修改栈顶指针delete p; //释放原栈顶元素的空间return OK;
}bool StackEmpty(LinkStack S) {  //判断是否空栈if (!S)return true;return false;
}void CreateBiTree_PreOrder(BiTree &T){ //以先序次序创建二叉树 char ch; cin>>ch;if(ch=='#')T=NULL; else{T=new BiTNode;  //生成根结点T->data=ch; //根结点的数据域置为chCreateBiTree_PreOrder(T->lchild);//构造左子树CreateBiTree_PreOrder(T->rchild); //构造右子树}}void InOrder(BiTree T){   //中序遍历的递归递归算法if(T){InOrder(T->lchild);cout<<T->data;InOrder(T->rchild);}
}void  InOrder_non_recursion(BiTree T)//中序遍历的非递归算法 
{LinkStack S;InitStack (S);   BiTree p;    BiTree q; p=T;while(p||!StackEmpty(S)){if(p){Push(S,*p); p=p->lchild;   //遍历左子树 }else{Pop(S,*q);cout<<q->data; //访问根节点 p=q->rchild;   //遍历右子树 }}
}int main() {BiTree T;cout<<"以先序次序创建二叉链表,以#表示空子树:"<<endl;CreateBiTree_PreOrder(T);cout<<"中序序列(递归算法):"; InOrder(T); cout<<"\n中序序列(非递归算法):"; InOrder_non_recursion(T);return 0;
}

实验结果:
在这里插入图片描述

4、后序遍历的递归与非递归算法的对比:

#include<iostream>
#define OK 1
#define ERROR 0
#define OVERFLOW -2
using namespace std;
typedef char TElemType; 
typedef int Status;typedef struct BiTNode{  //二叉树的存储结构TElemType   data;	// 数据域struct  BiTNode *lchild; //左孩子指针struct  BiTNode *rchild; //右孩子指针
}BiTNode, *BiTree;typedef struct StackNode {  //栈的存储结构BiTNode data;       //栈数据元素类型为树结点型 struct StackNode *next;
} StackNode, *LinkStack;Status InitStack(LinkStack &S) { //栈初始化S = NULL;return OK;
}Status Push(LinkStack &S, BiTNode e) { //入栈LinkStack p;p = new StackNode; //生成新结点if (!p) {return OVERFLOW;}p->data = e; //将新结点数据域置为ep->next = S; //将新结点插入栈顶S = p; //修改栈顶指针为preturn OK;
}Status Pop(LinkStack &S, BiTNode &e) {  //出栈LinkStack p;if (S == NULL)return ERROR; //栈空e = S->data; //将栈顶元素赋给ep = S; //用p临时保存栈顶元素空间,以备释放S = S->next; //修改栈顶指针delete p; //释放原栈顶元素的空间return OK;
}bool StackEmpty(LinkStack S) {  //判断是否空栈if (!S)return true;return false;
}void CreateBiTree_PreOrder(BiTree &T){ //以先序次序创建二叉树 char ch; cin>>ch;if(ch=='#')T=NULL; else{T=new BiTNode;  //生成根结点T->data=ch; //根结点的数据域置为chCreateBiTree_PreOrder(T->lchild);//构造左子树CreateBiTree_PreOrder(T->rchild); //构造右子树}}void PostOrder(BiTree T){   //后序遍历的递归递归算法if(T){PostOrder(T->lchild);PostOrder(T->rchild);cout<<T->data;}
}void  PostOrder_non_recursion(BiTree T)//后序遍历的非递归算法 
{LinkStack l_S,r_S;InitStack (l_S);InitStack (r_S);BiTree p,q;    p=T;Push(l_S,*p);while(!StackEmpty(l_S)){Pop(l_S, *q);Push(r_S,*q);if(q->lchild){Push(l_S, *q->lchild);}if(q->rchild){Push(l_S,*q->rchild);}}while(!StackEmpty(r_S)){Pop(r_S,*q);cout<<q->data;}
}int main() {BiTree T;cout<<"以先序次序创建二叉链表,以#表示空子树:"<<endl;CreateBiTree_PreOrder(T);cout<<"中序序列(递归算法):"; PostOrder(T); cout<<"\n中序序列(非递归算法):"; PostOrder_non_recursion(T);return 0;
}

实验结果:
在这里插入图片描述
欢迎大家一起来交流~

相关文章:

【二叉树】C非递归算法实现二叉树的先序、中序、后序遍历

引言: 遍历二叉树&#xff1a;指按某条搜索路径巡访二叉树中每个结点&#xff0c;使得每个结点均被访问一次&#xff0c;而且仅被访问一次。 除了层次遍历外&#xff0c;二叉树有三个重要的遍历方法&#xff1a;先序遍历、中序遍历、后序遍历。 1、递归算法实现先序、中序、后…...

Android——事件冲突处理

当我们给列表的item设置了点击事件后&#xff0c;又给item中的按钮设置了点击事件&#xff0c;此时item的点击事件会失效。 解决 给item的布局xml中设置以下属性 android:descendantFocusability"blocksDescendants"<LinearLayout xmlns:android"http://sc…...

vue + elementui 全局Loading效果

注&#xff1a;在request请求和响应封装的文件里引入loading&#xff0c;发请求时打开loading&#xff0c;响应时关闭loading&#xff0c;这样每个接口调用时都会有loading效果 &#xff08;1&#xff09; 首先确保项目中安装了element-ui这个依赖包 npm i element-ui -S&…...

深度了解flink(十) JobManager(4) ResourceManager HA

ResourceManager&#xff08;ZK模式&#xff09;的高可用启动流程 ResourceManager启动流程在DefaultDispatcherResourceManagerComponentFactory#create中 public DispatcherResourceManagerComponent create(Configuration configuration,ResourceID resourceId,Executor i…...

【万兴科技-注册_登录安全分析报告】

前言 由于网站注册入口容易被黑客攻击&#xff0c;存在如下安全问题&#xff1a; 暴力破解密码&#xff0c;造成用户信息泄露短信盗刷的安全问题&#xff0c;影响业务及导致用户投诉带来经济损失&#xff0c;尤其是后付费客户&#xff0c;风险巨大&#xff0c;造成亏损无底洞…...

Android启动流程_Zygote阶段

前言 上一篇文档中我们描述了 Android 启动中的 init 启动部分&#xff0c;本片文档将会继续 Android 启动流程的逻辑&#xff0c;继续梳理 Zygote 部分功能。 说明框架 对于 Zygote 进程&#xff0c;要从以下框架说明&#xff1a; 第一点&#xff0c;编译&#xff0c;zygo…...

2022NOIP比赛总结

种花 1.本题是一道前缀和优化加上枚举的问题。先考虑 C 因为 F 是 C 下边随便加一个点&#xff0c;所以只要求出 C 就求出了 F 。 注意到&#xff0c;并没有要求上下行一样&#xff0c;唯一的要求是 C 的两个横要隔一行&#xff0c;这就是问题的突破点&#xff0c;这题很明显…...

Leetcode 排序链表

这段代码的算法思想是 归并排序&#xff0c;一种适合链表的排序方法。它通过递归地将链表拆分成两部分&#xff0c;分别排序&#xff0c;然后合并已排序的部分&#xff0c;从而达到整体排序的目的。以下是代码的中文解释&#xff1a; 算法步骤&#xff1a; 找到链表的中点&…...

哈希函数简介

哈希函数是一种将任意大小的数据输入&#xff08;通常称为“消息”&#xff09;转换为固定大小的输出&#xff08;称为“哈希值”或“摘要”&#xff09;的算法。 主要特点&#xff1a; 1、输出固定长度 无论输入数据的大小如何&#xff0c;哈希函数的输出总是固定长度。例如…...

nginx------正向代理,反向代理生产,以及能否不使用代理详解

在生产环境中&#xff0c;选择使用正向代理还是反向代理取决于具体的应用场景和需求。下面详细解释这两种代理的用处以及为什么在不同情况下会选择它们。 正向代理 (Forward Proxy) 用途 匿名访问&#xff1a; 隐藏客户端的真实 IP 地址&#xff0c;提供隐私保护。常用于绕过…...

iptables限制docker端口禁止某台主机访问(使用DOCKER链和raw表的PREROUTING链)

背景&#xff1a; 在Linux上docker映射了端口&#xff0c;想着对服务端口进行限制指定IP访问&#xff0c;发现在filter表的INPUT链限制无效 环境&#xff1a; 主机192.168.56.132上的docker容器部署了nginx并将容器80端口映射到主机8000端口 [rootlocalhost ~]# docker ps …...

【VM实战】VMware迁移到VirtualBox

VMware 虚拟机开机卸载VMware Tools 调整虚拟磁盘 对于Windows 10及以上的虚拟机&#xff0c;一般VMware默认都会选Nvme固态硬盘。在导出前必须将其改为SATA&#xff0c;否则VirtualBox导入会报Appliance Import错误 (E_INVALIDARG 0x80070057) 先删掉当前盘的挂载&#xff…...

Android WebView加载不到cookie

以下配置根据需求酌情添加&#xff0c;建议逐个试验&#xff0c;cookie操作不是内存操作&#xff0c;建议修改配置后卸载app再重新运行防止缓存影响测试结果。 1.设置应用程序的 WebView 实例是否应发送并接受 Cookie CookieManager cookieManager CookieManager.getInstanc…...

c++qt

1.显示画布 #include "code.h" #include <QtWidgets/QApplication> #include<iostream> #include<vector> #include <QWindow> #include <QGraphicsView> #include <QGraphicsScene>using namespace std;//1.空格 2.墙 3.入口…...

零跑汽车嵌入式面试题汇总及参考答案

C++ 的三大特性是什么? C++ 的三大特性分别是封装、继承和多态。 封装 概念:封装是把数据和操作数据的函数绑定在一起,对数据的访问进行限制。通过将数据成员声明为私有或保护,只允许通过公共的成员函数来访问和修改数据,从而隐藏了类的内部实现细节。这有助于提高代码的安…...

LC:贪心题解

文章目录 376. 摆动序列 376. 摆动序列 题目链接&#xff1a;https://leetcode.cn/problems/wiggle-subsequence/description/ 这个题目自己首先想到的是动态规划解题&#xff0c;贪心解法真的非常妙&#xff0c;参考下面题解&#xff1a;https://leetcode.cn/problems/wiggle…...

ubuntu交叉编译dbus库给arm平台使用

1.下载dbus库源码 https://www.freedesktop.org/wiki/Software/dbus 克隆源码: https://gitlab.freedesktop.org/dbus/dbus/-/tree/dbus-1.12?ref_type=heads 下载1.12.20版本: 指定pkgconfig环境变量: export PKG_CONFIG_PATH=$PKG_CONFIG_PATH:$PWD/../expat-2.3.…...

ansible开局配置-openEuler

ansible干啥用的就不多介绍了&#xff0c;这篇文章主要在说ansible的安装、开局配置、免密登录。 ansible安装 查看系统版本 cat /etc/openEuler-latest输出内容如下&#xff1a; openeulerversionopenEuler-24.03-LTS compiletime2024-05-27-21-31-28 gccversion12.3.1-30.…...

连锁收银系统的优势与挑战

在快速发展的零售环境中&#xff0c;连锁收银系统不仅是收银的工具&#xff0c;更是现代零售管理的重要组成部分。它在提升效率、优化客户体验以及数据管理等方面发挥了关键作用。然而&#xff0c;随着技术的进步和市场环境的变化&#xff0c;连锁收银系统也面临着诸多挑战。本…...

轻型民用无人驾驶航空器安全操控理论培训知识总结-多旋翼部分

航空器知识 螺旋桨 螺旋桨为多旋翼民用无人驾驶航空器提供升力,多旋翼民用无人驾驶航空器通过飞控系统控制电机调节螺旋桨转速,来实现飞行。 天线 多旋翼民用无人驾驶航空器的图像传输以及遥控控制信号,主要是通过无线信道进行的,靠民用无人驾驶航空器与遥控器的天线传…...

conda相比python好处

Conda 作为 Python 的环境和包管理工具&#xff0c;相比原生 Python 生态&#xff08;如 pip 虚拟环境&#xff09;有许多独特优势&#xff0c;尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处&#xff1a; 一、一站式环境管理&#xff1a…...

大数据学习栈记——Neo4j的安装与使用

本文介绍图数据库Neofj的安装与使用&#xff0c;操作系统&#xff1a;Ubuntu24.04&#xff0c;Neofj版本&#xff1a;2025.04.0。 Apt安装 Neofj可以进行官网安装&#xff1a;Neo4j Deployment Center - Graph Database & Analytics 我这里安装是添加软件源的方法 最新版…...

2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面

代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口&#xff08;适配服务端返回 Token&#xff09; export const login async (code, avatar) > {const res await http…...

css的定位(position)详解:相对定位 绝对定位 固定定位

在 CSS 中&#xff0c;元素的定位通过 position 属性控制&#xff0c;共有 5 种定位模式&#xff1a;static&#xff08;静态定位&#xff09;、relative&#xff08;相对定位&#xff09;、absolute&#xff08;绝对定位&#xff09;、fixed&#xff08;固定定位&#xff09;和…...

springboot整合VUE之在线教育管理系统简介

可以学习到的技能 学会常用技术栈的使用 独立开发项目 学会前端的开发流程 学会后端的开发流程 学会数据库的设计 学会前后端接口调用方式 学会多模块之间的关联 学会数据的处理 适用人群 在校学生&#xff0c;小白用户&#xff0c;想学习知识的 有点基础&#xff0c;想要通过项…...

C++课设:简易日历程序(支持传统节假日 + 二十四节气 + 个人纪念日管理)

名人说:路漫漫其修远兮,吾将上下而求索。—— 屈原《离骚》 创作者:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊) 专栏介绍:《编程项目实战》 目录 一、为什么要开发一个日历程序?1. 深入理解时间算法2. 练习面向对象设计3. 学习数据结构应用二、核心算法深度解析…...

uniapp 小程序 学习(一)

利用Hbuilder 创建项目 运行到内置浏览器看效果 下载微信小程序 安装到Hbuilder 下载地址 &#xff1a;开发者工具默认安装 设置服务端口号 在Hbuilder中设置微信小程序 配置 找到运行设置&#xff0c;将微信开发者工具放入到Hbuilder中&#xff0c; 打开后出现 如下 bug 解…...

C++实现分布式网络通信框架RPC(2)——rpc发布端

有了上篇文章的项目的基本知识的了解&#xff0c;现在我们就开始构建项目。 目录 一、构建工程目录 二、本地服务发布成RPC服务 2.1理解RPC发布 2.2实现 三、Mprpc框架的基础类设计 3.1框架的初始化类 MprpcApplication 代码实现 3.2读取配置文件类 MprpcConfig 代码实现…...

leetcode73-矩阵置零

leetcode 73 思路 记录 0 元素的位置&#xff1a;遍历整个矩阵&#xff0c;找出所有值为 0 的元素&#xff0c;并将它们的坐标记录在数组zeroPosition中置零操作&#xff1a;遍历记录的所有 0 元素位置&#xff0c;将每个位置对应的行和列的所有元素置为 0 具体步骤 初始化…...

算法刷题-回溯

今天给大家分享的还是一道关于dfs回溯的问题&#xff0c;对于这类问题大家还是要多刷和总结&#xff0c;总体难度还是偏大。 对于回溯问题有几个关键点&#xff1a; 1.首先对于这类回溯可以节点可以随机选择的问题&#xff0c;要做mian函数中循环调用dfs&#xff08;i&#x…...