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

【数据结构】树与二叉树(廿二):树和森林的遍历——后根遍历(递归算法PostOrder、非递归算法NPO)

文章目录

  • 5.1 树的基本概念
    • 5.1.1 树的定义
    • 5.1.2 森林的定义
    • 5.1.3 树的术语
  • 5.2 二叉树
  • 5.3 树
    • 5.3.1 树的存储结构
      • 1. 理论基础
      • 2. 典型实例
      • 3. Father链接结构
      • 4. 儿子链表链接结构
      • 5. 左儿子右兄弟链接结构
    • 5.3.2 获取结点的算法
    • 5.3.3 树和森林的遍历
      • 1. 先根遍历(递归、非递归)
      • 2. 后根遍历(递归)
        • a.理论
        • b. ADL算法PostOrder
        • c. 代码实现
      • 3. 后根遍历(非递归)
        • a. ADL算法NPO
        • b. NPO算法解析
        • c. 代码实现
      • 3. 森林的遍历
      • 4. 代码整合

5.1 树的基本概念

5.1.1 树的定义

  • 一棵树是结点的有限集合T:
    • 若T非空,则:
      • 有一个特别标出的结点,称作该树的,记为root(T);
      • 其余结点分成若干个不相交的非空集合T1, T2, …, Tm (m>0),其中T1, T2, …, Tm又都是树,称作root(T)的子树
    • T 空时为空树,记作root(T)=NULL。

5.1.2 森林的定义

  一个森林是0棵或多棵不相交(非空)树的集合,通常是一个有序的集合。换句话说,森林由多个树组成,这些树之间没有交集,且可以按照一定的次序排列。在森林中,每棵树都是独立的,具有根节点和子树,树与树之间没有直接的连接关系。
  森林是树的扩展概念,它是由多个树组成的集合。在计算机科学中,森林也被广泛应用于数据结构和算法设计中,特别是在图论和网络分析等领域。
在这里插入图片描述

5.1.3 树的术语

  • 父亲(parent)、儿子(child)、兄弟(sibling)、后裔(descendant)、祖先(ancestor)
  • 度(degree)、叶子节点(leaf node)、分支节点(internal node)
  • 结点的层数
  • 路径、路径长度、结点的深度、树的深度

参照前文:【数据结构】树与二叉树(一):树(森林)的基本概念:父亲、儿子、兄弟、后裔、祖先、度、叶子结点、分支结点、结点的层数、路径、路径长度、结点的深度、树的深度

5.2 二叉树

5.3 树

5.3.1 树的存储结构

1. 理论基础

2. 典型实例

3. Father链接结构

4. 儿子链表链接结构

【数据结构】树与二叉树(十八):树的存储结构——Father链接结构、儿子链表链接结构

5. 左儿子右兄弟链接结构

【数据结构】树与二叉树(十九):树的存储结构——左儿子右兄弟链接结构(树、森林与二叉树的转化)
  左儿子右兄弟链接结构通过使用每个节点的三个域(FirstChild、Data、NextBrother)来构建一棵树,同时使得树具有二叉树的性质。具体来说,每个节点包含以下信息:

  1. FirstChild: 存放指向该节点的大儿子(最左边的子节点)的指针。这个指针使得我们可以迅速找到一个节点的第一个子节点。
  2. Data: 存放节点的数据。
  3. NextBrother: 存放指向该节点的大兄弟(同一层中右边的兄弟节点)的指针。这个指针使得我们可以在同一层中迅速找到节点的下一个兄弟节点。

  通过这样的结构,整棵树可以用左儿子右兄弟链接结构表示成一棵二叉树。这种表示方式有时候被用于一些特殊的树结构,例如二叉树、二叉树的森林等。这种结构的优点之一是它更紧凑地表示树,而不需要额外的指针来表示兄弟关系。
在这里插入图片描述

   A/|\B C D/ \E   F
A
|
B -- C -- D|E -- F

即:

      A/ B   \C/ \ E   D\F

在这里插入图片描述

5.3.2 获取结点的算法

