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

二叉树的递归遍历和非递归遍历

目录

一.二叉树的递归遍历

1.先序遍历二叉树

2.中序遍历二叉树

3.后序遍历二叉树

二.非递归遍历(栈)

1.先序遍历

2.中序遍历

3.后序遍历


一.二叉树的递归遍历

定义二叉树

#其中TElemType可以是int或者是char,根据要求自定
typedef struct BiNode{TElemType data;struct BiNode, *lchild,*rchild;}BiNode,*BiTree;void visit(TElemType data) {printf("%d ", data); 
}

1.先序遍历二叉树

void PreOrderTraverse(BiTree T)
{if(T==NULL)return ok;//空二叉树else{visit(T);//访问根节点PreOrderTraverse(T->lchild);//递归遍历左子树PreOrderTraverse(T->rchild);//递归遍历右子树}
}

2.中序遍历二叉树

void InOrderTraverse(BiTree T)
{if(T==NULL)return ok;//空二叉树else{InOrderTraverse(T->lchild);//递归遍历左子树visit(T);//访问根节点InOrderTraverse(T->rchild);//递归遍历右子树}
}

3.后序遍历二叉树

void PostOrderTraverse(BiTree T)
{if(T==NULL)return ok;//空二叉树else{PostOrderTraverse(T->lchild);//递归遍历左子树PostOrderTraverse(T->rchild);//递归遍历右子树visit(T);//访问根节点}
}

遍历的规则,以先序遍历为例:

如果去掉输出语句,从递归角度,三种算法是完全相同的,三种算法访问路径是相同的,只是访问时机不同

第一次经过时访问=先序遍历

第二次经过时访问=中序遍历

第三次经过时访问=后序遍历

二.非递归遍历(栈)

