数据结构非线性结构树介绍及存储方法

叁歲伎倆 2022-03-01 07:05 319阅读 0赞

所谓树, 其实跟链表有类似的地方,  就是都是由节点和指针构成的数据结构.

在链表中,  每1个节点(尾节点除外)只有1个指针指向下1个节点. 所以链表各个节点可以由一条线链接起来, 就是一种线性结构.

而在树中, 每1个节点可以有1个或多个指针指向下1个节点,  如下图:

![444127020140507235726070.png][]

所以树是一种非线性结构, 对于这种结构, 有很多算法都要依赖递归来实现, 否则就相当复杂, 所以很多教程都把递归作为1个专题放在树这章之前讲解, 就是这个原因.

其实树也可以利用连续存储来实现， 也就是说节点不需具有指向别的节点的指针， 但是这种树必须是完全二叉树。 下面会详细提到。

## 1. 树的定义    ##

树的定义有两种, 一种是专业的定义, 跟递归有关.

**        专业定义:**

**                 1. 只有1个称为根的节点.**

**                 2. 有若干个互不相交的子树, 这些子树本身也是树.**

解析下,子树本身也是树, 就如上上图的树A, 根就是是A了, 它具有2个子树, 分别是B1 和 B2, 而B1和B2也是1棵树啊, 所以, 这个定义跟递归有关.

**           通俗定义:**

**                 1. 树是有节点和边组成.(为什么不用指针这个字眼,用边?因为树是可以利用连续存储来实现的，下面会提到)**

**                 2. 每1个节点只有1个父节点, 但是可以有多个子节点.**

**                 3. 但是有1个节点例外, 该节点没有父节点, 此节点就是根节点.**

## 2. 树的一些专业术语. ##

**节点**:

构成树的元素, 通常节点里会包含指向其他节点的指针.  在C语言中, 节点通常是由结构体来表示的.

**父节点**:

节点的上1级节点,  通常1个节点有且只有1个父节点, 根节点例外, 根节点没有父节点.

**子节点**:

节点的下一级节点, 1个节点可以有1个或多个子节点, 也可以没有子节点.

**子孙**:

1个节点的子节点或者子节点的子节点....,等所有下级节点都可以成为这个节点的子孙,  1棵树的所有节点都是根节点的子孙.   上图C2 是B1的子孙, 但不是B2的子孙.

**兄弟**:

拥有同1个父节点的若干个节点成为兄弟, 上图B1 就是 B2的兄弟

**堂兄弟**:

不属于同1个父节点, 但是它们的父节点属与同1个父节点的若干个节点就是堂兄弟. 上图C1 就是 C3的堂兄弟.

**深度**:

1棵树从根节点到最底层节点的层数称之为深度.   根节点是第1层.

**叶子节点**:

没有子节点的节点, 因为叶子不同于树干, 不能再分叉了.  当1个棵树只有1个节点, 那么这个节点是根节点. 也是叶子节点.

**非终端节点**:

实际就是非叶子节点,  就是具有子节点的节点.

**度**:

1个节点的子节点个数成为这个节点的度

1个树中拥有最大度的节点的度就是这个树的度.

**森林**:

n个互不相交的树的集合, 成为森林.

## 3. 树的分类 ##

**一般的树**:

任意1个节点的子节点的个数都不受限制的树.

**二叉树**: (binary tree)

任意1个节点的个数最多有连个, 且子节点的位置不能被更改, 这种树就是二叉树.

第一句容易理解, 关键是第二句, 子节点的位置不能更改?   其实意思就是二叉树是有序的, 它的节点最多只有2个子节点, 分别是左子节点和右子节点,  它们的顺序不能被更改. 也不能更改节点的父子点(移动子树),我们称为这种树是有序的树

一般的树没有这种要求, 可以是有序的树, 也可以是无序的树(子节点位置可更改),    但是2叉树必须是有序的树.

二叉树还有分类

**满二叉树**: (full binary tree)

在不增加层数的情况下,  无法再多添加1个节点的二叉树, 就是满二叉树. 例如上图那个树就是非满2叉树, 因为还可以添加1个C4节点在B2节点下.

添加了C4节点后, 就是1个满二叉树, 如下图:

![444127020140508000133035.png][]

假如1个满二叉树的层数是k, 那么它的节点个数必定是 (2^k-1).

这里顺便贴个等比数列求和的推导公式:

（1）Sn=a1+a2+a3+...+an(公比为q)
    （2）q*Sn=a1*q+a2*q+a3*q+...+an*q =a2+a3+a4+...+a(n+1)
    （3）Sn-q*Sn=a1-a(n+1)
    （4）(1-q)Sn=a1-a1*q^n
    （5）Sn=(a1-a1*q^n)/(1-q)
    （6）Sn=(a1-an*q)/(1-q)
    （7）Sn=a1(1-q^n)/(1-q)