【数据结构】树与二叉树(二十):树获取大儿子、大兄弟结点的算法(GFC、GNB)

5.3.3 树和森林的遍历

【数据结构】树与二叉树(七):二叉树的遍历(先序、中序、后序及其C语言实现)

1. 先根遍历(递归、非递归)

在这里插入图片描述

【数据结构】树与二叉树(廿一):树和森林的遍历——先根遍历(递归算法PreOrder、非递归算法NPO)

2. 后根遍历(递归)

a.理论

在这里插入图片描述

b. ADL算法PostOrder

在这里插入图片描述

  1. 基本条件检查:

    • IF t=NULL THEN RETURN.:如果树的根节点 t 为空,直接返回,递归的出口条件。
  2. 递归调用子树的后根遍历:

    • PostOrder(t.child).:递归调用后根遍历算法,对当前节点 t 的第一个孩子进行遍历。
  3. 迭代调用右兄弟节点的后根遍历:

    • WHILE child≠∧ DO:使用 WHILE 循环,判断当前节点的第一个孩子是否存在(child≠∧)。
      • PostOrder(child).:递归调用先根遍历算法,对当前节点 child 进行遍历。
      • GNB(child.child).:调用算法 GNB 获取当前节点 child 的下一个兄弟节点,然后继续遍历。
  4. 打印根节点数据:

    • PRINT(Data(t)).:打印当前树节点 t 的数据。
        通过递归地调用后根遍历算法,依次访问树的根节点、根节点的孩子节点、孩子节点的兄弟节点……以此类推,完成对整个树的后根遍历。
c. 代码实现
void PostOrder(TreeNode* t) {if (t == NULL) {return;}// 递归调用子树的后根遍历TreeNode* child = getFirstChild(t);while (child != NULL) {PostOrder(child);// 迭代调用右兄弟节点的后根遍历child = getNextBrother(child);}// 打印当前树节点的数据printf("%c ", t->data);
}

3. 后根遍历(非递归)

a. ADL算法NPO
b. NPO算法解析

暂时仅提供c语言代码,ADL语言及代码解析,有缘再见……

c. 代码实现
// 后根遍历的非递归算法
void NorecPostOrder(TreeNode* root) {if (root == NULL) {return;}TreeNode* stack1[100];TreeNode* stack2[100];int top1 = -1;int top2 = -1;TreeNode* p = root;stack1[++top1] = p;while (top1 != -1) {p = stack1[top1--];stack2[++top2] = p;TreeNode* child = getFirstChild(p);while (child != NULL) {stack1[++top1] = child;child = getNextBrother(child);}}while (top2 != -1) {printf("%c ", stack2[top2--]->data);}
}
  • 参数:

    • root: 树的根节点。
  • 局部变量:

    • stack[100]: 用于模拟栈的数组,存储待访问的节点。

3. 森林的遍历

在这里插入图片描述
在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

4. 代码整合

