数据结构笔记——树的基本概念

树的定义

之前一直介绍的是一对一的线性结构，可现实中还有多一对多的情况需要处理，这就是今天要介绍的一对多的数据结构——树。

树（Tree）：是n（n>=0）个结点的有限集。n=0时称为空树。在任意一棵非空树中：

1. 有且仅有一个特定的称为根（Root）的结点；
2. 当n>1时，其余结点可分为m（m>0）个互不相交的有限集T₁、T₂、···、T_m，其中每一个集合本身又是一颗树，并且称为根的子树（SubTree），如图：

   

树的定义其实就是我们在说栈的时候提到的递归的方法。也就是在树的定义之中还用到了树的概念，这是一种比较新的定义方法。下图的子树T₁和子树T₂就是根结点A的子树。当然，D、G、H、I组成的树又是B为根结点的子树，E、J组成的树是以C为根结点的子树。

对于树的定义还需要强调两点：

1. n>0时根结点是唯一的，不可能存在多个根结点，别和现实中的大树混在一起，现实中的树有很多根须，那是真实的树，数据结构中的树只有一个根结点。
2. m>0时，子树的个数是没有限制的，但它们一定是互不相交的，像下图中的两个结构就不符合树的定义，因为它们有相交的子树：

1、结点的分类

树的结点包含一个数据元素，及若干指向其子树的分支。结点拥有的子树数称为结点的度。度为0的结点称为叶子结点或终端结点；度不为0的结点称为非终端结点或分支结点。除了根结点外，分支结点也叫内部结点。树的度是树内各结点的度的最大值。

2、结点间关系

**结点的子树的根称为该结点的孩子，相应地，该结点称为孩子的双亲。**同一个双亲的孩子之间互称兄弟。结点的祖先是从根到该结点所经分支上的所有结点。反之，以某结点为根的子树中任一结点都称为该结点的子孙。

3、树的其他概念

结点的层次从根开始定义起，根为第一层，根的孩子为第二层。若某结点在第l层，则其子树的根就在第l+1层。其双亲在同一层的结点互称为堂兄弟。树中结点的最大层次称为树的深度或高度。

如果将树中结点的各子树看成从左至右是有次序的，不能互换的，则称该树为有序树，否则称为无序树。

森林是m（m>=0）棵互不相交的树的集合。对树中的每个结点来说，其子树集合即为森林。

树的存储结构

一说到存储结构，就必须说到顺序存储和链式存储两种方式。

树中某个结点的孩子可以有多个，这就意味着，无论按何种顺序将树中所有结点存储到数组中，结点的存储位置都无法直接反映逻辑关系，所以简单的顺序存储结构不能满足树的实现要求。

今天介绍三种不同表示方法：双亲表示法、孩子表示法和孩子兄弟表示法。

1、双亲表示法

除了根结点外，其余每个结点，它不一定会有孩子，但一定有且仅有一个双亲。

我们假设以一组连续空间存储树的结点，同时在每个结点中，附设一个指示器指示其双亲结点在数组中的位置。也就是说每个结点除了知道自己是谁以外，还知道它的双亲是在哪里。

其中data是数据域，存储结点数据信息，而parent是指针域，存储该结点双亲在数组中的下标。

由于根结点是没有双亲的，所以我们约定根结点的位置域设置为-1，也就意味着，我们所有的结点都存有它的双亲。下面这个树可以这样表示：

这样的存储结构，可以根据结点的parent指针很容易找到它的双亲结点，所以时间复杂度是O(1)，直到parent为-1时，表示找到了树结点的根。可是如果要知道孩子结点是什么，对不起，需要遍历整个结构。

能不能改进一下呢？当然可以，我们增加一个结点最左边孩子的域，不妨叫他长子域，这样可以很容易找到它的孩子。如果没有孩子，长子域设置为-1：

这样我们找除了第一个孩子之外，找其他孩子就不太容易了。

另一个场景，如果我们很关注各兄弟之间的关系，双亲表示法无法体现这样的关系，我们可以增加一个右兄弟域来体现兄弟关系，也就是说，每一个结点，再保存一个它右兄弟的下标：

但是如果结点的孩子很多，超过了2个，我们既关注结点的双亲，又关注结点和孩子和兄弟，而且对遍历时间要求较高，那么就可以拓展此结构有双亲域，长子域和右兄弟域等。

存储结构的设计是一个非常灵活的过程。一个存储结构设计得是否合理，取决于基于该存储结构的运算是否合适、是否方便和时间复杂度等。

2、孩子表示法

换一种考虑方式。由于树中每个结点可能右多棵子树，可以考虑用多重链表，即每个结点有多个指针域，其中每个指针指向一个子树的根结点，我们叫之多重链表表示法。

不过，树的每个结点的度是不同的，所以限制有两个方案解决：

方案一

指针域的个数等于树的度：

其中data是数据域，child1到childd是指针域，用来指向该结点的孩子结点。

对于上面提到的树来说，树的度是3，所以我们的指针域个数是3，实现如下：

这种方法对于树中各结点的度相差很大时，显然是浪费空间的，因为很多的结点，它的指针域是空的。不过如果树的各结点度相差不大时，那就意味着开辟的空间被充分利用了。

方案二

这种方案时每个结点指针域的个数等于该结点的度，我们专用一个位置来存储结点指针域的个数：

其中data为数据域，degree为度域，也就是存储该结点的孩子的个数，child1到childd为指针域，指向结点的各个孩子的结点。如下：

这种方法虽然克服了浪费空间的缺点，对空间利用率是提高了，但是由于各个结点的链表是不同结构，加上需要维护结点的度的数值，再运算下会带来时间上的损耗。

接下来介绍下孩子表示法，具体办法是：把每个结点的孩子排列起来，以单链表作存储结构，则n个结点有n个孩子链表，如果是叶子结点则此单链表为空。然后n个头指针又组成一个线性表，采用顺序存储结构，存放进一个一维数组中，如图：

为此设计两种结点结构，一个是孩子链表的孩子结点：

其中child是数据域，用来存储某个结点在表头数组中的下标，next是指针域，用来存储指向某个结点的下一个孩子结点的指针。

另一个是表头数组的表头结点：

data是数据域，存储结点数据信息，firstChild是该结点的孩子链表的头指针。

3、孩子兄弟表示法

任意一棵树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。因此，我们设置两个指针，分别指向该结点的第一个孩子和此结点的右兄弟。

其中data是数据域，firstChild为指针域，存储该结点第一个孩子结点存储地址，rightsib是指针域，存放该结点右兄弟结点的存储位置：

这种表示法，给查找某个结点的某个孩子带来了方柏霓，只需要通过firstChild找到此结点的长子，在通过长子结点的rightsib找到它的二弟，接着一直下去，直到找到具体孩子。

其实这种方式最大好处就是将一个普通树转成了一棵二叉树，整理一下上面的图可以得到：

关于树的介绍，我们还将继续，获取更多精彩内容，关注我的微信公众号——Android机动车