**完全二叉树**: (Complete binary tree)

完全二叉树就厉害了，之前提到满二叉树的目的就是为了引出完全二叉树. 满二叉树是完全二叉树的一种。

若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。

又有1个通俗定义： 当1棵层数为k满二叉树, 从它的**最底层的最右边**的节点开始,**连续向左**删除n个节点(2k >= n >= 0), 得到的树就是1棵完全二叉树.

如下图， 左边两个是完全二叉树， 而右边那个不是，**因为最下层的节点不是向右连续的啊！**

![444127020130504160915069.png][]

这里补充一点：完全二叉树是效率很高的数据结构，堆是一种完全二叉树，所以效率极高，像十分常用的排序算法、Dijkstra算法、Prim算法等都要用堆才能优化，几乎每次都要考到的二叉排序树的效率也要借助平衡性来提高，而平衡性基于完全二叉树。

这里为什么要特别提到完全二叉树呢？  因为完全二叉树是一种重要的数据结构， 跟栈，对列一样， 二叉树也可以用链式和数组内核来实现， 但是因为数组必须是连续存储的， 所以数组实现的二叉树必须是完全二叉树。

完全二叉树的性质：

1. 如果知道完全二叉树的节点个数， 就必然可以退出完全二叉树的形状（包括层数， 最后一层的节点排布）。  也就是说两个节点树相同的完全二叉树的形状是一样的。

2. 根据第1个性质， 只需要知道1个确定节点个数的完全二叉树的节点编号， 就可以推出这个节点的父节点和字节点！ 这个是1个非常重要的优点！

## 3. 树的存储(内存) ##

###           3.1 二叉树的存储： ###

**3.1.1. 连续存储** ：