#include <stdio.h>
#include <stdlib.h>// 定义树节点
typedef struct TreeNode {char data;struct TreeNode* firstChild;struct TreeNode* nextBrother;
} TreeNode;// 创建树节点
TreeNode* createNode(char data) {TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));if (newNode != NULL) {newNode->data = data;newNode->firstChild = NULL;newNode->nextBrother = NULL;}return newNode;
}// 释放树节点及其子树
void freeTree(TreeNode* root) {if (root != NULL) {freeTree(root->firstChild);freeTree(root->nextBrother);free(root);}
}// 算法GFC:获取大儿子结点
TreeNode* getFirstChild(TreeNode* p) {if (p != NULL && p->firstChild != NULL) {return p->firstChild;}return NULL;
}// 算法GNB:获取下一个兄弟结点
TreeNode* getNextBrother(TreeNode* p) {if (p != NULL && p->nextBrother != NULL) {return p->nextBrother;}return NULL;
}/* 使用已知的getFirstChild和getNextBrother函数实现后根遍历以t为根指针的树。*/
void PostOrder(TreeNode* t) {if (t == NULL) {return;}// 递归调用子树的后根遍历TreeNode* child = getFirstChild(t);while (child != NULL) {PostOrder(child);// 迭代调用右兄弟节点的后根遍历child = getNextBrother(child);}// 打印当前树节点的数据printf("%c ", t->data);
}// 后根遍历的非递归算法
void NorecPostOrder(TreeNode* root) {if (root == NULL) {return;}TreeNode* stack1[100];TreeNode* stack2[100];int top1 = -1;int top2 = -1;TreeNode* p = root;stack1[++top1] = p;while (top1 != -1) {p = stack1[top1--];stack2[++top2] = p;TreeNode* child = getFirstChild(p);while (child != NULL) {stack1[++top1] = child;child = getNextBrother(child);}}while (top2 != -1) {printf("%c ", stack2[top2--]->data);}
}int main() {// 构建左儿子右兄弟链接结构的树TreeNode* A = createNode('A');TreeNode* B = createNode('B');TreeNode* C = createNode('C');TreeNode* D = createNode('D');TreeNode* E = createNode('E');TreeNode* F = createNode('F');A->firstChild = B;B->nextBrother = C;C->nextBrother = D;C->firstChild = E;E->nextBrother = F;// 使用递归后根遍历算法printf("Recursive Postorder: \n");PostOrder(A);printf("\n");// 使用非递归后根遍历算法printf("Non-recursive PostOrder: \n");NorecPostOrder(A);printf("\n");// 释放树节点freeTree(A);return 0;
}

在这里插入图片描述

相关文章:

【数据结构】树与二叉树(廿二):树和森林的遍历——后根遍历(递归算法PostOrder、非递归算法NPO)

文章目录 5.1 树的基本概念5.1.1 树的定义5.1.2 森林的定义5.1.3 树的术语 5.2 二叉树5.3 树5.3.1 树的存储结构1. 理论基础2. 典型实例3. Father链接结构4. 儿子链表链接结构5. 左儿子右兄弟链接结构 5.3.2 获取结点的算法5.3.3 树和森林的遍历1. 先根遍历&#xff08;递归、非…...

精通Nginx(17)-安全管控之防暴露、限制访问、防DDos攻击、防爬虫、防非法引用

安全是每个系统都需要考虑的关键因素,Nginx在这方面提供了丰富的功能,使我们可以就实际情形做很精细调整。这些功能包括防信息暴露、客户端访问限制、通讯加密、防DDos攻击、防爬虫、防非法引用及防非法域名请求等。 目录 防信息暴露 关闭版本号 关闭目录列表 客户端访问…...

STM32 Flash

FLASH简介 Flash是常用的用于存储数据的半导体器件&#xff0c;它具有容量大&#xff0c;可重复擦写&#xff0c;按“扇区/块”擦除、掉电后数据可继续保存的特性。 常见的FLASH主要有NOR FLASH和NAND FLASH两种类型。NOR和NAND是两种数字门电路&#xff0c;可以简单地认为FL…...

文件批量重命名技巧:图片文件名太长怎么办?告别手动改名方法

在日常生活中&#xff0c;常常会遇到文件名过长导致的问题。尤其是在处理大量图片文件时&#xff0c;过长的文件名可能会使得文件管理变得混乱不堪。现在来看下云炫文件管理器如何批量重命名&#xff0c;让图片文件名变得更简洁&#xff0c;提高工作效率。 操作1、在云炫文件…...

微信小程序手写滑动tab

微信小程序手写滑动tab index.wxml <view class"tab-bar"> <scroll-view scroll-x class"tab-scroll"> <block wx:for"{{tabs}}" wx:key"index"> <view class"tab-item {{currentIndex index ? acti…...

一文读懂如何安全地存储密码

目录 引言 明文存储 基本哈希存储 加盐哈希存储 适应性哈希算法 密码加密存储 小结 引言 密码是最常用的身份验证手段&#xff0c;既简单又高效。密码安全是网络安全的基石&#xff0c;对保护个人和组织信息的安全具有根本性的作用。然而有关密码泄漏的安全问题一再发生…...

