【数据结构】遍历二叉树(递归和非递归遍历的先序、中序和后序遍历、层次遍历法)

目录

  • 【数据结构】遍历二叉树(递归和非递归遍历的先序、中序和后序遍历、层次遍历法)
    • 一、递归算法
      • 先(根)序的遍历算法
      • 中(根)序的遍历算法
      • 后(根)序的遍历算法
    • 二、非递归算法
      • 层次遍历
      • 先序遍历非递归算法
      • 中序遍历非递归算法
      • 后序遍历非递归算法

【数据结构】遍历二叉树(递归和非递归遍历的先序、中序和后序遍历、层次遍历法)

采用二叉链表的形式储存
结点结构 [lchild,data,rchild]

特点:二叉链表找子孙结点容易,找祖先结点麻烦。

typedef struct BiTNode {                
    char data;  
    struct BiTNode *lchild, *rchild; //左右子树根结点地址
} BiTNode, *BiTree;

一、递归算法

递归算法书写简单,但是效率低。

先(根)序的遍历算法

先序遍历(递归定义 递归结束的条件就是:空树 )

  1. 若二叉树为空树,则空操作;
  2. 否则,(1)访问根结点;(2)先序遍历左子树;(3)先序遍历右子树。

先序遍历的递归算法:

//先序遍历 递归访问每一个结点
void xxbl(BiTree T){
    if(T){//递归调用的结束条件
        printf("%c",T->data);//访问结点
        xxbl(T->lchild);//遍历左子树
        xxbl(T->rchild);//遍历右子树
    }
}

中(根)序的遍历算法

  1. 若二叉树为空树,则空操作;
  2. 否则,(1)中序遍历左子树;(2)访问根结点;(3)中序遍历右子树。

中序遍历的递归算法:

void zxbl(BiTree T)
{
    if (T) {
        zxbl(T->lchild); 
        printf("%c",T->data); 
        zxbl(T->rchild);
    }
}

后(根)序的遍历算法

  1. 若二叉树为空树,则空操作;
  2. 否则,(1)后序遍历左子树;(2)后序遍历右子树;(3)访问根结点。
void hxbl(BiTree T)
{
    if(T){
        hxbl(T->lchild); 
        hxbl(T->rchild); 
        printf("%c",T->data);
    }
}

二、非递归算法

  1. 用循环队列实现二叉树的按层次遍历
  2. 使用 来实现 先保存 后 访问

层次遍历

从根节点开始,先访问第一层的结点,在访问第二层的结点。
特点:自顶向下,从左到右的访问次序。
借用 队列(循环队列) 来实现层次遍历的功能,所有要访问的结点都存放在队列中。

  1. 初始时若二叉树非空,则只需要知道要访问的第一个结点为根结点。
  2. 只要队列不空,说明队列中存有要访问的结点,则取队首结点访问,并将其非空左右孩子依次插入队列中。
    在这里插入图片描述
    算法代码示例:
//层次遍历算法
#define MAX 100
void LevelTrave(BiTree T){
	BiTree Q[MAX],p;
	//用循环队列实现二叉树的按层次遍历
	int f=r=0;//队列 队首和队尾指针
	if(T==NULL)	return;
	Q(r++)=T;// 根节点入队
	while(f!=r){
		p=Q[f++];//出队
		printf("%c",p->data);
		if(p->lchild){
			if(r>=MAX){
				printf("overflow");
				exit(0);
			}
			Q[r++]=p->lchild;
		}
		if(p->rchild){
			if(r>=MAX){
				printf("overflow");
				exit(0);
			}
			Q[r++]=p->rchild;
		}
	}
}

先序遍历非递归算法

先序遍历非递归算法的实现:访问根节点后,在访问左子树之前,先将其非空右子树的地址入栈(保存)。
在这里插入图片描述
采用顺序栈来存放访问过的结点右子树:

#define MAX 10000
typedef struct{
	BiTree data[MAX];
	int top;
}SeqStack;
void PreorderTraverse(BiTree T){//T为二叉树的根结点
    SeqStack s;//新建一个 栈
    BiTree p;
    s.top=-1; //栈顶指针
    p = T;//
    while(p){
    
        while(p){//访问左子树
        
            printf("%c",p->data); //访问p结点
            if(p->rchild) {//将p结点的非空右孩子入栈保存
                if(s.top==MAX-1) 
                	exit (0);//栈溢出
                else 
                	s.data[++s.top]=p->rchild;//入栈
            }
            
            p =p->lchild; //访问p的左孩子  
        }
        
            if (s.top!=-1) 
            	p=s.data[s.top--];//出栈
    }
}

中序遍历非递归算法

  1. 基本思想:访问根结点的左子树前,应保存其根结点,以便左子树访问结束后,访问根和根的右子树
  2. 图中a结点先于b结点被保存,但是其访问要在b及b的右子树被访问后进行----先保存后访问----先进后出----借助栈来实现

在这里插入图片描述

