数据结构(五)——树森林

5.4 树和森林

5.4.1 树的存储结构

树的存储1:双亲表示法
用数组顺序存储各结点,每个结点中保存数据元素、指向双亲结点(父结点)的“指针”

#define MAX_TREE_SIZE 100// 树的结点
typedef struct{ElemType data;int parent;
}PTNode;// 树的类型
typedef struct{PTNode nodes[MAX_TREE_SIZE];int n;	//结点数量
}PTree;


优点:找双亲(父结点)很方便
缺点:找孩子不方便,只能从头到尾遍历整个数组

树的存储2:孩子表示法(顺序+链式存储)

#define MAX_TREE_SIZE 100struct CTNode{int child;	//孩子结点在数组中的位置struct CTNode *next;	//下一个孩子
}typedef struct{ElemType data;struct CTNode *firstChild;	//第一个孩子
}CTBox;typedef struct{CTBox node[MAX_TREE_SIZE];int n,r;	//结点数和根的位置
}CTree;

优点:找孩子很方便
缺点:找双亲(父结点)不方便,只能遍历每个链表

树的存储3:孩子兄弟表示法
树的孩子兄弟表示法与二叉树类似,采用二叉链表实现,每个结点内保存数据元素和两个指针,但两个指针的含义和二叉树结点不同

//孩子兄弟表示法结点
typedef struct CSNode{ElemType data;struct CSNode *firstchild, *nextsibling;	//第一个孩子和右兄弟结点
}CSNode, *CSTree;

 

5.4.2 树、森林与二叉树的转换

树到二叉树的转换
①先在二叉树中,画一个根节点。
②按“树的层序”依次处理每个结点。
处理一个结点的方法是:如果当前处理的结点在树中有孩子,就把所有孩子结点 “用右指针串成糖葫芦”,并在二叉树中把第一个孩子挂在当前结点的左指针下方

森林到二叉树的转换
①先把所有树的根结点画出来,在二叉树中用右指针串成糖葫芦。
②按“森林的层序”依次处理每个结点。
处理一个结点的方法是:如果当前处理的结点在树中有孩子,就把所有孩子结点“用右 指针串成糖葫芦”,并在二叉树中把第一个孩子挂在当前结点的左指针下方

注意:森林中各棵树的根节点视为平级的兄弟关系

二叉树到树的转换
①先画出树的根节点
②从树的根节点开始,按“树的层序”恢复每个结点的孩子
如何恢复一个结点的孩子:在二叉树中,如果当前处理的结点有左孩子,就把左孩 子和“一整串右指针糖葫芦” 拆下来,按顺序挂在当前结点的下方


二叉树到森林的转换
①先把二叉树的根节点和“一整串右指针糖葫芦”拆下来,作为多棵树的根节点
②按“森林的层序”恢复每个结点的孩子
如何恢复一个结点的孩子:在二叉树中,如果当前处理的结点有左孩子,就把左孩子和“一整串右指针糖葫 芦” 拆下来,按顺序挂在当前结点的下方


5.4.3 树和森林的遍历

树的先根遍历。若树非空,先访问根结点, 再依次对每棵子树进行先根遍历。(深度优先遍历)

void PreOrder(TreeNode *R){if(R!=NULL){visit(R);while(R还有下一个子树T)PreOrder(T);}
}

树的先根遍历序列与这棵树相应二叉树的先序序列相同

树的后根遍历。若树非空,先依次对每棵子树进行后根遍历,最后再访问根结点。(深度优先遍历)

树的后根遍历序列与这棵树相应二叉树的中序序列相同。

树的层次遍历(用队列实现):(广度优先遍历)
   ①若树非空,则根节点入队
   ②若队列非空,队头元素出队并访问,同时将该元素的孩子依次入队
   ③重复②直到队列为空

森林的先序遍历
森林。森林是m (m>0)棵互不相交的树的集合。每棵树去掉根节点后,其各个子树又组成森林。

若森林为非空,则按如下规则进行遍历:

  1. 访问森林中第一棵树的根结点。
  2. 先序遍历第一棵树中根结点的子树森林。
  3. 先序遍历除去第一棵树之后剩余的树构成的森林。