【运维面试100问】(六)buffer和cache的区别

本站以分享各种运维经验和运维所需要的技能为主 《python零基础入门》&#xff1a;python零基础入门学习 《python运维脚本》&#xff1a; python运维脚本实践 《shell》&#xff1a;shell学习 《terraform》持续更新中&#xff1a;terraform_Aws学习零基础入门到最佳实战 《k8…...

创建域名邮箱邮件地址的方法与步骤

如何创建域名邮箱邮件地址?使用Zoho Mail创建域名邮箱邮件地址的步骤简单易懂&#xff0c;操作便捷。从其他邮箱迁移到Zoho Mail的过程也相当顺畅&#xff0c;您可以轻松为所有员工创建具有企业邮箱域名的电子邮件地址。 步骤1&#xff1a;添加并验证您的域名 首先&#xff0c…...

Qt框架学习(1)

1.安装Qt官网 安装需注意的是&#xff0c;要安装开源版(有钱当我没说),而安装包都是一样的&#xff0c;主要是在注册账户时选择个人开发&#xff0c;而不要选公司&#xff0c;否则在安装时登录账号后会安装商业版Qt. 2.Qt中的快捷键 快捷键解释F4头文件和实现文件切换ShiftF…...

3D电路板在线渲染案例

从概念上讲,这是有道理的,因为PCB印制电路板上的走线从一个连接到下一个连接的路线基本上是平面的。 然而,我们生活在一个 3 维世界中,能够以这种方式可视化电路以及相应的组件,对于设计过程很有帮助。本文将介绍KiCad中基本的3D查看功能,以及如何使用NSDT 3DConvert在线…...

ResizeObserver loop limit exceeded报错解决方案

前言&#xff1a; 控制台没有报错&#xff0c;但是开发Vue项目过程中一直报ResizeObserver loop limit exceeded 错&#xff0c;找到以下解决方式。在main.js文件中重写 ResizeObserver 方法。 main.js文件 &#xff08;完整版&#xff09; import { createApp } from "v…...

【OpenCV实现图像:使用OpenCV进行图像处理之透视变换】

文章目录 概要计算公式举个栗子实际应用小结 概要 透视变换&#xff08;Perspective Transformation&#xff09;是一种图像处理中常用的变换手段&#xff0c;它用于将图像从一个视角映射到另一个视角&#xff0c;常被称为投影映射。透视变换可以用于矫正图像中的透视畸变&…...

Vue中学习笔记-数据代理

文章目录 前文提要数据代理的概念MVVM模型和Vue中的数据代理M&#xff0c;模型V&#xff0c;视图VM&#xff0c;视图模型 前文提要 本人仅做个人学习记录&#xff0c;如有错误&#xff0c;请多包涵 数据代理的概念 使用一个对象代理对另一个对象中属性的操作。 MVVM模型和Vu…...

IDEA 配置maven结合案例使用篇

1. 项目需求和结构分析 需求案例&#xff1a;搭建一个电商平台项目&#xff0c;该平台包括用户服务、订单服务、通用工具模块等。 项目架构&#xff1a; 用户服务&#xff1a;负责处理用户相关的逻辑&#xff0c;例如用户信息的管理、用户注册、登录等。 spring-context 6.0.…...

基于白鲸算法优化概率神经网络PNN的分类预测 - 附代码

基于白鲸算法优化概率神经网络PNN的分类预测 - 附代码 文章目录 基于白鲸算法优化概率神经网络PNN的分类预测 - 附代码1.PNN网络概述2.变压器故障诊街系统相关背景2.1 模型建立 3.基于白鲸优化的PNN网络5.测试结果6.参考文献7.Matlab代码 摘要&#xff1a;针对PNN神经网络的光滑…...

Android使用Kotlin利用Gson解析多层嵌套Json数据

文章目录 1、依赖2、解析 1、依赖 build.gradle(app)中加入 dependencies { implementation com.google.code.gson:gson:2.8.9 }2、解析 假设这是要解析Json数据 var responseStr "{"code": 200,"message": "操作成功","data&quo…...

