砍树系列第一篇——树

作者: 郭大头_Gopoop | 来源:发表于2018-11-17 13:59 被阅读15次

砍树系列第一篇——树
砍树
飞鸟集
负重前行的时候要比别人跑得更快
砍树
一封信（修改稿1）
砍树
砍树
砍树
砍树

树的本质

树其实是一种非线性结构，我们熟知的线性结构，比如数组，队列，链表，构成线性结构的每个元素至多存在一个直接前驱（或直接后继）元素。所谓非线性结构，是指在该结构中至少存在一个数据元素，有两个或者两个以上的直接前驱（或直接后继）元素。天天走的大马路，就是一种非线性结构。

树的概念

树的定义
树是n（n≥0）个有限数据元素的集合。当n=0时，称这棵树为空树。在一颗非空树T中：
1）有一个特殊的数据元素成为树的根节点，根节点是没有前驱结点的。
2）若n>1，除根节点之外的其余数据元素被分成m(m>0)个互不相交（重点加粗）的集合T1,T2,T3....Tm，其中每一个集合Ti（1≤ i ≤m）本身又是一棵树，也都称为这个根节点的子树。

可以看出，在树的定义中使用了递归概念，用树来定义树。

树结构

从上述定义和上图的示例，我们可以看出，树具有下面两个特点：
1）树的根节点没有前驱节点，除根节点之外的所有节点有且只有一个前驱节点。换句话来说，就是从根节点到子树的某个节点，只能有一条路径（树的术语，后续有解释）。
2）树中所有节点可以有任意个后继节点，当然也可以没有。
根据上述特点可知下图所示的就都不是树结构。

非树结构

树的相关术语

1）结点
在树中，一个元素也称做一个结点。
2）结点的度
结点所拥有的子树的个数称为该结点的度。
3）叶结点
度为0的结点称为叶结点，或者称为终端结点（我觉得可以叫没孩子的结点）。
4）分支结点
与叶结点相反，度不为0的结点称为分支结点，或者称为非终端结点。一棵树的结点除叶结点外，其余的都是分支结点。
5）孩子，双亲，兄弟
树中一个结点的子树的根节点称为这个结点的孩子；反过来，这个结点称为它孩子结点的双亲；具有同一个双亲的孩子结点互称为兄弟。
6）路径，路径长度
如果一棵树中的一串结点N1，N2，...，Nk有如下关系：结点Ni是Ni+1的父节点（1≤ i <k），就把N1，N2，...，Nk称为一条由N1到Nk的路径，这条路径的长度就k-1。
7）祖先，子孙
在树中，如果有一条路径从结点M到结点N，那M就称为N的祖先，而N称为M的子孙。
8）结点的层数
规定树的根节点的层数为1，其余结点的层数等于它的双亲的结点的层数加1。
9）树的深度
树中结点的最大层数称为树的深度。
10）树的度
树中各结点度的最大值称为该树的度。
11）有序树和无序树
如果一棵树中结点的各子树从左到右是有次序的，那么如果交换了某结点各子树的相对位置，则会构成不同的树，这样的树称为有序树；反之，则称为无序树。
12）森林
零棵或有限棵不相交的树的集合称为森林。自然界中树和森林是不同的概念，但在数据结构中，树和森林只有很小的区别。任何一棵树，删除根结点就变成了森林。

树的表示

话不多说，直接上图。

树表示法

树的基本操作

1）init（t）：初始化一颗空树t。
2）root（x）：求结点x所在树的根节点。
3）parent（t，x）：求树t中结点x是双亲结点。
4）child（t，x，i）：求树t中结点x的第i个孩子结点。
5）rightSibling（t，x）：求树t中结点x的第一个右边兄弟结点。
6）insert（t，x，i，s）：把以s为根结点的树插入到树t中作为结点x的第i棵子树。
7）delete（t，x，i）：在树t中删除结点x的第i棵子树。
8）tranverse（t）：树的遍历操作，即按某个方式访问树t中的每个结点，且使每个结点只被访问一次。

树的存储

树的存储有多种方式，既可以采用顺序存储结构，也可以采用链式存储结构，但无论采用哪种存储方式，都要求存储不但能够存储各结点本身的数据，还要能唯一地反映树中各结点之间的逻辑关系，每种存储方式都各有各的有点。常见的存储方法有以下几种。
1）双亲链表存储方法
由树的定义可以知道，树中的每个节点都有唯一的一个双亲结点，根据这个特性，可以用一组连续的存储空间存储树中的各个结点，每个节点除了存放本身的信息外还有其双亲结点存储位置，树的这种存储方法称为双亲链表表示法，如下所示。

一棵树及其双亲静态链表存储示意图

当算法中需要在树结构中频繁地查找某结点的父结点或者根节点时，使用双亲表示法最合适。当频繁地访问结点的孩子结点时，双亲表示法就很麻烦，采用孩子链表表示法就很简单。
2）孩子链表表示法
树中每一个数据元素对应一个结点，结点中有两部分信息，一部分是其本身的数据信息，另一部分是其孩子链表的头指针，即将每个数据元素的孩子们链接成一个孩子链表，将链表的头指针和它们的双亲信息组成了一个结点，再将这些结点顺序存储起来。