数据结构基础08——非线性数据结构之树基本概念

官方定义:
树(tree)是包含n(n>=0)个结点的有穷集,其中:
(1)每个元素称为结点(node);
(2)有一个特定的结点被称为根结点或树根(root)。
(3)除根结点之外的其余数据元素被分为m(m≥0)个互不相交的集合T1,T2,……Tm-1,其中每一个集合Ti(1<=i<=m)本身也是一棵树,被称作原树的子树(subtree)。

树也可以这样定义:树是由根结点和若干颗子树构成的。树是由一个集合以及在该集合上定义的一种关系构成的。集合中的元素称为树的结点,所定义的关系称为父子关系。父子关系在树的结点之间建立了一个层次结构。在这种层次结构中有一个结点具有特殊的地位,这个结点称为该树的根结点,或称为树根。

我们可以形式地给出树的递归定义如下:
单个结点是一棵树,树根就是该结点本身。
设T1,T2,..,Tk是树,它们的根结点分别为n1,n2,..,nk。用一个新结点n作为n1,n2,..,nk的父亲,则得到一棵新树,结点n就是新树的根。我们称n1,n2,..,nk为一组兄弟结点,它们都是结点n的子结点。我们还称T1,T2,..,Tk为结点n的子树。

空集合也是树,称为空树。空树中没有结点。
结点的度:一个结点含有的子结点的个数称为该结点的度;
叶结点或终端结点:度为0的结点称为叶结点;
非终端结点或分支结点:度不为0的结点;
双亲结点或父结点:若一个结点含有子结点,则这个结点称为其子结点的父结点;
孩子结点或子结点:一个结点含有的子树的根结点称为该结点的子结点;
兄弟结点:具有相同父结点的结点互称为兄弟结点;
树的度:一棵树中,最大的结点的度称为树的度;
结点的层次:从根开始定义起,根为第1层,根的子结点为第2层,以此类推;
树的高度或深度:树中结点的最大层次;
堂兄弟结点:双亲在同一层的结点互为堂兄弟;
结点的祖先:从根到该结点所经分支上的所有结点;
子孙:以某结点为根的子树中任一结点都称为该结点的子孙。
森林:由m(m>=0)棵互不相交的树的集合称为森林;

看标题,既然树是非线性数据结构,那么它与线性数据结构的区别是什么呢?我们知道线性数据结果是由后继指针如果我们把前一个节点称之为x,那么x最多只会有一个y节点直接与之对应,且y的前继节点最多只会有1个x(如链表的引用和数组的下一个顺序读取),即一对一的关联关系。
而树则是如果我们有x节点,那么最多会有n个后继节点与之对应,且这n个节点中每一个都最多只会有一个节点前继节点x,即一对多的关系。
(同理,其实后面还有一种多对多的数据结构——图,而树在某种意义上来说可以视为被阉割版的图,所以又叫树状图。从图的观点来看,树也可视为一个拥有N 个节点和N-1 条边的一个有向无环图。)
image.png

比如下面这幅图,A 节点就是 B 节点的父节点,B 节点是 A 节点的子节点。B、C、D 这三个节点的父节点是同一个节点,所以它们之间互称为兄弟节点。我们把没有父节点的节点叫作根节点,也就是图中的节点 E。我们把没有子节点的节点叫作叶子节点或者叶节点,比如图中的 G、H、I、J、K、L 都是叶子节点。
image.png

除此之外,关于“树”,还有三个比较相似的概念:高度(Height)、深度(Depth)、层(Level)。它们的定义是这样的:
image.png

image.png

在我们的生活中,“高度”这个概念,其实就是从下往上度量,比如我们要度量第 10 层楼的高度、第 13 层楼的高度,起点都是地面。所以,树这种数据结构的高度也是一样,从最底层开始计数,并且计数的起点是 0。“深度”这个概念在生活中是从上往下度量的,比如水中鱼的深度,是从水平面开始度量的。所以,树这种数据结构的深度也是类似的,从根结点开始度量,并且计数起点也是 0。“层数”跟深度的计算类似,不过,计数起点是 1,也就是说根节点的位于第 1 层。

树的三种遍历方式:

1.先(前)序遍历

前序遍历首先访问根节点,然后从左往右遍历子树 也就是根节点是在子节点之前进行处理 顺序:根左右

image.png

我们把上图的树,当做我们电脑中用到的目录,E是根节点(也就是根目录),E下面有两个子文件夹(子树)分别是A,F,A,F两个文件夹下又有各自对应的文件和文件夹。

现在我们需要遍历打印出所有文件的访问路径(如H的路径是:E/A/C/H,如cmd的tree或Linux中的ls -R命令),这个时候我们该怎么样进行遍历呢?

首先我们打开文件夹E(打开或访问时就打印文件名),发现里面有两个子文件夹A和F,我们从左向右找里面的文件,先打开A,发现新的三个目录同样的我从左开找点开B文件夹发现里面只有G没有新的目录(没子树,左边也没有其他节点),这个时候B目录遍历完毕回到文件夹A里面也就是BCD层,找B左边的文件夹C,C下面有两个左边的H没有子节点打印,然后右边的I打印,同理依次递归。最后到FKL,完成整个目录的遍历。

2.后序遍历

后序遍历是先从左往右变量子树,最后访问树的根节点。 根节点是在子节点都处理完成之后处理的 顺序:左右根

如:
还是上面的例子,我们电脑中有文件目录E。这时候我们需要计算得到任何一个文件或文件夹所占用空间大小。同理我们可以把树作为n个子树从左向右进行递归。但是在计算空间大小时,如F文件夹所占用空间我们知道F实际一个文件夹,它的大小是所有子文件(节点)大小的总和,这时我们就不能直接先打印F节点了,而是先从左向右看子文件的大小,最后在回到上层的F节点。最后打印出F节点的空间大小。

3.中序遍历

顺序:左根右 即先遍历左边的节点,再遍历右边的节点,但是需要注意的是只有中序遍历可以确定二叉树中。

总结:所谓的树的遍历其实就是以父节点为基准从左到右,先处理父节点的叫先序变量,后处理父节点的叫后序遍历,特殊情况,二叉树中因为抽象成子树后只存在3个节点,父类节点在中间处理叫中序遍历。

实现:

基于链表:

事实上由于树的种类多种多样这里只提供一个简单的基本实现,只要能表达上述结构均可。前面我们已经看到链表和树的区别可以简单看做对应的节点关系的一对一和一对多。那么我们就可以用一个节点指向多个子节点。但是我们如果要设计实现一颗不知道类型的树,可以将一个节点指向两个后继节点。一个最左边的子节点,一个为自己的兄弟节点(根节点兄弟节点为空)即可。
/**
树的一个节点
*/
class TreeNode<T>{
T  data;
TreeNode<T> firstChild;
TreeNode<T> nextSibling;
}

基于数组实现

同链表实现,数组的表结构基于默认递增的1进行确认后继关系,这里我们只需要确定递增的步长按照对应的遍历顺序添加即可(事实上通过这种方法可以很方便的实现一颗二叉树)
更新时间:2020-02-11 17:44:44

本文由 寻非 创作,如果您觉得本文不错,请随意赞赏
采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名
原文链接:https://www.zhouning.group/archives/数据结构基础07非线性数据结构之树基本概念
最后更新:2020-02-11 17:44:44

评论

Your browser is out of date!

Update your browser to view this website correctly. Update my browser now

×