【数据结构二叉树】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; //将新结点数据域置为e
	p->next = S; //将新结点插入栈顶
	S = p; //修改栈顶指针为p
	return OK;
}

Status Pop(LinkStack &S, BiTNode &e) {  //出栈
	LinkStack p;
	if (S == NULL)
		return ERROR; //栈空
	e = S->data; //将栈顶元素赋给e
	p = 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; //根结点的数据域置为ch
        CreateBiTree_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; //将新结点数据域置为e
	p->next = S; //将新结点插入栈顶
	S = p; //修改栈顶指针为p
	return OK;
}

Status Pop(LinkStack &S, BiTNode &e) {  //出栈
	LinkStack p;
	if (S == NULL)
		return ERROR; //栈空
	e = S->data; //将栈顶元素赋给e
	p = 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; //根结点的数据域置为ch
        CreateBiTree_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; //将新结点数据域置为e
	p->next = S; //将新结点插入栈顶
	S = p; //修改栈顶指针为p
	return OK;
}

Status Pop(LinkStack &S, BiTNode &e) {  //出栈
	LinkStack p;
	if (S == NULL)
		return ERROR; //栈空
	e = S->data; //将栈顶元素赋给e
	p = 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; //根结点的数据域置为ch
        CreateBiTree_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;
}

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

4.结语

对于先序、中序和后序遍历，如果采用非递归算法，则需要借助栈来实现。对于二叉树而言，还有一种大家更为熟知的遍历方式，那就是层次遍历。实现对二叉树的层次遍历，则需要借助队列来实现。实现对二叉树的层次遍历，可以参考C实现二叉树的层次遍历
欢迎大家一起来交流~

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/908344.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

【LeetCode】移除链表中等于设定值的元素、反转链表

【LeetCode】移除链表中等于设定值的元素、反转链表

主页&#xff1a;HABUO&#x1f341;主页&#xff1a;HABUO &#x1f31c;有时候世界虽然是假的&#xff0c;但并不缺少真心对待我们的人&#x1f31b; 1. 移除链表中设定值的元素 题目&#xff1a;给你一个链表的头节点 head 和一个整数 val &#xff0c;请你删除链表中所…
阅读更多...
程序员日志之DNF手游1023版本活动补充

程序员日志之DNF手游1023版本活动补充

目录 传送门正文日志1、概要2、正文 传送门 SpringMVC的源码解析&#xff08;精品&#xff09; Spring6的源码解析&#xff08;精品&#xff09; SpringBoot3框架&#xff08;精品&#xff09; MyBatis框架&#xff08;精品&#xff09; MyBatis-Plus SpringDataJPA SpringClo…
阅读更多...
macOS开发环境配置与应用开发教程

macOS开发环境配置与应用开发教程

macOS开发环境配置与应用开发教程 引言 macOS是一个强大的操作系统&#xff0c;广泛应用于软件开发&#xff0c;尤其是iOS和macOS应用开发。本文将详细介绍如何配置macOS开发环境&#xff0c;并通过实例演示如何进行应用开发。希望通过这篇文章&#xff0c;帮助读者快速上手m…
阅读更多...
提高交换网络可靠性之认识STP根桥与端口角色

提高交换网络可靠性之认识STP根桥与端口角色

转载请注明出处 该实验旨在学习如何选举根桥与识别端口角色。 1.三台交换机按要求连线&#xff0c;改名&#xff0c;分别为S1&#xff0c;S2&#xff0c;S3&#xff0c;以S1为例&#xff1a; 2.在S1上配置优先级为28672 同理&#xff0c;在交换机S2和S3上配置其优先级为32768&…
阅读更多...
基于大数据的热门旅游景点数据分析系统的设计与实现

基于大数据的热门旅游景点数据分析系统的设计与实现