void InorderTraverse(BiTree T){//中序遍历根结点为T的二叉树
    SeqStack s; 
    BiTree p;
    s.top=-1; 
    p = T;
    while(p||(s.top!=-1)){ //
        while(p){
            if(s.top==MAX-1) 
                exit (0);
            s.data[++s.top]=p; 
            p =p->lchild;// 一直去访问左子树 同时将结点入栈
            //向左下走一直走到头
            }
            
        if (s.top!=-1){
            p=s.data[s.top--];//根节点出栈
            printf("%c",p->data);
            p = p->rchild; //访问该根节点的右子树
            
        }
    }
}

后序遍历非递归算法

  1. 后序遍历非递归算法的实现:访问根结点的子树前,应保存其根结点,以便左子树访问结束后,访问根的右子树和根
  2. 图中a结点先于b结点被保存,但是其访问要在b及其右子树被访问后进行----先保存后访问----先进后出----借助栈实现

只有在其左、右子树被访问后才能被访问(需要标记 定义一个flag标记其左右子树是否都被访问过)
在这里插入图片描述

#define	MAX5
typedef struct{
	BiTree q;
	int flag;
}dataelem;
//q存放的是遍历操作访问到的一棵子树的根节点
//flag=0代表目前是在访问q结点的左子树,flag=1代表目前是在访问q结点的右子树
typedef struct{
dataelem data[MAX];
int top;//栈顶指针
}SeqStack2;

代码示例(!!!):

void postorder(BiTree T){
    SeqStack2 s;
    s.top=-1;
    p=T;
    do{
        while(p!=NULL){
        	if(s.top==MAX-1) 
            	exit (0);//栈溢出
            s.data[++s.top].q=p; 
            s.data[s.top].flag=0; 
            
            p=p->lchild;//一直向左下访问 
        }
        
        while((s.top>-1)&&(s.data[s.top].flag==1)){ 
        //
            p=s.data[s.top--].q; 
            printf(%c”,p->data); 
        }
        
        if(s.top>-1){
            s.data[s.top].flag=1;//标记 此时开始访问 其右子树
            p=s.data[s.top].q; 
            p=p->rchild;
        }
        
    }while(s.top>-1);
}

感谢阅读!!!

  1. 树与二叉树知识点文章: 【数据结构】树与二叉树(递归法先序、中序、后序、层次遍历二叉树、二叉树的建立以及求树高的方法)
  2. 二叉树遍历算法的应用: 【数据结构】树与二叉树遍历算法的应用(求叶子节点个数、求树高、复制二叉树、创建二叉树、二叉树存放表达式、交换二叉树每个结点的左右孩子)
  3. 二叉树遍历算法的应用: 【数据结构】树与森林(树的存储结构、森林与二叉树的转化、树与森林的遍历)

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

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

相关文章

LabVIEW电信号傅里叶分解合成实验

LabVIEW电信号傅里叶分解合成实验 电信号的分析与处理在科研和工业领域中起着越来越重要的作用。系统以LabVIEW软件为基础,开发了一个集电信号的傅里叶分解、合成、频率响应及频谱分析功能于一体的虚拟仿真实验系统。系统不仅能够模拟实际电路实验箱的全部功能&…

查找树莓派ip地址的几种方法

1.环境说明 从上面的图中可以看到树莓派是通过网线和win10电脑相连的,以此来共享win10电脑网络,但是需要在电脑端设置后才能将网络共享出来, 设置方法参考以下链接: 通过一根网线共享网络给另一个电脑或者群辉上网 注意&#xff0…

GitHub repository - Watch - Star - Fork - Follow

GitHub repository - Watch - Star - Fork - Follow References 眼睛图标旁边写着 Watch 字样。点击这个按钮就可以 Watch 该仓库,今后该仓库的更新信息会显示在用户的公开活动中。Star 旁边的数字表示给这个仓库添加 Star 的人数。这个数越高,代表该仓库…

今日arXiv最热大模型论文:清华大学发布,ChatGML又添新功能,集成“自我批评”,提升数学能力

引言:数学问题解决在大语言模型中的挑战 在当今的人工智能领域,大语言模型(Large Language Models,LLMs)已经在理解和生成人类语言方面取得了显著的进展。这些模型在文本摘要、问答、角色扮演对话等多种语言任务上展现…

组合模式:构建树形对象结构的设计艺术

在软件开发中,组合模式是一种结构型设计模式,用于表示对象的部分-整体层次结构。通过使单个对象和组合对象具有相同的接口,这种模式允许客户端以统一的方式处理单个对象和组合对象。本文将详细介绍组合模式的定义、实现、应用场景以及优缺点。…

一些知识点小细节

当遇到的问题有关逆序输出,可以转换一下思想,就是使用for循环的时候,i的初始化是从数组或者是字符串的最后一个,然后注意设置循环结束的条件,最重要的是不要忘记i--;而不是I; 注意:当要逆序输出…

弱口令入侵FE企业管理平台【附口令】

