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

数据结构 之 二叉树的遍历------先根遍历(五)

提示:本篇章主要讲解数据结构中树的相关知识。

文章目录

    • 二叉树的遍历
    • 为什么要提出这么多遍历方法?
    • 先根遍历二叉树(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里输入程序如下&#xff1a; #include <iostream> //使能cin(),cout(); #include <iomanip> //使能setbase(),setfill(),setw(),setprecision(),setiosflags()和resetiosflags(); //setbase( char x )是设置输出数字的基数,如输出进制数则用set…...

Android 玩机知识储备

基础知识 安卓刷机&#xff1a;https://post.smzdm.com/p/724098/安装分区&#xff08;视频&#xff09;: https://www.bilibili.com/video/BV1BY4y1H7Mc/安卓分区&#xff08;文章&#xff09;: https://www.cnblogs.com/unixcs/p/16398969.html开机过程&#xff1a;https://…...

MyBatis 学习记录(六)之逆向工程

MyBatis 学习记录&#xff08;六&#xff09; MyBatis的逆向工程1、创建逆向工程添加依赖和插件创建逆向工程的配置文件执行MBG插件的generate目标最终生成的效果 2、QBC查询 MyBatis的逆向工程 **正向工程&#xff1a;**先创建Java实体类&#xff0c;由框架负责根据实体类生成…...

深度了解flink(七) JobManager(1) 组件启动流程分析

前言 JobManager是Flink的核心进程&#xff0c;主要负责Flink集群的启动和初始化&#xff0c;包含多个重要的组件(JboMaster&#xff0c;Dispatcher&#xff0c;WebEndpoint等)&#xff0c;本篇文章会基于源码分析JobManagr的启动流程&#xff0c;对其各个组件进行介绍&#x…...

PostgreSQL 约束

PostgreSQL 约束 介绍 PostgreSQL 是一种功能强大的开源对象关系数据库系统&#xff0c;它提供了多种约束来确保数据的完整性和一致性。约束是数据库规则&#xff0c;用于限制表中数据的类型和操作。在 PostgreSQL 中&#xff0c;约束可以分为几种类型&#xff0c;包括主键约…...

【Redis】

1、Redis 概述 远程字典服务器&#xff08;Remote Dictionary Server&#xff0c;Redis)&#xff1a;一个开源的、高性能的、轻量级、使用ANSI C语言编写、支持网络、可基于内存亦可持久化的日志型、Key-Value数据库&#xff0c;通过提供多种键值数据类型来试音不同场景下的缓…...

大厂面试真题-MVCC有哪些不好

MVCC&#xff08;Multi-Version Concurrency Control&#xff0c;多版本并发控制&#xff09;虽然具有提高数据库并发性能、避免脏读等优势&#xff0c;但也存在一些缺点。以下是对MVCC缺点的详细归纳&#xff1a; 一、存储开销增加 MVCC需要为每个数据行存储多个版本&#x…...

一篇教你多排轮播效果

多排轮播 提示&#xff1a;demo案例 效果看看把 这些都是可以单独左右滑动的 文章目录 多排轮播前言一、上才艺总结 前言 今天想着想着 看着别人这样 哎还挺好看&#xff0c;就自己弄了 提示&#xff1a;以下是本篇文章正文内容&#xff0c;下面案例可供参考 一、上才艺 &…...

安全警告您正在访问危险网站怎么关闭

在上网时&#xff0c;很多人可能遇到过“安全警告&#xff1a;您正在访问危险网站”的提示。这类警告通常由浏览器或安全软件自动弹出&#xff0c;旨在保护用户免受钓鱼网站、恶意软件等潜在安全威胁的侵害。这篇文章将带您了解这种安全警告的来源、关闭提示的步骤以及应采取的…...

群控系统服务端开发模式-应用开发-业务架构逻辑开发第一轮测试

整个系统的第一个层次已经开发完毕&#xff0c;已经有简单的中控&#xff0c;登录、退出、延迟登录时长、黑名单、数据层封装、验证层封装、RSA加解密、Redis等功能&#xff0c;还缺获取个人、角色按钮权限、角色菜单权限功能。角色按钮权限以及角色菜单权限等明后天开发&#…...

git 怎么保留某个文件夹忽略其下面的所有文件?

在 Git 中&#xff0c;如果你想要保留某个文件夹&#xff08;比如 folder/&#xff09;但忽略其下面的所有文件&#xff0c;可以使用 .gitignore 文件来实现。需要注意的是&#xff0c;Git 不会自动创建空目录。因此&#xff0c;为了让 Git 记录这个空目录&#xff0c;你需要在…...

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】问题 说明&#xff1a;之前我们都是使用web.xml进行servlet映射路径的配置。这样配置的弊端&…...

rom定制系列------红米note8_miui14安卓13定制修改固件 带面具root权限 刷写以及界面预览

&#x1f49d;&#x1f49d;&#x1f49d;红米note8机型代码&#xff1a;ginkgo。高通芯片。此固件官方最终版为稳定版12.5.5安卓11的版本。目前很多工作室需要高安卓版本的固件来适应他们的软件。并且需要root权限。根据客户要求。修改固件为完全root。并且修改为可批量刷写的…...

Kaspa钱包ts代码封装

文章目录 1. 配置wasm2. 钱包地址创建3. KAS转账&余额查询4. KRC-20 处理5. 使用demo 1. 配置wasm 下载wasm地址&#xff1a;https://kaspa.aspectron.org/nightly/downloads/ 在项目根目录下添加wasm目录&#xff0c; 将下载的wasm文件中web目录下kaspa和kaspa-dev文件家…...

中南大学无人机智能体的全面评估!BEDI:用于评估无人机上具身智能体的综合性基准测试

作者&#xff1a;Mingning Guo, Mengwei Wu, Jiarun He, Shaoxian Li, Haifeng Li, Chao Tao单位&#xff1a;中南大学地球科学与信息物理学院论文标题&#xff1a;BEDI: A Comprehensive Benchmark for Evaluating Embodied Agents on UAVs论文链接&#xff1a;https://arxiv.…...

循环冗余码校验CRC码 算法步骤+详细实例计算

通信过程&#xff1a;&#xff08;白话解释&#xff09; 我们将原始待发送的消息称为 M M M&#xff0c;依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)&#xff08;意思就是 G &#xff08; x ) G&#xff08;x) G&#xff08;x) 是已知的&#xff09;&#xff0…...

江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命

在华东塑料包装行业面临限塑令深度调整的背景下&#xff0c;江苏艾立泰以一场跨国资源接力的创新实践&#xff0c;重新定义了绿色供应链的边界。 跨国回收网络&#xff1a;废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点&#xff0c;将海外废弃包装箱通过标准…...

苍穹外卖--缓存菜品

1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得&#xff0c;如果用户端访问量比较大&#xff0c;数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据&#xff0c;减少数据库查询操作。 缓存逻辑分析&#xff1a; ①每个分类下的菜品保持一份缓存数据…...

微服务商城-商品微服务

数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...

学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2

每日一言 今天的每一份坚持&#xff0c;都是在为未来积攒底气。 案例&#xff1a;OLED显示一个A 这边观察到一个点&#xff0c;怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 &#xff1a; 如果代码里信号切换太快&#xff08;比如 SDA 刚变&#xff0c;SCL 立刻变&#…...

08. C#入门系列【类的基本概念】:开启编程世界的奇妙冒险

C#入门系列【类的基本概念】&#xff1a;开启编程世界的奇妙冒险 嘿&#xff0c;各位编程小白探险家&#xff01;欢迎来到 C# 的奇幻大陆&#xff01;今天咱们要深入探索这片大陆上至关重要的 “建筑”—— 类&#xff01;别害怕&#xff0c;跟着我&#xff0c;保准让你轻松搞…...

接口自动化测试:HttpRunner基础

相关文档 HttpRunner V3.x中文文档 HttpRunner 用户指南 使用HttpRunner 3.x实现接口自动化测试 HttpRunner介绍 HttpRunner 是一个开源的 API 测试工具&#xff0c;支持 HTTP(S)/HTTP2/WebSocket/RPC 等网络协议&#xff0c;涵盖接口测试、性能测试、数字体验监测等测试类型…...

ubuntu系统文件误删(/lib/x86_64-linux-gnu/libc.so.6)修复方案 [成功解决]

报错信息&#xff1a;libc.so.6: cannot open shared object file: No such file or directory&#xff1a; #ls, ln, sudo...命令都不能用 error while loading shared libraries: libc.so.6: cannot open shared object file: No such file or directory重启后报错信息&…...

Vue 3 + WebSocket 实战:公司通知实时推送功能详解

&#x1f4e2; Vue 3 WebSocket 实战&#xff1a;公司通知实时推送功能详解 &#x1f4cc; 收藏 点赞 关注&#xff0c;项目中要用到推送功能时就不怕找不到了&#xff01; 实时通知是企业系统中常见的功能&#xff0c;比如&#xff1a;管理员发布通知后&#xff0c;所有用户…...