效果等同于依次对各个树进行先根遍历,等同于对二叉树的先序遍历。

森林的中序遍历

  1. 中序遍历森林中第一棵树的根结点的子树森林。
  2. 访问第一棵树的根结点。
  3. 中序遍历除去第一棵树之后剩余的树构成的森林

效果等同于依次对各个树进行后根遍历,等同于对二叉树的中序遍历。

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【Mysql】硬盘性能压测(Sysbench工具)

1、IOPS和吞吐量介绍 IOPS(每秒输入/输出操作数):是衡量存储设备每秒能够执行的输入/输出操作的数量。对于数据库等需要频繁读写的应用程序而言,IOPS 是一个关键的性能指标。更高的 IOPS 意味着存储设备能够处理更多的读写请求&am…

【Vue】三、使用ElementUI实现图片上传

目录 一、前端代码实现 二、后端代码实现 三、调试效果实现 一、前端代码实现 废话不多说直接上代码 <el-form-item prop"image" label"上传图片" v-model"form.image"><el-upload:action"http://localhost:8…

基于springboot+vue的智慧生活商城系统

博主主页&#xff1a;猫头鹰源码 博主简介&#xff1a;Java领域优质创作者、CSDN博客专家、阿里云专家博主、公司架构师、全网粉丝5万、专注Java技术领域和毕业设计项目实战&#xff0c;欢迎高校老师\讲师\同行交流合作 ​主要内容&#xff1a;毕业设计(Javaweb项目|小程序|Pyt…

Stable Diffusion 本地训练端口与云端训练端口冲突解决办法

方法之一&#xff0c;修改本地训练所用的端口 1 首先&#xff0c;进入脚本训练器的根目录 例如&#xff1a;C:\MarkDeng\lora-scripts-v1.7.3 找到gui.py 2 修改端口号 因为云端训练器也是占用28000和6006端口 那么本地改成27999和6007也是可以的 保存退出&#xff0c;运行启动…

如何在C语言中使用命令行参数

C语言文章更新目录 C语言学习资源汇总&#xff0c;史上最全面总结&#xff0c;没有之一 C/C学习资源&#xff08;百度云盘链接&#xff09; 计算机二级资料&#xff08;过级专用&#xff09; C语言学习路线&#xff08;从入门到实战&#xff09; 编写C语言程序的7个步骤和编程…

【C++】关联式容器——map和set

1 关联式容器 STL中我们常用的部分容器&#xff0c;比如&#xff1a;vector、list、deque、forward_list(C11)等&#xff0c;这些容器统称为序列式容器&#xff0c;因为其底层为线性序列的数据结构&#xff0c;里面存储的是元素本身。 那什么是关联式容器呢&#xff1f;它与序…

阿里云服务器2核4G服务器收费价格表,1个月和一年报价

阿里云2核4G服务器多少钱一年&#xff1f;2核4G服务器1个月费用多少&#xff1f;2核4G服务器30元3个月、85元一年&#xff0c;轻量应用服务器2核4G4M带宽165元一年&#xff0c;企业用户2核4G5M带宽199元一年。本文阿里云服务器网整理的2核4G参加活动的主机是ECS经济型e实例和u1…

JAVA面向对象编程 JAVA语言入门基础

类与对象的概念 类 (Class) 和对象 (Object) 是面向对象程序设计方法中最核心的概念。 类是对某一类事物的描述(共性)&#xff0c;是抽象的、概念上的定义&#xff1b;而对象则是实际存在的属该类事物的具体的个体&#xff08;个性&#xff09;&#xff0c;因而也称为实例(In…

透视未来工厂:山海鲸可视化打造数字孪生新篇章

在信息化浪潮的推动下&#xff0c;数字孪生工厂项目正成为工业制造领域的新宠。作为一名山海鲸可视化的资深用户&#xff0c;我深感其强大的数据可视化能力和数字孪生技术在工厂管理中的应用价值&#xff0c;同时我们公司之前也和山海鲸可视化合作制作了一个智慧工厂项目&#…

学习或复习电路的game推荐:nandgame(NAND与非门游戏)、Turing_Complete(图灵完备)

