当前位置: 首页 > 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;连锁收银系统也面临着诸多挑战。本…...

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

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

RestClient

什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端&#xff0c;它允许HTTP与Elasticsearch 集群通信&#xff0c;而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级&#xff…...

HTML 语义化

目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案&#xff1a; 语义化标签&#xff1a; <header>&#xff1a;页头<nav>&#xff1a;导航<main>&#xff1a;主要内容<article>&#x…...

基于FPGA的PID算法学习———实现PID比例控制算法

基于FPGA的PID算法学习 前言一、PID算法分析二、PID仿真分析1. PID代码2.PI代码3.P代码4.顶层5.测试文件6.仿真波形 总结 前言 学习内容&#xff1a;参考网站&#xff1a; PID算法控制 PID即&#xff1a;Proportional&#xff08;比例&#xff09;、Integral&#xff08;积分&…...

【OSG学习笔记】Day 18: 碰撞检测与物理交互

物理引擎&#xff08;Physics Engine&#xff09; 物理引擎 是一种通过计算机模拟物理规律&#xff08;如力学、碰撞、重力、流体动力学等&#xff09;的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互&#xff0c;广泛应用于 游戏开发、动画制作、虚…...

微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】

微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来&#xff0c;Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...

Xshell远程连接Kali(默认 | 私钥)Note版

前言:xshell远程连接&#xff0c;私钥连接和常规默认连接 任务一 开启ssh服务 service ssh status //查看ssh服务状态 service ssh start //开启ssh服务 update-rc.d ssh enable //开启自启动ssh服务 任务二 修改配置文件 vi /etc/ssh/ssh_config //第一…...

蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练

前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1)&#xff1a;从基础到实战的深度解析-CSDN博客&#xff0c;但实际面试中&#xff0c;企业更关注候选人对复杂场景的应对能力&#xff08;如多设备并发扫描、低功耗与高发现率的平衡&#xff09;和前沿技术的…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序

一、开发环境准备 ​​工具安装​​&#xff1a; 下载安装DevEco Studio 4.0&#xff08;支持HarmonyOS 5&#xff09;配置HarmonyOS SDK 5.0确保Node.js版本≥14 ​​项目初始化​​&#xff1a; ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...

高危文件识别的常用算法:原理、应用与企业场景

高危文件识别的常用算法&#xff1a;原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件&#xff0c;如包含恶意代码、敏感数据或欺诈内容的文档&#xff0c;在企业协同办公环境中&#xff08;如Teams、Google Workspace&#xff09;尤为重要。结合大模型技术&…...

【服务器压力测试】本地PC电脑作为服务器运行时出现卡顿和资源紧张(Windows/Linux)

要让本地PC电脑作为服务器运行时出现卡顿和资源紧张的情况&#xff0c;可以通过以下几种方式模拟或触发&#xff1a; 1. 增加CPU负载 运行大量计算密集型任务&#xff0c;例如&#xff1a; 使用多线程循环执行复杂计算&#xff08;如数学运算、加密解密等&#xff09;。运行图…...