Welcome

0%

数据结构--树

发表于 分类于

树的定义

树（Tree）是 n（n >= 0）个结点的有限集，n = 0 时称为空树。

在任意一棵非空树中：

  • 有且仅有一个特定的根节点（Root），不可能存在多个根结点。

  • 当 n > 1 时，其余结点可以分为 m（m > 0）个互不相交的有限集 T1、T2、······、Tm，其中每一个集合本身又是一个树，并且称为根的子树（SubTree），如下图所示。

树的定义

  • 当 m>0 时，子树的个数没有限制，但它们一定是互不相交的。

结点分类

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

结点分类

结点间关系

结点的子树的根称为该结点的孩子（Child），相应地，该结点称为孩子的双亲（Parent）。同一个双亲的孩子之间互称兄弟（Sibling）。结点的祖先是从根到该结点所经分支上的所有结点。所以对于 H 来说，D，B，A 都是它的祖先。反之，以某结点为根的子树中的任一结点都称为该结点的子孙。所以 B 的子孙有 D，G，H，I。

结点层次

树的其他相关概念

  • 结点的层次（Level）从根开始定义起，根为第一层，根的孩子为第二层。双亲在同一层的结点互为堂兄弟。显然上图中的 D，E，F 是堂兄弟，而 G，H，I，J 也是。树中结点的最大层次称为树的深度（Depth）或高度，当前树的深度为 4。
  • 如果将树中结点的各子树看成从左至右是有次序的，不能互换的，则称该树为有序树，否则称为无序树。
  • 森林（Forest）是 m（m >= 0）棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。

树的存储结构

双亲表示法

假设以一组连续空间存储树的结点，同时在每个结点中，附设一个指示器指示其双亲结点到链表中的位置。其中 data 是数据域，存储结点的数据信息。而 parent 是指针域，存储该结点的双亲在数组中的下标。

| data | parent |

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/* 树的双亲表示法结构定义 */
#define MAX_TREE_SIZE 100
typedef int TElemType;        /* 树结点的数据类型，暂定为整型 */

struct PTNode        /* 结点结构 */
{
    TElemType data;    /* 结点数据 */
    int parent;        /* 双亲位置 */
};
struct PTree         /* 树结构 */
{
    PTNode nodes[MAX_TREE_SIZE];    /* 结点数组 */
    int r, n;        /* 根的位置和结点数 */
}

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

下标 data parent
0 A -1
1 B 0
2 C 0
3 D 1
4 E 2
5 F 2
6 G 3
7 H 3
8 I 3
9 J 4

我们可以根据结点的 parent 指针很容易找到它的双亲结点，所用的时间复杂度为O(1)，直到 parent 为 -1 时，表示找到了树结点的根。这样的存储结构有一个问题就是要遍历整个结构才能找到结点的孩子。

改进方法：

增加一个结点最左边孩子的域（长子域），这样就可以很容易找到结点的孩子。如果没有孩子的结点，这个长子域就设置为 -1，如下表所示。

下标 data parent firstchild
0 A -1 1
1 B 0 3
2 C 0 4
3 D 1 6
4 E 2 9
5 F 2 -1
6 G 3 -1
7 H 3 -1
8 I 3 -1
9 J 4 -1

对于有 0 个或 1 个孩子结点来说，这样的结构是解决了要找结点孩子的问题了。但如果结点的孩子很多，超过了 2 个。我们又关注结点的双亲、又关注结点的孩子、还关注结点的兄弟，而且对时间遍历要求还比较高，那么我们还可以把此结构扩展为有双亲域、长子域、再有右兄弟域。

由以上分析过程可以看出，存储结构的设计是一个非常灵活的过程。一个存储结构设计得是否合理，取决于基于该存储结构的运箅是否适合、是否方便，时间复杂度好不好等。

孩子表示法

由于树中每个结点可能有多棵子树，可以考虑用多重链表，即每个结点有多个指针域，其中毎个指针指向一棵子树的根结点，我们把这种方法叫做多重链表表示法。由于每个结点的度（结点孩子个数）不同，所以有两种方案：

1. 指针域的个数就等于树的度

| data | child1 | child2 | child3 | ······ | childd |

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

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

2. 每个结点指针域的个数等于该结点的度

专门取一个位置来存储结点指针域的个数：

| data | degree | child1 | child2 | child3 | ······ | childd |

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

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

更好的方法：

把每个结点放到一个顺序存储结构的数组中，再对每个结点的孩子建立一个单链表体现它们的关系。

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

树的孩子表示法

上图中有两种结点结构，一个是表头数组的表头结点：| data | firstchild |

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

另一个是孩子链表的孩子结点：| child | next |

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/* 树的孩子表示法结构定义 */
#define MAX_TREE_SIZE 100

struct CTNode        /* 孩子结点 */
{
    int child;
    struct CTNode *next;
};
CTNode *ChildPtr;
struct CTBox         /* 表头结构 */
{
    TElemType data;
    ChildPtr firstchild;
};
struct CTree         /* 树结构 */
{
    CTBox nodes[MAX_TREE_SIZE];        /* 结点数组 */
    int r, n;        /* 根的位置和结点数 */
}

这样的结构对于我们要查找某个结点的某个孩子，或者找某个结点的兄弟，只需要查找这个结点的孩子单链表即可。对于遍历整棵树也是很方便的，对头结点的数组循环即可。

如果想要知道某个结点的双亲是谁，只需在表头结构中加入双亲位置指针域，存储该结点的双亲在数组中的下标即可（| data | parent | firstchild |），这种方法被称为双亲孩子表示法。

孩子兄弟表示法

从树结点的兄弟的角度出发研究树的存储结构，我们可以发现，任意一棵树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。因此，我们设置两个指针，分别指向该结点的第一个孩子和此结点的右兄弟。

| data | firstchild | rightsib |

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

1
2
3
4
5
6
/* 树的孩子兄弟表示法结构定义 */
struct CSNode 
{
    TElemType data;
    struct CSNode *firstchild, *rightsib;
};

这个表示法的最大好处是它把一棵复杂的树变成了一棵二叉树。如下图所示。

树的孩子兄弟表示法

二叉树的内容将在之后介绍。