作者主页&#xff1a;编程千纸鹤 作者简介&#xff1a;Java领域优质创作者、CSDN博客专家 、CSDN内容合伙人、掘金特邀作者、阿里云博客专家、51CTO特邀作者、多年架构师设计经验、多年校企合作经验&#xff0c;被多个学校常年聘为校外企业导师&#xff0c;指导学生毕业设计并参…
阅读更多...
【大语言模型】ACL2024论文-03 MAGE: 现实环境下机器生成文本检测

【大语言模型】ACL2024论文-03 MAGE: 现实环境下机器生成文本检测

【大语言模型】ACL2024论文-03 MAGE: 现实环境下机器生成文本检测 目录 文章目录 【大语言模型】ACL2024论文-03 MAGE: 现实环境下机器生成文本检测目录摘要研究背景问题与挑战如何解决核心创新点算法模型实验效果&#xff08;包含重要数据与结论&#xff09;主要参考工作后续优…
阅读更多...
A012-基于Spring Boot的私房菜定制上门服务系统的设计与实现

A012-基于Spring Boot的私房菜定制上门服务系统的设计与实现

摘 要 如今社会上各行各业&#xff0c;都喜欢用自己行业的专属软件工作&#xff0c;互联网发展到这个时候&#xff0c;人们已经发现离不开了互联网。新技术的产生&#xff0c;往往能解决一些老技术的弊端问题。因为传统私房菜定制上门服务系统信息管理难度大&#xff0c;容错率…
阅读更多...
ios 快捷指令扩展（Intents Extension）简单使用 swift语言

ios 快捷指令扩展（Intents Extension）简单使用 swift语言

本文介绍使用Xcode15 建立快捷指令的Extension&#xff0c;并描述如何修改快捷指令的IntentHandler&#xff0c;带参数跳转主应用&#xff1b;以及展示多个选项的快捷指令弹框(配置intentdefinition文件)&#xff0c;点击选项带参数跳到主应用的方法 创建快捷指令 快捷指令是…
阅读更多...
【MacOS实操】如何基于SSH连接远程linux服务器

【MacOS实操】如何基于SSH连接远程linux服务器

MacOS上远程连接linux服务器&#xff0c;可以使用ssh命令pem秘钥文件连接。 一、准备pem秘钥文件 如果已经有pem文件&#xff0c;则跳过这一步。如果手上有ppk文件&#xff0c;那么需要先转换为pem文件。 macOS 的默认 SSH 客户端不支持 PPK 格式&#xff0c;你需要将 PPK 文…
阅读更多...
Puppeteer点击系统：解锁百度流量点击率提升的解决案例

Puppeteer点击系统：解锁百度流量点击率提升的解决案例

在数字营销领域&#xff0c;流量和搜索引擎优化&#xff08;SEO&#xff09;是提升网站可见性的关键。我开发了一个基于Puppeteer的点击系统&#xff0c;旨在自动化地提升百度流量点击率。本文将介绍这个系统如何通过模拟真实用户行为&#xff0c;优化关键词排名&#xff0c;并…
阅读更多...
Golang | Leetcode Golang题解之第524题通过删除字母匹配到字典里最长单词

Golang | Leetcode Golang题解之第524题通过删除字母匹配到字典里最长单词

题目&#xff1a; 题解&#xff1a; func findLongestWord(s string, dictionary []string) (ans string) {m : len(s)f : make([][26]int, m1)for i : range f[m] {f[m][i] m}for i : m - 1; i > 0; i-- {f[i] f[i1]f[i][s[i]-a] i}outer:for _, t : range dictionary …
阅读更多...
019集——获取CAD图中多个实体的包围盒（CAD—C#二次开发入门）

019集——获取CAD图中多个实体的包围盒（CAD—C#二次开发入门）

如下图所示&#xff0c;获取多个实体的最大包围盒&#xff0c;用红色线表示&#xff1a; 也可单独选圆的包围盒 部分代码如下&#xff1a; using Autodesk.AutoCAD.ApplicationServices; using Autodesk.AutoCAD.DatabaseServices; using Autodesk.AutoCAD.Geometry; using A…
阅读更多...
【快速上手】pyspark 集群环境下的搭建（Yarn模式）

