【数据结构】树与二叉树(廿一):树和森林的遍历——先根遍历(递归算法PreOrder、非递归算法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. 先根遍历(递归)
        • a.理论
        • b. ADL算法PreOrder
        • c. 代码实现
      • 2. 先根遍历(非递归)
        • a. ADL算法NPO
        • b. NPO算法解析
        • c. 代码实现
      • 3. 代码整合

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 树和森林的遍历

1. 先根遍历(递归)

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

a.理论

在这里插入图片描述

b. ADL算法PreOrder

在这里插入图片描述

  1. 基本条件检查:

    • IF t=NULL THEN RETURN.:如果树的根节点 t 为空,直接返回,递归的出口条件。
  2. 打印根节点数据:

    • PRINT(Data(t)).:打印当前树节点 t 的数据。
  3. 递归调用子树的先根遍历:

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

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

  通过递归地调用先根遍历算法,依次访问树的根节点、根节点的孩子节点、孩子节点的兄弟节点,以此类推,完成对整个树的先根遍历。

c. 代码实现
void PreOrder(TreeNode* t) {
    // 基本条件检查
    if (t == NULL) {
        return;
    }

    // 打印当前树节点的数据
    printf("%c ", t->data);

    // 递归调用子树的先根遍历
    TreeNode* child = getFirstChild(t);
    while (child != NULL) {
        PreOrder(child);
        // 迭代调用右兄弟节点的先根遍历
        child = getNextBrother(child);
    }
}

2. 先根遍历(非递归)

a. ADL算法NPO

在这里插入图片描述

b. NPO算法解析
  1. 栈的初始化:

    • CREATE(S): 创建一个栈 S 用于存储待访问的节点。
  2. 初始节点指针 p 的设置:

    • p ← t: 将当前节点指针 p 设置为树的根节点 t
  3. 遍历过程:

    • NPO3. [若 p 所指结点不为空,访问 p 所指结点,将 p 压入栈,并将其 FirstChild 指针设为 p.]
      • 如果当前节点 p 不为空,访问该节点的数据,将 p 压入栈,并将 p 的第一个孩子节点设置为新的 p
  4. While 循环:

    • WHILE p ≠ ∧ DO
      • 进入一个循环,只要当前节点 p 不为空。
      • PRINT(Data(p)): 打印当前节点的数据。
      • S <= p: 将当前节点 p 压入栈。
      • p ← FirstChild(p): 将 p 移动到其第一个孩子节点。
  5. 后续处理:

    • WHILE p = ∧ AND S 非空 DO
      • 进入一个循环,只有当 p 为空而且栈 S 不为空时。
      • p <= S: 弹出栈顶元素,将其赋给 p
      • p ← NextBrother(p): 将 p 移动到其下一个兄弟节点。
  6. 结束条件:

    • IF S 非空 THEN GOTO NPO3: 如果栈 S 非空,跳转到标签 NPO3,继续遍历。
c. 代码实现
// 先根遍历的非递归算法
void NorecPreOrder(TreeNode* t) {
    if (t == NULL) {
        return;
    }

    TreeNode* stack[100];  // 假设栈的最大大小为100
    int top = -1;

    TreeNode* p = t;

    while (p != NULL || top != -1) {
        if (p != NULL) {
            // 访问当前节点
            printf("%c ", p->data);

            // 将当前节点入栈
            stack[++top] = p;

            // 移动到当前节点的第一个孩子
            p = getFirstChild(p);
        } else {
            // 出栈并移动到下一个兄弟节点
            p = getNextBrother(stack[top--]);
        }
    }
}
  1. 参数:

    • t: 树的根节点。
  2. 局部变量:

    • stack[100]: 用于模拟栈的数组,存储待访问的节点。
    • top: 栈顶指针,表示栈的当前位置。
  3. 算法过程:

    • 如果树的根节点为空 (t == NULL),直接返回。
    • 初始化当前节点指针 p 为树的根节点 t
    • 使用循环遍历整个树结构,直到当前节点 p 为空且栈 stack 为空。
    • 在循环中:
      • 如果当前节点 p 不为空:
        • 访问当前节点的数据:printf("%c ", p->data);
        • 将当前节点入栈:stack[++top] = p;
        • 移动到当前节点的第一个孩子:p = getFirstChild(p);
      • 如果当前节点 p 为空:
        • 出栈并移动到下一个兄弟节点:p = getNextBrother(stack[top--]);
    • 循环结束后,遍历完成。
  4. 栈的作用:

    • 使用栈来模拟递归调用过程,确保每个节点都能被正确地访问。
    • 入栈操作保存了当前节点的信息,以便在遍历完当前节点的子树后返回到其兄弟节点。
    • 这个算法的时间复杂度是 O(n),其中 n 是树的节点数量。

3. 代码整合

#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 PreOrder(TreeNode* t) {
    // 基本条件检查
    if (t == NULL) {
        return;
    }

    // 打印当前树节点的数据
    printf("%c ", t->data);

    // 递归调用子树的先根遍历
    TreeNode* child = getFirstChild(t);
    while (child != NULL) {
        PreOrder(child);
        // 迭代调用右兄弟节点的先根遍历
        child = getNextBrother(child);
    }
}

