数据结构 之 二叉树的遍历------先根遍历(五)
提示:本篇章主要讲解数据结构中树的相关知识。
文章目录
- 二叉树的遍历
- 为什么要提出这么多遍历方法?
- 先根遍历二叉树(TLR)
- 先根遍历二叉树的递归算法(重点)
- 先根遍历二叉树的非递归算法(了解,但是得会写,很有可能找工作的时候让写一个非递归的)
- 先根遍历二叉树的非递归算法
二叉树的遍历
- 遍历二叉树是指以某种次序访问二叉树中的每个结点,并且每个结点仅被访问一次.(沿着某条搜索路线依次访问每个结点)
这里“访问”的含义很广,访问结点所做的操作依赖于具体的应用问题。假设遍历时访问结点仅是输出结点数据域的值,那么遍历的结果将是得到一个线性序列。
由于二叉树有左、右子树,所以遍历的次序不同,得到的结果就会不同。
-

-
假设 L、T、R 分别代表左子树、根结点、右子树
对一棵二叉树的遍历可以有6种不同的次序:TLR、TRL、LTR、RTL、LRT、RLT
如果限定先左后右,那么只有三种访问顺序:TLR、LTR、LRT。分别称作:先根遍历,中根遍历,后根遍历,又称前序遍历,中序遍历,后序遍历
为什么要提出这么多遍历方法?
完全是不同的应用角度出发的。
例如:要判断两个二叉树是否相等,只要子树的根结点不同,那么就不等,显然这是可以用先根遍历实现;
例如:删除二叉树时,必须先删除其左、右子树,然后才能删除根结点,这时就要用后根遍历实现。
可以在具体应用中对遍历方法好好体会,接下来进入正题。
先根遍历二叉树(TLR)
先根遍历二叉树的递归定义为:
若二叉树非空,则:
(1)访问根结点;(2)按先根次序遍历左子树;(3)按先根次序遍历右子树;
否则,遍历结束。
简易口诀:根左右
如下图所示

※先根遍历的顺序为:ABDEGCF

先跟遍历:abdgcefhi
先根遍历二叉树的递归算法(重点)
将访问根结点的操作简化为输出根结点的值
void Preorder ( BTNode * bt )
{ /* 先根遍历以bt为根的二叉树 */ if (bt) {printf(bt->data); /*访问根结点*/ Preorder( bt->lchild ); /*先根遍历左子树*/ Preorder( bt->rchild ); /*先根遍历右子树*/ }}

先根遍历二叉树的非递归算法(了解,但是得会写,很有可能找工作的时候让写一个非递归的)
逻辑过程如下:
对于先根遍历二叉树而言,在访问根结点之后,可以直接找到这个根的左子树进行遍历;但是当左子树遍历完毕之后,还必须沿着已经走过的路线返回到根结点,再通过根结点才能找到它的右子树。
因此,在从根结点走向它的左孩子结点之前,必须根结点的地址存入栈中暂存起来。
左子树遍历完毕之后,再按照后进先出的原则取回栈顶元素,才能找到根结点的地址,最后遍历根的右子树。

