【数据结构-初阶】二叉树(1)---树的相关概念
🎈主页传送门:良木生香
🔥个人专栏:《C语言》 《数据结构-初阶》 《程序设计》
🌟人为善,福随未至,祸已远行;人为恶,祸虽未至,福已远离
上期回顾:在上一篇文章中(这是文章链接:【数据结构-初阶】详解线性表(5)---队列),我们学习了初阶数据结构中的后一个线性表---队列,那么在初阶线性结构中线性表的内容我们就告一段落了,今天我们就进入到初阶段数据结构中的非线性表这块知识的学习.在这块知识中,我们会学习到树,但是还不学习图,这会等到我们学习C++语言的时候详细讲解
目录
在学习二叉树之前,我们要先了解一下什么是树
一、树的相关概念
讲到树，我们就能联想到平时生活中所看到的植物树，那我们今天要讲的树与平时看到的树有联系吗？有的兄弟，当然有，我们今天要将的树灵感就是来源于生活中的树
生活中的树根是在地下的，分支是朝天上生长的，所以我们说树是向阳而生的，而我们今天要讲的树长这样：
1.树的概念与结构：
树是一种非线性的数据结构，与前面讲的线性表不同，它是由n(n>=0)个有限节点组成一个具有层次关系的集合.我们将其称之为树是因为它看起来像是一颗倒挂的树,也就是说根是朝上的,叶子结点是朝下的.
- 它有一个特殊的节点,叫做根节点,这个节点是没有前驱节点的
- 除了根节点之外,剩下的其他节点被分成M(M>0)个互不相交的集合,T1,T2,T3.....Tm.其中一个集合Ti(1<Ti<M)又是一颗结构与树类似的子树.每棵子树的根节点有且只会有一个前驱,可以有0个或者多个后驱,因此,树是递归定义的.
小贴士:树形结构中,子树不能有交集,否则不是树形结构
非树形结构的像下面这样:
- 标有问号的就是子树中有交集的,这样就不是树形结构了,如果相交了,那就是图,不是树了
- 除了根节点之外,其他节点有且仅有一个父节点
- 一颗N节点的树有N-1条边
2、树的相关术语
介绍树的相关术语,我们就拿下面这张图做例子:
父节点/双亲节点:若一个节点含有子节点,那么这个节点成为其子节点的父节点;像上图中,A是B的父节点;
子节点/孩子节点:一个结点含有的子树的根节点成为该节点的子结点;像上图中,B是A的子结点/孩子节点
结点的度:一个结点有几个孩子,那他的度就是多少;比如A的度是6,F的度是2的等等...
树的度:一棵树中,最大结点的度称为树的度,如上图:树的度为6
叶子结点/终端结点:度为0的结点成为叶结点,如上图:B、C、H、I...等等
分支结点/非终端结点:度不为0的结点,像上图中的D、E、F、G...
兄弟结点:具有相同父结点的结点互相称为兄弟结点(亲兄弟),像上图中的B、C是兄弟结点
结点的层次:从根开始定义起,根为第1层,跟的子结点是第2层,以此类推;
树的高度或者深度:树中结点的最大层次;像上图中的树的高度为4;
结点的祖先:从根到该结点所经分支上的所有结点;像上图中,A是所有节点的祖先;
路径:一条从树任意结点出发,沿父结点-子结点连接,达到任意结点的序列;比如A到Q的路径为:A-E-J-Q;H到Q的路径为:H-D-A-E-J-Q
子孙:以某个结点为根的子树中任以结点都称为该节点的子孙.像上图中:所有节点都是A的子孙;
森林:由m(m>0)棵互补相交的树的集合称为森林
3、树的表示方法
树结构相对线性表就⽐较复杂了，要存储表⽰起来就⽐较⿇烦了，既然保存值域，也要保存结点和结 点之间的关系，实际中树有很多种表⽰⽅式如：双亲表⽰法，孩⼦表⽰法、孩⼦双亲表⽰法以及孩⼦兄弟表⽰法等。
在这么多方法里面，我们应该怎么选择哪个方法作为我们讲解的方法呢？我们选择孩子兄弟表示法，这也是前辈们在最初探索树的时候想出来的，因为这种方法比较容易我们理解
下面是树的结构体:
struct TreeNode { struct Node* child; // 左边开始的第⼀个孩⼦结点 struct Node* brother; // 指向其右边的下⼀个兄弟结点 int data; // 结点中的数据域 };怎么理解这个结构体呢?不着急,请看下图:
我们以这个图为例,那么这棵树在结构体中的具象化就应该是这样子的:
4、树形结构在生活中的具体应用:
树形结构在生活中有许多的应用,拿个最简单的例子来说,就像我们电脑上的文件管理器,就是树形结构的应用,文件管理都是一层一层向下管理的:
以上就是我对树的概念内容的分享了,感谢大佬们的阅读~~~~
文章是自己写的哈，有什么描述不对的、不恰当的地方，恳请大佬指正，看到后会第一时间修改，感谢您的阅读.