// 先根遍历的非递归算法
void NorecPreOrder(TreeNode* t) {
    if (t == NULL) {
        return;
    }

    TreeNode* stack[100];  // 假设栈的最大大小为100
    int top = -1;

    TreeNode* p = t;

    while (p != NULL || top != -1) {
        if (p != NULL) {
            // 访问当前节点
            printf("%c ", p->data);

            // 将当前节点入栈
            stack[++top] = p;

            // 移动到当前节点的第一个孩子
            p = getFirstChild(p);
        } else {
            // 出栈并移动到下一个兄弟节点
            p = getNextBrother(stack[top--]);
        }
    }
}

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 Preorder: \n");
    PreOrder(A);
    printf("\n");
    // 使用非递归先根遍历算法
    printf("Non-recursive PreOrder: \n");
    NorecPreOrder(A);
    printf("\n");

    // 释放树节点
    freeTree(A);

    return 0;
}

在这里插入图片描述

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

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

相关文章

强化学习笔记

这里写自定义目录标题 参考资料基础知识16.3 有模型学习16.3.1 策略评估16.3.2 策略改进16.3.3 策略迭代16.3.3 值迭代 16.4 免模型学习16.4.1 蒙特卡罗强化学习16.4.2 时序差分学习Sarsa算法&#xff1a;同策略算法&#xff08;on-policy&#xff09;&#xff1a;行为策略是目…

INFINI Labs 产品更新 | 发布 Easysearch Java 客户端,Console 支持 SQL 查询等功能

近年来&#xff0c;日志管理平台越来越流行。使用日志管理平台可以实时地、统一地、方便地管理和查看日志&#xff0c;挖掘日志数据价值&#xff0c;驱动运维、运营&#xff0c;提升服务管理效率。 方案架构 Beats 是轻量级采集器&#xff0c;包括 Filebeat、Metricbeat 等。E…

开发者生态:共享知识,携手共进,共创技术辉煌

开发者生态&#xff1a;共享知识&#xff0c;携手共进&#xff0c;共创技术辉煌 在数字化时代&#xff0c;开发者是推动技术进步和创新的重要力量。他们创造着改变世界的软件和应用&#xff0c;推动着技术的边界不断向前。而在这个快速发展的时代&#xff0c;建立一个健康、活跃…

【Q2—30min】

1.socket服务端创建过程 socket是应用层与TCP/IP协议族通信的中间软件抽象层&#xff0c;它是一组接口。在设计模式中&#xff0c;Socket其实就是一个门面模式&#xff0c;它把复杂的TCP/IP协议族隐藏在Socket接口后面&#xff0c;对用户来说&#xff0c;一组简单的接口就是全部…

mysql面试题——存储引擎相关

一&#xff1a;MySQL 支持哪些存储引擎? MySQL支持多种存储引擎&#xff0c;比如InnoDB&#xff0c;MyISAM&#xff0c; MySQL大于等于5.5之后&#xff0c;默认存储引擎是InnoDB 二&#xff1a;InnoDB 和 MyISAM 有什么区别? InnoDB支持事务&#xff0c;MyISAM不支持InnoD…

前端入门(二)Vue2到Vue3

文章目录 Vue简介Vue的特点Hello, Vue Vue基本语法模板语法数据绑定&#xff08;v-bind、v-model&#xff09;el与data的两种写法 数据代理实现原理Object.defineProperty()数据代理 事件处理&#xff08;v-on:click / click&#xff09;事件修饰符键盘事件&#xff08;略&…

思伟老友记 | 厦门路桥翔通海砼建材有限公司与思伟软件携手走过23年

23年 感恩相伴 携手成长 2001年-2023年&#xff0c;厦门路桥翔通海砼建材有限公司已携手上海思伟软件有限公司走过23年。从最初的半手动生产模式到如今的自动生产一体化系统&#xff0c;海砼公司通过思伟软件生产混凝土累计超过1000万m&#xff0c;思伟软件则借助海砼公司的实…

C语言——函数的嵌套调用

#define _CRT_SECURE_NO_WARNINGS 1#include<stdio.h>void new_line() {printf("Hello\n"); }void three_line() {int i0;for(i0;i<3;i){new_line();} }int main() {three_line();return 0; }