上面提过了， 要利用连续存储(数组）来实现的二叉树必须是完全二叉树， 因为它们的节点必须是连续的啊！ 如果要利用连续存储来存储普通的二叉树， 就必须把这个二叉树转化为完全二叉树。

关键是如何转化？ 很简单， 就是添加必要的空节点把1个非完全二叉树补成1个完全二叉树， 如下图：

蓝色的树就是1个普通的2叉树，  白色的节点就是必要的不存放实际数据的节点， 添加上去组成1个完全二叉树， 就可以利用连续存储了。

至于要转成完全二叉树的原因：

假如只按一定的顺序只存储有效的节点，  内存物理上是1个线性结构， 如果把非线性的树存放在线性的内存中，存放后就变成线性结构了，例如上图中的蓝色树在内存里存放: A,B1,C1,C2,D3,D4  的确是能存放， 但是不能将存放的数据还原成原来的树啊！ 所以就必须添加一些无效的节点令它转化成1个完全二叉树！

缺点：

其实也可以看出， 如过利用连续存储来存放普通的二叉树， 首先需要一定量的连续内存空间，而且必然会造成1些空间浪费。 而且普通二叉树的层数越大， 耗费的内存越大！

优点：

就是上面完全二叉树的第2个性质，  只需要知道1个节点在数组的位置， 就可以推出它的父节点和子节点， 时间复杂度是0啊！

![444127020140512212720088.jpg][]

**3.1.2. 链式存储** ：

这个跟链表有点类似。

我们会把每1个节点分成4个域， 分别是数据域， 父节点指针域， 左子节点指针域， 右字节域指针域。（或者不包含父节点指针域，则只有3个域）

如下图：

![444127020140512212458033.png][]

可以见到，这种存储方式浪费的空间很少， 无非就是一些子节点的空指针， 但是这些空指针个数仍是线性增长的， 但是我们认为浪费的空间已经很少啦， 比起连续存储来讲， 因为链式存储不需存储多余的节点啊。

###       3.2 一般树的存储： ###

一般树的特点是节点的度（子节点个数）无限制， 用上面连续存储根本没可能， 如果用链式存储也很困难， 因为无法决定子节点的子节点指针域的个数啊！

####             3.2.1 双亲表示法(数组)： ####

双亲表示法实际上也是利用连续存储的， 只不过数组内的元素必须分为两个域， 1个是数据域， 另1个是父节点的**下标**（注意不是指针啊）. 根节点的父节点下标是·-1.

双亲表示法对于元素（节点）在数组内的顺序无要求。

如下图：

如上图右边的数组， 基本上可以把1棵树的结构表示出来了， 但是有个问题， 就是无法通过数组得到同1个父子点兄弟之间的顺序， 例如无法知道C1，C2,C3这个3兄弟在树中的顺序， 所以双亲表示法只适合表示无序的树。

优点：

几乎不浪费内存空间， 查找父节点很容易。

缺点：

不能表示有序的树， 查找子节点相对困难， 查找任何1个节点的子节点都必须遍历整个数组。 不能表示有序的树。

![44412702014051221311303.png][]

####            3.2.2 孩子表示法(数组)： ####

孩子表示法也是利用连续存储来实现的， 它的节点同样具有两个域， 1个是数据域， 另1个是1个子节点下标链表的头节点地址。

关键就是这个链表了， 链表的节点有两个域， 1个是int类型，用于表示节点下标， 另1个是指针。

如下图：

![444127020130504160709051.png][]

可以见到， 因为可以利用子节点下标链表的顺序来表示子节点兄弟的顺序， 所以这种表示法是能表示有序树的。

优点：

查找子节点算法很方便， 可以表示有序树

缺点：

查找父节点算法很困难， 必须遍历每1个节点的子节点下标链表， 如上图， 甚至判断哪个是根节点都需要遍历啊（O(n^2)）！

####         3.2.3 双亲孩子表示法(数组)： ####

由上面的例子可以看出， 其实双亲表示法和孩子表示法的优缺点是互补的， 所以把它们合拼在一起就是双亲孩子表示法了。

所谓双亲孩子法就是指表示树的数组内的节点有3个域， 数组域， 父节点下标域，及子节点下标链表域。

如下图：

![44412702013050416053106.png][]

优点：

具有双亲表示法和孩子表示法的所有优点， 关键是方便地查找父节点和子节点。

缺点：

占用相对更多的内存空间。

####        3.2.4 二叉树表示法 ： ####

这个的原理就是把一般树转化为二叉树， 然后再利用二叉树的存储方法来存储。

关键是如何把1个一般树转化为二叉树？  一句话：  **每个子节点的左子节点指向它原来的第1个子节点**， **右子节点指向它原来的下1个兄弟**。

所以这个方法又叫**孩子兄弟链表表示法**

如下图：

![444127020130504160026076.png][]

可以看到， 转换后层数增加了， 而且某个子树的度越大， 转化后所需的层数越多， 毕竟是利用层数来表示兄弟的个数啊。

而且有个特点， 就是转化后的二叉树， 对于根节点来讲， 是没有右字数的， 因为根节点没有兄弟嘛。

优点：

能使用一些二叉树的算法。

缺点：

查找真正的父节点和子节点的算法有点复杂，  例如上图转化后的二叉树， 如果求C3的父节点， 则必须反方向先求出C2和C1..

###          3.3 森林的存储： ###

所谓森林上面也提到过了， 就是互不相交(没有公共节点）的n棵树的集合。

例如下图中的三棵树就可以组成1个森林。

![444127020130504151943085.png][]

一般来讲，

首先： 我们会先把森林的所有树转化为二叉树（孩子兄弟链表表示法）

然后： 把转化后的二叉树合成1个新的二叉树， 怎么合成？ 就是把各个二叉树视为兄弟， 然后新增1个根节点作为它们的父子点。

其实不难理解的啦， 转化后如图：

![444127020130504155720078.png][]

然后就按照二叉树的方法存储就ok了。

[444127020140507235726070.png]: http://image16.poco.cn/mypoco/myphoto/20140507/23/444127020140507235726070.png
[444127020140508000133035.png]: http://image16.poco.cn/mypoco/myphoto/20140508/00/444127020140508000133035.png
[444127020130504160915069.png]: http://image142.poco.cn/mypoco/myphoto/20130504/16/444127020130504160915069.png
[444127020140512212720088.jpg]: http://image16.poco.cn/mypoco/myphoto/20140512/21/444127020140512212720088.jpg
[444127020140512212458033.png]: http://image16.poco.cn/mypoco/myphoto/20140512/21/444127020140512212458033.png
[44412702014051221311303.png]: http://image16.poco.cn/mypoco/myphoto/20140512/21/44412702014051221311303.png
[444127020130504160709051.png]: http://image142.poco.cn/mypoco/myphoto/20130504/16/444127020130504160709051.png
[44412702013050416053106.png]: http://image142.poco.cn/mypoco/myphoto/20130504/16/44412702013050416053106.png
[444127020130504160026076.png]: http://image142.poco.cn/mypoco/myphoto/20130504/16/444127020130504160026076.png
[444127020130504151943085.png]: http://image142.poco.cn/mypoco/myphoto/20130504/15/444127020130504151943085.png
[444127020130504155720078.png]: http://image142.poco.cn/mypoco/myphoto/20130504/15/444127020130504155720078.png