typedef struct BiTNode {char data;struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;typedef struct {BiTree data[MAX_SIZE];int top;
} Stack;void InitStack(Stack** S) {*S = (Stack*)malloc(sizeof(Stack));(*S)->top = -1;
}int StackEmpty(Stack* S) {return (S->top == -1);
}int StackFull(Stack* S) {return (S->top == MAX_SIZE - 1);
}void push(Stack* S, BiTree elem) {if (StackFull(S)) {printf("Stack is full. Cannot push element.\n");return;}S->top++;S->data[S->top] = elem;
}void pop(Stack* S, BiTree* elem) {if (StackEmpty(S)) {printf("Stack is empty. Cannot pop element.\n");return;}*elem = S->data[S->top];S->top--;
}int GetTop(Stack* S, BiTree* elem) {if (StackEmpty(S)) {printf("Stack is empty. Cannot get top element.\n");return 0;}*elem = S->data[S->top];return 1;
}

1.先序遍历

(1)从根结点开始先压左路结点,并访问结点,直到把根结点和左路结点全部压入栈。

(2)若左子树和为空,说明左路和根结点已经全部压栈并且已经访问过了,开始取栈顶元素来访问上一层父节点的右子树。把右子树看成子问题继续进行(1)

(3)依次进行上述(1)和(2)压栈访问和出栈操作,直到栈为空或者右子树为空这说明遍历完毕

void PreOrderTraverse(BiTree T)
{Stack* S;BiTree p, q;InitStack(&S);p = T;while (p || !StackEmpty(S)){if (p){printf("%c", p->data);push(S, p); // 将节点 p 入栈p = p->lchild;}else{pop(S, &q);p = q->rchild;}}free(S); // 释放 Stack 结构体内存
}

2.中序遍历

中序遍历和先序遍历思路类似,区别在于,先序遍历先访问根,在访问左,中序遍历先访问左,在访问根,最后都再访问右

void InOrderTraverse(BiTree T)
{Stack* S;BiTree p, q;InitStack(&S);p = T;while (p || !StackEmpty(S)){if (p){push(S, p);p = p->lchild;}else{pop(S, &q);printf("%c", q->data);p = q->rchild;}}free(S); // 释放 Stack 结构体内存
}

3.后序遍历

后续遍历必须访问完左右子树之后才可以访问父亲结点,所以访问完左子树时,现在得去访问右子树,通过栈找到父亲结点(这是第一次top父亲结点),然后找到父亲结点的右子树进行访问,当把右子树访问完成后,再通过栈找到父亲结点进行访问(这是第二次top父亲结点A)。那么怎么才知道这时是第一次top和第二次top呢?如果不做处理的话这里就会一直认为是第一次top父亲节点,不出栈,就会造成死循环,所以怎样解决呢?

这里创建一个prev结点,用来记录上一次出栈的结点,若上一次出栈的结点为右子树,这说明可以访问根结点了,说明是已经第二次top父亲结点

void PostOrderTraverse(BiTree T)
{Stack* S;BiTree p = T;InitStack(&S);BiTree prev = NULL;while (p || !StackEmpty(S)){while (p){push(S, p);p = p->lchild;}BiTree q;if (GetTop(S, &q) && (q->rchild == NULL || q->rchild == prev)){printf("%c ", q->data);prev = q;//更新q结点pop(S, &p);p = NULL;}else if (q->rchild != NULL){p = q->rchild;}}free(S);
}

相关文章:

二叉树的递归遍历和非递归遍历

目录 一.二叉树的递归遍历 1.先序遍历二叉树 2.中序遍历二叉树 3.后序遍历二叉树 二.非递归遍历(栈) 1.先序遍历 2.中序遍历 3.后序遍历 一.二叉树的递归遍历 定义二叉树 #其中TElemType可以是int或者是char,根据要求自定 typedef struct BiNode{TElemType data;stru…...

JDK17:未来已来,你准备好了吗?

🌷🍁 博主猫头虎(🐅🐾)带您 Go to New World✨🍁 🦄 博客首页——🐅🐾猫头虎的博客🎐 🐳 《面试题大全专栏》 🦕 文章图文…...

K8s和Docker

Kubernetes(简称为K8s)和Docker是两个相关但又不同的技术。 一、Docker 1、Docker是一种容器化平台,用于将应用程序及其依赖项打包成可移植的容器。 2、Docker容器可以在任何支持Docker的操作系统上运行 好处:提供了一种轻量级…...

使用物理机服务器应该注意的事项

使用物理机服务器应该注意的事项 如今云计算的发展已经遍布各大领域,尽管现在的云服务器火遍全网,但是仍有一些大型企业依旧选择使用独立物理服务器,你知道这是为什么吗?壹基比小鑫来告诉你吧。 独立物理服务器托管业务适合大中…...

py脚本解决ArcGIS Server服务内存过大的问题

在一台服务器上,使用ArcGIS Server发布地图服务,但是地图服务较多,在发布之后,服务器的内存持续处在95%上下的高位状态,导致服务器运行状态不稳定,经常需要重新启动。重新启动后重新进入这种内存高位的陷阱…...

Go语言Web开发入门指南

Go语言Web开发入门指南 欢迎来到Go语言的Web开发入门指南。Go语言因其出色的性能和并发支持而成为Web开发的热门选择。在本篇文章中,我们将介绍如何使用Go语言构建简单的Web应用程序,包括路由、模板、数据库连接和静态文件服务。 准备工作 在开始之前…...

保姆级教程——VSCode如何在Mac上配置C++的运行环境

vscode官方下载: 点击官网链接,下载对应的pkg,安装打开; https://code.visualstudio.com/插件安装 点击箭头所指插件商店按钮,yyds; 下载C/C 插件; ![外链图片转存 下载CodeLLDB插件&#x…...

Java 操作FTP服务器进行下载文件

用Java去操作FTP服务器去做下载,本文章里面分为单个下载和批量下载,批量下载只不过多了一层循环,为了方便参考,我代码都贴出来了。 不管单个下载还是多个,一定要记得,远程服务器的直接写文件夹路径&#xf…...

物理机服务器应该注意的事

物理机服务器应该注意的事 1、选址 服务器是个非常重要的硬件产品,对机房的也是有一定的要求的,比如温度、安全性,噪音、电源稳定性等等问题都需要解决!但是不是每个人都会选择自己建立一个机房,毕竟各方面加起来的成本都太高。这…...

信息化发展24

信息技术的发展 1 )在计算机软硬件方面, 计算机硬件技术将向超高速、超小型、平行处理、智能化的方向发展, 计算机硬件设备的体积越来越小、速度越来越高、容量越来越大、功耗越来越低、可靠性越来越高。 2 )计算机软件越来越丰富…...

Qt开发_调用OpenCV(3.4.7)设计完成人脸检测系统

一、前言 近年来,人脸识别技术得到了广泛的应用,它可以在各种场景中实现自动化的人脸检测和识别,例如安防监控、人脸解锁、人脸支付等。 该项目的目标是设计一个简单易用但功能强大的人脸检测系统,可以实时从摄像头采集视频,并对视频中的人脸进行准确的检测和框选。通过…...

Java 中 List 删除元素

fori循环 删除某个元素后,list的大小发生了变化,会导致遍历准确。 这种方式可以用在删除特定的一个元素时使用,但不适合循环删除多个元素时使用 增强for循环 删除元素后继续循环会报错误信息ConcurrentModificationException,但是…...

Redis:StringRedisTemplate简介

(笔记总结自b站黑马程序员课程) 为了在反序列化时知道对象的类型,JSON序列化器会将类的class类型写入json结果中,存入Redis,会带来额外的内存开销。 为了减少内存的消耗,我们可以采用手动序列化的方式&am…...

pytorch-神经网络-手写数字分类任务

Mnist分类任务: 网络基本构建与训练方法,常用函数解析 torch.nn.functional模块 nn.Module模块 读取Mnist数据集 会自动进行下载 %matplotlib inlinefrom pathlib import Path import requestsDATA_PATH Path("data") PATH DATA_PATH / &…...

【群智能算法改进】一种改进的鹈鹕优化算法 IPOA算法[1]【Matlab代码#57】

文章目录 【获取资源请见文章第5节:资源获取】1. 原始POA算法2. 改进后的IPOA算法2.1 Sine映射种群初始化2.2 融合改进的正余弦策略2.3 Levy飞行策略 3. 部分代码展示4. 仿真结果展示5. 资源获取 【获取资源请见文章第5节:资源获取】 1. 原始POA算法 此…...

C++初阶:C++入门

目录 一.iostream文件 二.命名空间 2.1.命名空间的定义 2.2.命名空间的使用 三.C的输入输出 四.缺省参数 4.1.缺省参数概念 4.2.缺省参数分类 4.3.缺省参数注意事项 4.4.缺省参数用途 五.函数重载 5.1.重载函数概念 5.2.C支持函数重载的原理--名字修饰(name Mangl…...

golang操作数据库--gorm框架、redis

目录 1.数据库相关操作(1)非orm框架①引入②初始化③增删改查 (2) io版orm框架 (推荐用这个)①引入②初始化③增删改查④gorm gen的使用 (3) jinzhu版orm框架①引入②初始化③增删改查 2.redis(1)引入(2)初始化①普通初始化②v8初始化③get/set示例 1.数据库相关操作 (1)非orm…...

10 种常用的字符串方法

10 种常用的字符串方法 1.concat() 字符串拼接 const str1 12345678;const str2 abcdefgh;const str3 -【】;‘;console.log(str1.concat(str2,str3))//12345678abcdefgh-【】;‘ 2.includes() 判断字符串中是否包含指定值,返回布尔值…...

CSDN每日一练 |『生命进化书』『订班服』『c++难题-大数加法』2023-09-06

CSDN每日一练 |『生命进化书』『订班服』『c++难题-大数加法』2023-09-06 一、题目名称:生命进化书二、题目名称:订班服三、题目名称:c++难题-大数加法一、题目名称:生命进化书 时间限制:1000ms内存限制:256M 题目描述: 小A有一本生命进化书,以一个树形结构记载了所有生…...

echarts饼图label自定义样式

生成的options {"tooltip": {"trigger": "item","axisPointer": {"type": "shadow"},"backgroundColor": "rgba(9, 24, 48, 0.5)","borderColor": "rgba(255,255,255,0.4)&q…...

【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15

缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下: struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...

Admin.Net中的消息通信SignalR解释

定义集线器接口 IOnlineUserHub public interface IOnlineUserHub {/// 在线用户列表Task OnlineUserList(OnlineUserList context);/// 强制下线Task ForceOffline(object context);/// 发布站内消息Task PublicNotice(SysNotice context);/// 接收消息Task ReceiveMessage(…...

【大模型RAG】Docker 一键部署 Milvus 完整攻略

本文概要 Milvus 2.5 Stand-alone 版可通过 Docker 在几分钟内完成安装;只需暴露 19530(gRPC)与 9091(HTTP/WebUI)两个端口,即可让本地电脑通过 PyMilvus 或浏览器访问远程 Linux 服务器上的 Milvus。下面…...

React19源码系列之 事件插件系统

事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...

Nginx server_name 配置说明

Nginx 是一个高性能的反向代理和负载均衡服务器,其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机(Virtual Host)。 1. 简介 Nginx 使用 server_name 指令来确定…...

微信小程序云开发平台MySQL的连接方式

注:微信小程序云开发平台指的是腾讯云开发 先给结论:微信小程序云开发平台的MySQL,无法通过获取数据库连接信息的方式进行连接,连接只能通过云开发的SDK连接,具体要参考官方文档: 为什么? 因为…...

Element Plus 表单(el-form)中关于正整数输入的校验规则

目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入&#xff08;联动&#xff09;2.1 模板2.2 校验规则2.3 CSS 1 单个正整数输入 1.1 模板 <el-formref"formRef":model"formData":rules"formRules"label-width"150px"…...

Linux离线(zip方式)安装docker

目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1&#xff1a;修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本&#xff1a;CentOS 7 64位 内核版本&#xff1a;3.10.0 相关命令&#xff1a; uname -rcat /etc/os-rele…...

保姆级教程:在无网络无显卡的Windows电脑的vscode本地部署deepseek

文章目录 1 前言2 部署流程2.1 准备工作2.2 Ollama2.2.1 使用有网络的电脑下载Ollama2.2.2 安装Ollama&#xff08;有网络的电脑&#xff09;2.2.3 安装Ollama&#xff08;无网络的电脑&#xff09;2.2.4 安装验证2.2.5 修改大模型安装位置2.2.6 下载Deepseek模型 2.3 将deepse…...

Selenium常用函数介绍

目录 一&#xff0c;元素定位 1.1 cssSeector 1.2 xpath 二&#xff0c;操作测试对象 三&#xff0c;窗口 3.1 案例 3.2 窗口切换 3.3 窗口大小 3.4 屏幕截图 3.5 关闭窗口 四&#xff0c;弹窗 五&#xff0c;等待 六&#xff0c;导航 七&#xff0c;文件上传 …...