先根遍历二叉树的非递归算法
void Preorder2 ( BTNode *bt )
{
p = bt;
InitStack(s);while ( p || !StackEmpty(S) ) { if (p) /*二叉树非空*/ { printf(p->data) ; /*访问根结点*/ Push( s, p ) ; /*根指针进栈*/ p = p->lchild ; /*p移向左孩子*/ } else /*栈非空*/ {Pop ( s , p ) ; /*双亲结点出栈/* p = p->rchild ; /*p移向右孩子*/ }}
}
相关文章:
数据结构 之 二叉树的遍历------先根遍历(五)
提示:本篇章主要讲解数据结构中树的相关知识。 文章目录 二叉树的遍历为什么要提出这么多遍历方法?先根遍历二叉树(TLR)先根遍历二叉树的递归算法(重点)先根遍历二叉树的非递归算法(了解,但是得…...
Xss_less靶场攻略(1-18)
xss-lab-less1 ur特殊字符转义 存在url中 转义符为 %2B& 转义符为 %26空格 转义符为 或 %20/ 转义符为 %2F? 转义符为 %3F% 转义符为 %25#转义符为 %23 转义符为 %3Dimg 标签懒加载 在XSS攻击中,img标签的src属性是一个常见的攻击向量,因为它可以…...
【AI语音克隆整合包及教程】声临其境,让想象成为现实——第二代GPT-SoVITS引领语音克隆新时代!
随着人工智能技术的飞速发展,曾经只能在科幻小说中出现的场景逐渐走进了我们的日常生活。其中,语音克隆技术以其独特魅力,成为了人们关注的焦点。GPT-SoVITS作为一款前沿的语音克隆工具,由RVC变声器创始人“花儿不哭”与AI音色转换…...
echarts属性之dataZoom
dataZoom-slider 滑动条型数据区域缩放组件(dataZoomInside) 滑动条型数据区域缩放组件提供了数据缩略图显示,缩放,刷选,拖拽,点击快速定位等数据筛选的功能。下图显示了该组件可交互部分 所有属性 data…...
SQLite 语法
SQLite 语法 SQLite 是一种轻量级的数据库管理系统,它遵循 SQL(结构化查询语言)标准。SQLite 的语法相对简单,易于学习和使用。本文将详细介绍 SQLite 的基本语法,包括数据定义语言(DDL)、数据…...
逗号运算符应用举例
在main.cpp里输入程序如下: #include <iostream> //使能cin(),cout(); #include <iomanip> //使能setbase(),setfill(),setw(),setprecision(),setiosflags()和resetiosflags(); //setbase( char x )是设置输出数字的基数,如输出进制数则用set…...
Android 玩机知识储备
基础知识 安卓刷机:https://post.smzdm.com/p/724098/安装分区(视频): https://www.bilibili.com/video/BV1BY4y1H7Mc/安卓分区(文章): https://www.cnblogs.com/unixcs/p/16398969.html开机过程:https://…...
MyBatis 学习记录(六)之逆向工程
MyBatis 学习记录(六) MyBatis的逆向工程1、创建逆向工程添加依赖和插件创建逆向工程的配置文件执行MBG插件的generate目标最终生成的效果 2、QBC查询 MyBatis的逆向工程 **正向工程:**先创建Java实体类,由框架负责根据实体类生成…...
深度了解flink(七) JobManager(1) 组件启动流程分析
前言 JobManager是Flink的核心进程,主要负责Flink集群的启动和初始化,包含多个重要的组件(JboMaster,Dispatcher,WebEndpoint等),本篇文章会基于源码分析JobManagr的启动流程,对其各个组件进行介绍&#x…...
PostgreSQL 约束
PostgreSQL 约束 介绍 PostgreSQL 是一种功能强大的开源对象关系数据库系统,它提供了多种约束来确保数据的完整性和一致性。约束是数据库规则,用于限制表中数据的类型和操作。在 PostgreSQL 中,约束可以分为几种类型,包括主键约…...
【Redis】
1、Redis 概述 远程字典服务器(Remote Dictionary Server,Redis):一个开源的、高性能的、轻量级、使用ANSI C语言编写、支持网络、可基于内存亦可持久化的日志型、Key-Value数据库,通过提供多种键值数据类型来试音不同场景下的缓…...
大厂面试真题-MVCC有哪些不好
MVCC(Multi-Version Concurrency Control,多版本并发控制)虽然具有提高数据库并发性能、避免脏读等优势,但也存在一些缺点。以下是对MVCC缺点的详细归纳: 一、存储开销增加 MVCC需要为每个数据行存储多个版本&#x…...
一篇教你多排轮播效果
多排轮播 提示:demo案例 效果看看把 这些都是可以单独左右滑动的 文章目录 多排轮播前言一、上才艺总结 前言 今天想着想着 看着别人这样 哎还挺好看,就自己弄了 提示:以下是本篇文章正文内容,下面案例可供参考 一、上才艺 &…...
安全警告您正在访问危险网站怎么关闭
在上网时,很多人可能遇到过“安全警告:您正在访问危险网站”的提示。这类警告通常由浏览器或安全软件自动弹出,旨在保护用户免受钓鱼网站、恶意软件等潜在安全威胁的侵害。这篇文章将带您了解这种安全警告的来源、关闭提示的步骤以及应采取的…...
群控系统服务端开发模式-应用开发-业务架构逻辑开发第一轮测试
整个系统的第一个层次已经开发完毕,已经有简单的中控,登录、退出、延迟登录时长、黑名单、数据层封装、验证层封装、RSA加解密、Redis等功能,还缺获取个人、角色按钮权限、角色菜单权限功能。角色按钮权限以及角色菜单权限等明后天开发&#…...
git 怎么保留某个文件夹忽略其下面的所有文件?
在 Git 中,如果你想要保留某个文件夹(比如 folder/)但忽略其下面的所有文件,可以使用 .gitignore 文件来实现。需要注意的是,Git 不会自动创建空目录。因此,为了让 Git 记录这个空目录,你需要在…...
Linux Shell 实现一键部署mariadb11.6
mariadb MariaDB数据库管理系统是MySQL的一个分支,主要由开源社区在维护,采用GPL授权许可 MariaDB的目的是完全兼容MySQL,包括API和命令行,使之能轻松成为MySQL的代替品。在存储引擎方面,使用XtraDB来代替MySQL的InnoDB。 MariaDB由MySQL的创始人Michael Widenius主导开发…...
Servlet 3.0 注解开发
文章目录 Servlet3.0注解开发修改idea创建注解的servlet模板内容讲解 关于servlet3.0注解开发的疑问_配置路径省略了属性urlPatterns内容讲解内容小结 Servlet3.0注解开发 【1】问题 说明:之前我们都是使用web.xml进行servlet映射路径的配置。这样配置的弊端&…...
rom定制系列------红米note8_miui14安卓13定制修改固件 带面具root权限 刷写以及界面预览
💝💝💝红米note8机型代码:ginkgo。高通芯片。此固件官方最终版为稳定版12.5.5安卓11的版本。目前很多工作室需要高安卓版本的固件来适应他们的软件。并且需要root权限。根据客户要求。修改固件为完全root。并且修改为可批量刷写的…...
Kaspa钱包ts代码封装
文章目录 1. 配置wasm2. 钱包地址创建3. KAS转账&余额查询4. KRC-20 处理5. 使用demo 1. 配置wasm 下载wasm地址:https://kaspa.aspectron.org/nightly/downloads/ 在项目根目录下添加wasm目录, 将下载的wasm文件中web目录下kaspa和kaspa-dev文件家…...
Linux应用开发之网络套接字编程(实例篇)
服务端与客户端单连接 服务端代码 #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <arpa/inet.h> #include <pthread.h> …...
家政维修平台实战20:权限设计
目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系,主要是分成几个表,用户表我们是记录用户的基础信息,包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题,不同的角色…...
【Go】3、Go语言进阶与依赖管理
前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课,做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程,它的核心机制是 Goroutine 协程、Channel 通道,并基于CSP(Communicating Sequential Processes࿰…...
基于SpringBoot在线拍卖系统的设计和实现
摘 要 随着社会的发展,社会的各行各业都在利用信息化时代的优势。计算机的优势和普及使得各种信息系统的开发成为必需。 在线拍卖系统,主要的模块包括管理员;首页、个人中心、用户管理、商品类型管理、拍卖商品管理、历史竞拍管理、竞拍订单…...
根目录0xa0属性对应的Ntfs!_SCB中的FileObject是什么时候被建立的----NTFS源代码分析--重要
根目录0xa0属性对应的Ntfs!_SCB中的FileObject是什么时候被建立的 第一部分: 0: kd> g Breakpoint 9 hit Ntfs!ReadIndexBuffer: f7173886 55 push ebp 0: kd> kc # 00 Ntfs!ReadIndexBuffer 01 Ntfs!FindFirstIndexEntry 02 Ntfs!NtfsUpda…...
Docker拉取MySQL后数据库连接失败的解决方案
在使用Docker部署MySQL时,拉取并启动容器后,有时可能会遇到数据库连接失败的问题。这种问题可能由多种原因导致,包括配置错误、网络设置问题、权限问题等。本文将分析可能的原因,并提供解决方案。 一、确认MySQL容器的运行状态 …...
【WebSocket】SpringBoot项目中使用WebSocket
1. 导入坐标 如果springboot父工程没有加入websocket的起步依赖,添加它的坐标的时候需要带上版本号。 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-websocket</artifactId> </dep…...
基于单片机的宠物屋智能系统设计与实现(论文+源码)
本设计基于单片机的宠物屋智能系统核心是实现对宠物生活环境及状态的智能管理。系统以单片机为中枢,连接红外测温传感器,可实时精准捕捉宠物体温变化,以便及时发现健康异常;水位检测传感器时刻监测饮用水余量,防止宠物…...
门静脉高压——表现
一、门静脉高压表现 00:01 1. 门静脉构成 00:13 组成结构:由肠系膜上静脉和脾静脉汇合构成,是肝脏血液供应的主要来源。淤血后果:门静脉淤血会同时导致脾静脉和肠系膜上静脉淤血,引发后续系列症状。 2. 脾大和脾功能亢进 00:46 …...
工厂方法模式和抽象工厂方法模式的battle
1.案例直接上手 在这个案例里面,我们会实现这个普通的工厂方法,并且对比这个普通工厂方法和我们直接创建对象的差别在哪里,为什么需要一个工厂: 下面的这个是我们的这个案例里面涉及到的接口和对应的实现类: 两个发…...