测试用例的设计方法(全):正交实验设计方法|功能图分析方法|场景设计方发

正交实验设计方法 一.方法简介 利用因果图来设计测试用例时, 作为输入条件的原因与输出结果之间的因果关系,有时很难从软件需求规格说明中得到。往往因果关系非常庞大,以至于据此因果图而得到的测试用例数目多的惊人&#xff0c;给软件测试带来沉重的负担&#xff0c;为了有效…

Vue3 常用组件

一、Fragment组件 Vue2 的template 模板中必须要有一个根标签&#xff0c;而我们在Vue3 的模板中不需要使用根标签就能渲染&#xff0c;因为Vue3 在内部会将多个标签包含在一个Fragment 虚拟元素中。 好处就在于可以减少标签的层级&#xff0c;减小内存占用。 二、Teleport组…

基于ResNet框架的CNN

数据准备 DATA_URL http://download.tensorflow.org/example_images/flower_photos.tgz 一、训练集和验证集的划分 #spile_data.pyimport os from shutil import copy import randomdef mkfile(file):if not os.path.exists(file):os.makedirs(file)file flower_data/flower…

YOLO目标检测——无人机航拍行人检测数据集下载分享【含对应voc、coc和yolo三种格式标签】

实际项目应用&#xff1a;智能交通管理、城市安防监控、公共安全救援等领域数据集说明&#xff1a;无人机航拍行人检测数据集&#xff0c;真实场景的高质量图片数据&#xff0c;数据场景丰富标签说明&#xff1a;使用lableimg标注软件标注&#xff0c;标注框质量高&#xff0c;…

whisper使用方法

看这个 github https://github.com/Purfview/whisper-standalone-win/tags下载 视频提取音频 ffmpeg -i 222.mp4 -vn -b:a 128k -c:a mp3 output.mp3截取4秒后的音频 ffmpeg -i output.mp3 -ss 4 -c copy output2.mp3使用 whisper-faster.exe 生成字幕 whisper-faster.exe …

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

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

游戏报错d3dcompiler_47.dll缺失怎么修复,总结多种修复方法

在使用这些软件和游戏的过程中&#xff0c;我们常常会遇到一些问题&#xff0c;其中之一就是d3dcompiler_47.dll丢失的问题。这个问题可能会导致软件或游戏无法正常运行&#xff0c;给用户带来困扰。本文将详细介绍解决软件游戏d3dcompiler_47.dll丢失的方法&#xff0c;帮助您…

读懂:“消费报销”模式新零售打法,适用连锁门店加盟的营销方案

读懂&#xff1a;“消费报销”模式新零售打法&#xff0c;适用连锁门店加盟的营销方案 引言&#xff1a;2023年的双十一已经落下帷幕&#xff0c;作为每年的经典电商促销节&#xff0c;今年已是第15个年头&#xff0c;但是今年各大电商平台却都是非常默契的&#xff0c;没有公布…

《数据:挖掘价值,洞察未来

大数据&#xff1a;挖掘价值&#xff0c;洞察未来 我们正身处一个数据驱动的时代&#xff0c;大数据已经成为企业和个人决策的重要依据。本文将深入探讨大数据的魅力&#xff0c;挖掘其价值&#xff0c;并洞察未来发展趋势&#xff0c;让我们一起领略大数据的无穷奥秘。 一、大…

《云计算:云端协同,智慧互联》

《云计算&#xff1a;云端协同&#xff0c;智慧互联》 云计算&#xff0c;这个科技领域中的热门词汇&#xff0c;正在逐渐改变我们的生活方式。它像一座座无形的桥梁&#xff0c;将世界各地的设备、数据、应用紧密连接在一起&#xff0c;实现了云端协同&#xff0c;智慧互联的愿…

比科奇推出5G小基站开放式RAN射频单元的高性能低功耗SoC

全新的PC805作为业界首款支持25Gbps速率eCPRI和CPRI前传接口的系统级芯片&#xff08;SoC&#xff09;&#xff0c;消除了实现低成本开放式射频单元的障碍 中国北京&#xff0c;2023年11月 - 5G开放式RAN基带芯片和电信级软件提供商比科奇&#xff08;Picocom&#xff09;今日…

pip list 和 conda list的区别

PS : 网上说conda activate了之后就可以随意pip了 可以conda和pip混用 但是安全起见还是尽量用pip 这样就算activate了&#xff0c;进入base虚拟环境了 conda与pip的区别 来源 Conda和pip通常被认为几乎完全相同。虽然这两个工具的某些功能重叠&#xff0c;但它们设计用于不…