https://www.nandgame.com/ 免费 https://store.steampowered.com/app/1444480/Turing_Complete/ 收费&#xff0c;70元。据说可以导出 Verilog &#xff01;

转座子插入位点分析4------PS转座子测序数据分析

观察数据 这是经公司使用fastp质控后的数据&#xff0c;我们先挑选部分数据进行比对&#xff0c;观察序列结构 为了准确性&#xff0c;我们再次挑选另一批数据进行比对 可以看到&#xff0c;所有序列都存在一个“GTGTCAAATACTTATTTTCCCCGCTGTA”的前导序列&#xff0c;这可能…

深度学习pytorch——多层感知机反向传播(持续更新)

在讲解多层感知机反向传播之前&#xff0c;先来回顾一下多输出感知机的问题&#xff0c;下图是一个多输出感知机模型&#xff1a; 课时44 反向传播算法-1_哔哩哔哩_bilibili 根据上一次的分析深度学习pytorch——感知机&#xff08;Perceptron&#xff09;&#xff08;持续更新…

突破边界:Web3开启数字化社会的新纪元

引言 随着科技的不断进步和数字化社会的发展&#xff0c;Web3正逐渐成为了人们关注的焦点。作为新一代互联网的演进形态&#xff0c;Web3具有突破传统边界、实现去中心化的特点&#xff0c;被认为将开启数字化社会的新纪元。本文将深入探讨Web3的概念、特点、应用场景&#xf…

Java 自定义线程池实现

自定义线程池 简介任务图示阻塞队列 BlockingQueue<T>ReentrantLock代码 线程池 ThreadPool工作线程类 Worker 拒绝策略接口代码测试类 TestThreadPool为什么需要j i&#xff1f;&#xff08;lambad表达式相关&#xff09; 测试结果拒绝策略&#xff1a;让调用者自己执行…

外包干了6天,技术明显进步。。。

我是一名大专生&#xff0c;自19年通过校招进入湖南某软件公司以来&#xff0c;便扎根于功能测试岗位&#xff0c;一晃便是近四年的光阴。今年8月&#xff0c;我如梦初醒&#xff0c;意识到长时间待在舒适的环境中&#xff0c;已让我变得不思进取&#xff0c;技术停滞不前。更令…

mysql80-DBA数据库学习1

掌握能力 核心技能 核心技能 mysql部署 官网地址www.mysql.com 或者www.oracle.com https://dev.mysql.com/downloads/repo/yum/ Install the RPM you downloaded for your system, for example: yum install mysql80-community-release-{platform}-{version-number}.noarch…

Qt 写一个邮件发送程序

最近在完成一个邮箱代替的告警功能&#xff0c;写了一个邮件发送的demo 以下为代码&#xff1a; #ifndef MAINWINDOW_H #define MAINWINDOW_H#include <QMainWindow> #include<QTcpSocket> namespace Ui { class MainWindow; }class MainWindow : public QMainWin…

【STL源码剖析】【2、空间配置器——allocator】

文章目录 1、什么是空间配置器&#xff1f;1.1设计一个简单的空间配置器&#xff0c;JJ::allocator 2、具备次配置力( sub-allocation)的 SGI 空间配置器2.1 什么是次配置力2.2 SGI标准的空间配置器&#xff0c;std::allocator2.2 SGI特殊的空间配置器&#xff0c;std::alloc2.…

Java代码基础算法练习-公式求和-2024.03.24

任务描述&#xff1a; 求公式Snaaaaaa…aa…aaa&#xff08;有n个a&#xff09;之值&#xff0c;其中a是一个数字&#xff0c;为2。 例如&#xff0c;n5 时222222222222222&#xff0c;n 由键盘输入(n<5)。 任务要求&#xff1a; package march0317_0331;import java.util.…

【大模型】在VS Code(Visual Studio Code)上安装中文汉化版插件

文章目录 一、下载安装二、配置显示语言&#xff08;一&#xff09;调出即将输入命令的搜索模式&#xff08;二&#xff09;在大于号后面输入&#xff1a;Configure Display Language&#xff08;三&#xff09;重启 三、总结 【运行系统】win 11 【本文解决的问题】 1、英文不…