DOM事件的传播机制

DOM事件的传播机制是指当一个事件在DOM树中触发时&#xff0c;它是如何在各个元素之间传播的。DOM事件传播机制分为三个阶段&#xff1a;捕获阶段、目标阶段和冒泡阶段。此外&#xff0c;还有一种常用的技术称为事件委托&#xff0c;它能够简化事件处理程序的绑定和管理。本文将…...

gitlab利用CI多工程持续构建

搭建CI的过程中有多个工程的时候&#xff0c;一个完美的构建过程往往是子工程上的更新(push 或者是merge)触发父工程的构建&#xff0c;这就需要如下建立一个downstream pipeline 子仓库1 .gitlab-ci.yml stages:- buildbuild_job:stage: buildtrigger:project: test_user/tes…...

【C++初阶】四、类和对象(构造函数、析构函数、拷贝构造函数、赋值运算符重载函数)

相关代码gitee自取&#xff1a; C语言学习日记: 加油努力 (gitee.com) 接上期&#xff1a; 【C初阶】三、类和对象 &#xff08;面向过程、class类、类的访问限定符和封装、类的实例化、类对象模型、this指针&#xff09; -CSDN博客 引入&#xff1a;类的六个默认成员函数…...

js粒子效果(二)

效果: 代码: <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>Particle Animation</title><…...

观成科技:隐蔽隧道工具Ligolo-ng加密流量分析

1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具&#xff0c;该工具基于TUN接口实现其功能&#xff0c;利用反向TCP/TLS连接建立一条隐蔽的通信信道&#xff0c;支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式&#xff0c;适应复杂网…...

【Linux】shell脚本忽略错误继续执行

在 shell 脚本中&#xff0c;可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行&#xff0c;可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令&#xff0c;并忽略错误 rm somefile…...

基于FPGA的PID算法学习———实现PID比例控制算法

基于FPGA的PID算法学习 前言一、PID算法分析二、PID仿真分析1. PID代码2.PI代码3.P代码4.顶层5.测试文件6.仿真波形 总结 前言 学习内容&#xff1a;参考网站&#xff1a; PID算法控制 PID即&#xff1a;Proportional&#xff08;比例&#xff09;、Integral&#xff08;积分&…...

IGP(Interior Gateway Protocol,内部网关协议)

IGP&#xff08;Interior Gateway Protocol&#xff0c;内部网关协议&#xff09; 是一种用于在一个自治系统&#xff08;AS&#xff09;内部传递路由信息的路由协议&#xff0c;主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...

为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?

在建筑行业&#xff0c;项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升&#xff0c;传统的管理模式已经难以满足现代工程的需求。过去&#xff0c;许多企业依赖手工记录、口头沟通和分散的信息管理&#xff0c;导致效率低下、成本失控、风险频发。例如&#…...

MMaDA: Multimodal Large Diffusion Language Models

CODE &#xff1a; https://github.com/Gen-Verse/MMaDA Abstract 我们介绍了一种新型的多模态扩散基础模型MMaDA&#xff0c;它被设计用于在文本推理、多模态理解和文本到图像生成等不同领域实现卓越的性能。该方法的特点是三个关键创新:(i) MMaDA采用统一的扩散架构&#xf…...

Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器

第一章 引言&#xff1a;语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域&#xff0c;文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量&#xff0c;支撑着搜索引擎、推荐系统、…...

OpenLayers 分屏对比(地图联动)

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 地图分屏对比在WebGIS开发中是很常见的功能&#xff0c;和卷帘图层不一样的是&#xff0c;分屏对比是在各个地图中添加相同或者不同的图层进行对比查看。…...

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决 问题背景 在一个基于 Spring Cloud Gateway WebFlux 构建的微服务项目中&#xff0c;新增了一个本地验证码接口 /code&#xff0c;使用函数式路由&#xff08;RouterFunction&#xff09;和 Hutool 的 Circle…...

算法岗面试经验分享-大模型篇

文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer &#xff08;1&#xff09;资源 论文&a…...