砍树系列第一篇——树

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

树的定义
树是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 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)孩子链表表示法
树中每一个数据元素对应一个结点,结点中有两部分信息,一部分是其本身的数据信息,另一部分是其孩子链表的头指针,即将每个数据元素的孩子们链接成一个孩子链表,将链表的头指针和它们的双亲信息组成了一个结点,再将这些结点顺序存储起来。
砍树系列第一篇——树
文章图片
一棵树及其孩子链表存储示意图
在用孩子链表方法存储的树中,查找双亲比较困难,查找孩子却十分方便,所以比较适用于对孩子操作多的应用。由于前两种表示法都有局限性,于是结合前两种表示法,衍生出了双亲孩子链表表示法,优点不言而喻了,具体存储方法如下图所示。
砍树系列第一篇——树
文章图片
一棵树及其双亲孩子链表存储示意图 3)孩子兄弟链表存储方法
这是一种常用的存储结构。其方式是:在树中每个元素对应一个结点,每个结点除其信息域外,有两个指针,分别指向该结点的第一个孩子结点和下一个兄弟结点。
砍树系列第一篇——树
文章图片
一棵树及其孩子兄弟链表存储示意图
仔细观察不难发现,通过孩子兄弟链表存储方法,普通树转化为了二叉树,所以孩子兄弟表示法又被称为“二叉树表示法”或者“二叉链表表示法”。
【砍树系列第一篇——树】树的基本知识就介绍到这,下一篇将介绍树和森林与二叉树之间的转换规则,树和森林的遍历方式,以及对应的算法实现。

    推荐阅读