以前我们学的线性结构是一对一的线性关系,但现实中,还有一对多的情况要处理,那就是树形结构。今天我们将学习树的概念及结构、和树的三种常见表示方法。
树是一种非线性的数据结构,它是由n(n >= 0)个有限结点组成的一个具有层次关系的集合。
答案是: 因为它的逻辑图看起来像一颗倒挂的树,根朝上,叶向下。如下图:
空树: n=0时称为空树。
根节点: 有且仅有一个特定的结点,称为根(Root)节点。(根节点没有前驱结点)
树是递归实现的: 当n>1时,除根节点外,其余结点可分为m(m>0)个互不相交的有限集T1,T2,……Tm,其中每一个集合Ti(1<= i <=m)本身又是一颗树,并且称为根的子树(SubTree)。(每颗子树的根节点有且仅有一个前驱,可以有0个或多个后继)简单来说:任何一颗树都由根与子树组成。(没有子树就结束) 如下图:
① 对于任意一棵树根节点都是唯一,子树的根节点是子树的。
② 在树形结构中,子树之间一定是互不相交的,否则就不是树型结构。如下图:
树这种一对多的结构相对线性表就比较复杂了,要存储表示起来就比较麻烦了,既要保存值域,也要保存结点和结点之间的关系, 不过充分利用顺序存储和链式存储结构的特点,完全可以实现树的存储结构的表示。我们这里了解三种不同的表示法:双亲表示法、孩子表示法、孩子兄弟表示法。
定义: 用一组连续空间存储树的节点,同时在每个结点中,附设一个指示器指示其双亲结点在表中的位置。结点结构如下图所示:
其中data是数据域,存储结点的数据信息。parent是指针域,存储该结点的双亲在数组中的下标,因为根节点没有双亲,所以我们约定根节点的位置域设置为-1。
实现: 树的结构需要有三个成员:结点数组、结点数、根的位置,所以我们将其定义为一个结构体。
双亲表示法的代码实现:
//树节点的数据类型
typedef int TElemType;
//结点结构
typedef struct PTNode
{
TElemType data;//结点数据域
int parent;//结点指针域,指向双亲的下标位置
}PTNode;
//树结构
typedef struct PTree
{
PTNode* a;//指向堆区开辟的节点数组
int root;//根节点的位置
int size;//结点数
}PTree;
如下图中树结构和树双亲表示所示:
优缺点:
优点:①找双亲容易;②顺序存储。
缺点:找孩子难,需要遍历整个结构。
定义: 由于树中每个结点可能有多棵子树,可以考虑用多重链表,即每个结点有多个指针域,其中每个指针指向一棵子树的根节点,我们把这种方法叫做多重链表表示法。
因为树的每个结点的度,也就是它的孩子个数是不同的。所以我们有两种设计方案来解决。
方案一(树的度已知):结点同构 ——已知树的度为d,指针域的个数就等于树的度。其结构如下图:
其中data是数据域,child1到childd是指针域,用来指向该结点的孩子结点。
代码示例:
//已知树的度为N
#define N 5
//树的节点
typedef struct TreeNode
{
struct TreeNode* child[N];//指针数组——存储孩子结点的位置
int data;//存储数据
}TreeNode;
如下左图的树,树的度是3,所以指针域的个数是3,孩子表示如下右图所示:
如图我们可知这种方法当树中很多结点的度小于d时,结点中有很多指针域为空,空间浪费。
方案二(树的度未知):孩子表示法——理解两个结构:①孩子结点;②表头结点。然后使用顺序存储实现孩子表示法。 如图所示:
①孩子结点: 就是用单链表存储某个结点的所有孩子结点的地址(注:n个结点有n个孩子链表,如果是叶子结点则该链表为空。)结构如下所示:
②表头结点: 有两个成员:data成员存储某个结点的数据信息;firstchild成员存储该结点孩子链表的头指针。结构如图所示:
③树结构: 由三个成员组成:指向表头数组的指针a、保存根位置的root、保存节点数的size。
代码示例:
//孩子结点
typedef struct CTNode
{
int child;//数据域,存储孩子结点在表头数组中的下标
struct CTNode* next;//指向下一个孩子结点
}CTNode;
//表头结点
typedef struct
{
int data;//存储结点的数据
CTNode* firstchild;//存储孩子链表的头指针
}CTBox;
//树的结构
typedef struct
{
CTBox* a;//指向堆区开辟表头数组
int root;//根位置
int size;//节点数
}Tree;
定义: 我们观察发现,任意一棵树,它的节点的第一个孩子如果存在就是唯一,它的右兄弟如果存在也是唯一的。因此,我们设置两个指针,分别指向该结点的第一个孩子和此结点的右兄弟,也可叫做左兄弟右孩子法。结构如图所示:
代码示例:
typedef int DataType;
typedef struct TreeNode
{
struct Node* firstChild1; // 第一个孩子结点
struct Node* pNextBrother; // 指向其下一个兄弟结点
DataType data; // 结点中的数据域
}TreeNode;
如下图树结构与孩子兄弟的表示:
总结:这三种表示方法就是分别从孩子、双亲、兄弟的角度设计的。
文章浏览阅读1.4w次,点赞83次,收藏82次。随着科技的不断进步,人工智能已经成为了各行各业的必备技能。特别是在内容创作领域,人工智能生成内容(AIGC)正逐渐成为趋势。AI可以创造出优秀的、原创的文章和故事,这为创作者们提供了一种新的创作方式。同时,AIGC技术也可以节省人力成本,提高内容生产效率。但是,如何在使用技术的前提下保持内容的原创性和质量,这是我们需要思考的问题。
文章浏览阅读3.7k次。mysql-“连接失败:用户'root'@'localhost'(使用密码:是)的访问被拒绝”这个问题在这里已有答案:MySQL错误1045(28000):用户'bill'@'localhost'的访问被拒绝(使用密码:是) 35个答案我写了一些PHP网页使用的函数,以便与mysql数据库进行交互。 当我在服务器上测试它们时,..._mysql -uroot -p 数据库访问拒绝oot @localhost
文章浏览阅读5k次,点赞103次,收藏105次。springboot整合jetcache使用详解_springboot集成jetcache如何操作jetcache
文章浏览阅读2.9k次。win11要求TPM2.0,在Esxi上无法直接安装。记录下安装办法。网上安装可信平台模块的方法,貌似只有workstations可以,Esxi不行,只能采用绕开检测的办法。安装程序开始后,Shift+F10打开命令行界面,输入 regedit 打开注册表,定位到HKEY_LOCAL_MACHINE\SYSTEM\SetupSetup→New→Key,创建名为“LabConfig”的项目,右键LabConfig →New→DWORD(32-bit)Value,名称为“BypassTPMCheck_esxi 安装windows11
文章浏览阅读1.6k次,点赞40次,收藏41次。立体视觉、单目系统、双目系统、视差_双目立体视觉
文章浏览阅读1.6k次。数据库开发环境的搭建包括数据库的创建、提示:以下是本篇文章正文内容,下面案例可供参考以上就是数据库开发环境的简单搭建过程了。_数据库搭建
文章浏览阅读1.7k次。绘制应力应变的方法有很多,常规的做法是把数据文件拖入到origin绘图,还有一个简单的方法是使用python脚本,在模拟完成后,直接运行一下脚本就能得到应力应变曲线,可以快速的观察运行结果。_混凝土应力应变曲线图绘制代码
文章浏览阅读760次,点赞2次,收藏3次。1、写一个函数,用户输入任意两个数字的任意算术运算(简单的计算器小功能) , 并能弹出运算后的结果。 var num1 = prompt('第一个数字:'); var num2 = prompt('第二个数字:'); function getjisuan(num1,num2){ return [parseFloat(num1) + parseFloat(num2), num1 * num2, num1 / num2]; } alert(getjisuan(num1,num2));_写一个函数,实现用户输入任意两个数字的任意算术运算(简单的计算器小功能),并能弹
文章浏览阅读1.3w次,点赞8次,收藏52次。1 sklearn中的线性回归sklearn中的线性模型模块是linear_model,我们曾经在学习逻辑回归的时候提到过这个模块。linear_model包含了 多种多样的类和函数:普通线性回归,多项式回归,岭回归,LASSO,以及弹性网。2 多元线性回归LinearRegression其中右下角的2表示向量 的L2范式,也就是我们的损失函数所代表的含义。在L2范式上开平方,就是我们的 损失函数。这个式子,也正是sklearn当中,用在类Linear_model.LinerReg._sklearn 线性回归
文章浏览阅读4.3w次,点赞12次,收藏57次。.CSV文件是以逗号分割的数据仓储,读取数据时从每一行中读取一条数据元祖,也就是一条数据,再用字符分割的方式获取表中的每一个数据项。 package com.conn.csv; import java.io.BufferedReader; import java.io.FileReader; /** * @desc: 读取csv文件 * @..._java csv剧中
文章浏览阅读183次。一、Web开发入门1.1 引入 之前的程序: java桌面程序,控制台控制,socket gui界面。javase规范 现在和以后的程序:java web程序。浏览器控制。javaee规范1.2 软件的结构C/S (Client - Server 客户端-服务器端):典型应用:QQ软件 ,飞秋,红蜘蛛。特点:1)必须下载特定的客户端程序。..._蚂蚁元学堂
文章浏览阅读6.2k次,点赞8次,收藏38次。参考Computing Euler angles from a rotation matrix旋转矩阵转换为欧拉角参考代码#Ref: https://www.learnopencv.com/rotation-matrix-to-euler-angles/def isRotationMatrix(R): ''' checks if a matrix is a valid rotation matrix(whether orthogonal or not) ''' Rt = n._欧拉角和旋转矩阵