【快速上手】pyspark 集群环境下的搭建（Yarn模式）

目录 前言&#xff1a; 一、安装步骤 安装前准备 1.第一步&#xff1a;安装python 2.第二步&#xff1a;在bigdata01上安装spark 3.第三步&#xff1a;同步bigdata01中的spark到bigdata02和03上 二、启动 三、可打开yarn界面查看任务 前言&#xff1a; 上一篇介绍的是…
阅读更多...
sublime python出现中文乱码怎么办

sublime python出现中文乱码怎么办

一、乱码现象 利用sublime自带编译快捷方式ctrlB会出现中文乱码的情况。 print("没有循环数据!") print("完成循环!") 二、寻找原因 1、由于之前我已经安装了插件ConvertToUTF8&#xff0c;排除文本编码错误问题。 2、相同的代码在插件sublimerepl搭建的…
阅读更多...
第三届北京国际水利科技博览会将于25年3月在国家会议中心召开

第三届北京国际水利科技博览会将于25年3月在国家会议中心召开

由中国农业节水和农村供水技术协会、北京水利学会、振威国际会展集团等单位联合主办的第三届北京国际水利科技博览会暨供水技术与设备展&#xff08;北京水利展&#xff09;将于2025年3月31日至4月2日在北京•国家会议中心举办&#xff01; 博览会以“新制造、新服务、新业态”…
阅读更多...
RHCE DNS

RHCE DNS

DNS DNS1.1 DNS介绍1.2 安装bind&#xff0c;配置文件1.3 正向解析文件模板1.4 反向解析文件模板1.5 转发服务器实验1.6 解析web服务器实验1.7 区域传送克隆虚拟机 DNS 1.1 DNS介绍 DNS系统 域名系统&#xff08;DNS&#xff09;是一个分层的分布式数据库。它存储用于将Inter…
阅读更多...
JSON交互处理

JSON交互处理

目录 一、什么是JSON 二、JSON和JavaScript对象互转 ​三、Controller返回JSON数据 3.1 使用Jackson 编写Controller 1. 一个对象 2. 多个对象 3. 输出时间对象 4. 优化&#xff1a;抽取为工具类 一、什么是JSON Json是JavaScript对象的字符串表示法&#xff0c;它用…
阅读更多...
GeoSever发布图层（保姆姬）

GeoSever发布图层（保姆姬）

发布服务的具体步骤。 1. 安装 GeoServer 下载 GeoServer 安装包&#xff1a;GeoServer 官网按照安装说明进行安装&#xff0c;可以选择 Windows、Linux 或其他平台。 2. 启动 GeoServer 启动 GeoServer 通常通过访问 http://localhost:8080/geoserver 进行。默认用户名和密…
阅读更多...
Linux中断、软中断、MMU内存映射-深入理解

Linux中断、软中断、MMU内存映射-深入理解

中断&#xff1a; Linux中&#xff0c;中断上半部不能嵌套&#xff0c;如果一直保存上下文&#xff0c;栈可能会溢出。中断上半部处理紧急事情&#xff0c;下半部处理非紧急事情。下半部通常通过软中断来实现。在上半部执行完后会执行下半部的软中断&#xff0c;如果囤积了A和…
阅读更多...
讲讲 kafka 维护消费状态跟踪的方法？

讲讲 kafka 维护消费状态跟踪的方法？

大家好&#xff0c;我是锋哥。今天分享关于【讲讲 kafka 维护消费状态跟踪的方法&#xff1f;】面试题&#xff1f;希望对大家有帮助&#xff1b; 讲讲 kafka 维护消费状态跟踪的方法&#xff1f; 1000道 互联网大厂Java工程师 精选面试题-Java资源分享网 在 Kafka 中&#x…
阅读更多...
最新文章

Copyright @ 2022~2023