漏洞描述 飞企互联-FE企业运营管理平台 druid路径弱口令,攻击者可能通过尝试弱口令,非法进入系统,恶意操作或者收集信息进一步攻击利用。 漏洞复现 1、Fofa app"飞企互联-FE企业运营管理平台"2、零零信安 (html_banner360浏览…

android studio 网络请求okhttp3、okgo

一、在build.gradle文件里添加 implementation com.squareup.okhttp3:okhttp:4.9.0 implementation com.squareup.okhttp3:okhttp:3.12.0 implementation com.squareup.okio:okio:1.17.4 implementation com.lzy.net:okgo:3.0.4 implementation com.alibaba:fastjson:1.2.57 i…

蓝桥杯【第15届省赛】Python B组

这题目难度对比历届是相当炸裂的简单了…… A:穿越时空之门 【问题描述】 随着 2024 年的钟声回荡,传说中的时空之门再次敞开。这扇门是一条神秘的通道,它连接着二进制和四进制两个不同的数码领域,等待着勇者们的探索。 在二进制…

# Nacos 服务发现-快速入门-创建服务消费者模块,使用 feign 调用 服务生产者

Nacos 服务发现-快速入门-创建服务消费者模块,使用 feign 调用 服务生产者 1、 新增 quickstart_consumer 子工程(子模块), 创建子模块:--> 右键 nacos_discovery 父工程 --> Modules --> Maven --> G…

小剧场短剧剧集收费短剧小程序APP

1. 内容展现 付费、免费、任务解锁:用户可以通过付费直接观看短剧,也可以通过完成平台任务(如签到、分享等)获得免费观看的机会。这种灵活的解锁方式既满足了用户的多种需求,也促进了平台的活跃度。主流展现形式&…

MyBatis核心配置文件介绍使用

文章目录 一、environments二、properties三、typeAliases四、mappers五、创建核心配置文件模板&映射文件模板核心配置文件模板映射文件模板 六、总结 一、environments 核心配置文件中的标签必须按照固定的顺序: properties?,settings?,typeAliases?,typeH…

vue 百度地图 使用 vue-baidu-map 进行当前位置定位和范围展示

vue 百度地图 使用 vue-baidu-map 进行当前位置定位和范围展示(考勤打卡) 一、创建百度地图账号,获取秘钥二、 引入插件1、安装vue-baidu-map2、在main.js中引入 三、 简单使用 最近写项目的时候,做到了考勤打卡的模块内容&#x…

c++ 中文转拼音的封装, char 类型 不支持 中文 已解决

在日常业务中&#xff0c;需要进行中文转拼音的检索。已便实现对应的 模糊搜索。 使用方法 std::string res "我是中国人";char* result new char[res.length() 1];for (int i 0; i < res.length(); i){result[i] res[i];}result[res.length()] \0;std::str…

【C++类和对象】上篇

&#x1f49e;&#x1f49e; 前言 hello hello~ &#xff0c;这里是大耳朵土土垚~&#x1f496;&#x1f496; &#xff0c;欢迎大家点赞&#x1f973;&#x1f973;关注&#x1f4a5;&#x1f4a5;收藏&#x1f339;&#x1f339;&#x1f339; &#x1f4a5;个人主页&#x…

Xilinx Zynq UltraScale+ MPSoC无人机控制器

官方术语是无人驾驶飞行器&#xff08;UAV&#xff09;&#xff0c;这显然有点拗口&#xff0c;所以我们更喜欢说无人机。在过去的几十年里&#xff0c;无人机技术有了巨大的进步。我们为一个客户开发了一个无人机的飞行和视频控制器。 客户挑战 客户需要一种混合FPGA/CPU硬件&…

idea keymap用eclipse的相关快捷键

idea快捷键用eclipse的方式 CtrlShiftR 搜索文件 shiftshift 全部文件/类搜索 CtrlH 全局搜索 CtrlO 快速打开Outline大纲视图 ctrle 查看recent窗口文件 ctrlt 快速进入接口的实现类 ctrlshiftf 格式化代码 altshiftr 变量或函数的重命名 ctrlshifto 移除无用的头文…

MySQL基础知识——MySQL日志

一条查询语句的执行过程一般是经过连接器、 分析器、 优化器、 执行器等功能模块&#xff0c; 最后到达存储引擎。 那么&#xff0c; 一条更新语句的执行流程又是怎样的呢&#xff1f; 下面我们从一个表的一条更新语句进行具体介绍&#xff1a; 假设这个表有一个主键ID和一个…

MySQL:MySQL的查询(上)

文章目录 MySQL的增加单行数据插入多行数据插入插入否则更新替换 MySQL的查询select列where语句 本篇开始总结的是MySQL当中的基本查询语句 对于数据库的查询&#xff0c;无非大致就是增删查改&#xff0c;因此对于这些内容进行一一解释&#xff1a; MySQL的增加 单行数据插…

Redis中的集群(九)

集群 消息 集群中的各个节点通过发送和接收消息(message)来进行通信&#xff0c;我们称发送消息的节点为发送者(sender),接收消息 的节点成为接收者&#xff0c;如图所示。节点发送的消息主要有以下五种: 1.MEET消息:当发送者接到客户端发送的CLUSTER MEET命令时&#xff0c…