树

数据结构 › C
,
·本篇:3.6k字 大约需要: 13分钟

前言

树的实现及相关操作

编程语言：C

树

树的定义

树（Tree）是n（n ≥ 0）个结点的有限集

n = 0时称为空树

在任意一棵非空树中：

  • 有且仅有一个特定的称为根（Root）的结点
  • 当n > 1时，其余结点可分为m（m > 0）个互不相交的有限集T1、T2、……、Tm，其中每一个集合本身又是一棵树，并且称为根的子树（SubTree）

结点分类

结点拥有的子树数称为结点的度（Degree）

度为0的结点称为叶节点（Leaf）或终端结点；度不为0的结点称为非终端结点或分支结点

除根节点之外，分支结点也称为内部节点

树的度是树内各结点的度的最大值

结点间的关系

结点的子树的根称为该结点的孩子（Child），相应的，该结点称为孩子的双亲（Parent）

同一个双亲的孩子之间互称兄弟（Sibling）

结点的祖先是从根到该结点所经分支上的所有结点，反之，以某结点为根的子树中的任一结点都称为该结点的子孙

树的其他相关概念

结点的层次（Level）是从根开始定义起，根为第一层，根的孩子为第二层

双亲在同一层的结点互为堂兄弟

树中结点的最大层次称为树的深度（Depth）或高度

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

森林（Forest）是m（m ≥ 0）棵互不相交的树的结合

树的抽象数据类型

树的存储结构

双亲表示法

假设以一组连续空间存储树的结点，同时在每个结点中，附设一个指示器指示其双亲结点在数组中的位置

结构代码

1
2
3
4
5
6
7
8
9
10
11
12
#define MAXSIZE 100
typedef struct PTNode // 结点结构
{
    int data; // 结点数据，可以为任意数据类型
    int parent; // 双亲位置
} PTNode;

typedef struct // 树结构
{
    PTNode nodes[MAXSIZE];
    int r, n; // 根的位置和结点数
} PTree;

由于根结点是没有双亲的，所以我们约定根结点的位置域设置为-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个孩子结点来说，这样的结构是解决了要找结点孩子的问题，甚至是有两个孩子，知道了长子是谁，另一个当然就是次子了
  • 但是双亲表示法无法体现出兄弟之间的关系，可以增加一个右兄弟域来体现兄弟关系，每一个结点如果它存在右兄弟，则记录下右兄弟的下标，如果右兄弟不存在，则赋值为-1，如下表所示
下标 data parent rightsib
0 A -1 -1
1 B 0 2
2 C 0 -1
3 D 1 -1
4 E 2 5
5 F 2 -1
6 G 3 7
7 H 3 8
8 I 3 -1
9 J 4 -1
  • 但如果结点的孩子很多，超过了2个。我们又关注结点的双亲，又关注结点的孩子，还关注结点的兄弟，而且对时间的遍历要求还比较高，那么可以把此结构扩展为有双亲域、长子域、再有右兄弟域

孩子表示法

每个结点有多个指针域，其中每个指针指向一棵子树的根结点，把这种方法叫做多重链表表示法

不过，树的每个结点的度，也就是它的孩子个数是不同的，所以可以设计两种方案来解决

方案一

指针域的个数等于树的度

树的度是树各个结点度的最大值

其结构如下表所示

data child1 child2 child3 ...... childn
  • 其中data是数据域，child1到childn是指针域，用来指向该结点的孩子结点

对于图一的树来说，树的度是3，所以我们的指针域的个数是3，如下图所示


图二

从图中可以看到，这种方法对于树中各结点的度相差很大时，显然是很浪费空间的，因为有很多结点的指针域都是空的

方案二

第二种方案每个结点指针域个数等于该结点的度，专门取一个位置来存储结点指针域的个数，其结构如下表所示

data degree child1 child2 child3 ...... childn
  • 其中data为数据域，degree为度域，即存储该结点的孩子结点的个数，child1到childn为指针域，指向该结点的各个孩子的结点

对于图二的树，用方案二实现如下图


图三

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

仔细观察，我们为了要遍历整棵树，把每个结点放到一个顺序存储结构的数组中是合理的，但每个结点的孩子有多少是不确定的，所以我们再对每个结点的孩子建立一个单链表体现它们的关系

孩子表示法

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


图四

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

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

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

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

结构代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#define MAXTREESIZE 100
typedef struct CTNode // 孩子结点
{
    int child;
    struct CTNode *next;
} CTNode, *ChildPtr;

typedef struct // 表头结构
{
    int data; // 可以为任意数据类型
    ChildPtr FirstChild;
} CTBox;

typedef struct 
{
    CTBox nodes[MAXTREESIZE]; // 结点数组
    int r, n; // 根的位置和结点数
} CTree;

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

但是，我如何知道某个结点的双亲是谁呢？需要将整棵树遍历才行

所以将双亲表示法和孩子表示法综合一下

双亲孩子表示法

只需要在孩子表示法的表头结点中加入双亲结点的下标即可，根结点的下标设为-1


图五

结构代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#define MAXTREESIZE 100
typedef struct CTNode // 孩子结点
{
    int child;
    struct CTNode *next;
} CTNode, *ChildPtr;

typedef struct // 表头结构
{
    int data; // 可以为任意数据类型
    int Parent; // 双亲结点的下标
    ChildPtr FirstChild;
} CTBox;

typedef struct
{
    CTBox nodes[MAXTREESIZE]; // 结点数组
    int r, n; // 根的位置和结点数
} CTree;

孩子兄弟表示法

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

结点结构如下表所示

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

结构代码

1
2
3
4
5
typedef struct CSNode
{
    int data; // 可以为任意数据类型
    struct CSNode *FirstChild, *RightSib;
} CSNode, *CSTree;

对于图一的树，用该方法实现如下图


图六

  • 这种表示法，给查找某个结点的孩子带来了方便，只需要通过firstchild找到此结点的长子，然后再通过长子结点的rightsib找到它的二弟，接着一直下去，直到找到具体的孩子

  • 如果有必要可以再增加一个parent指针域来解决快速查找双亲的问题

  • 这个表示法的最大好处就是把一棵复杂的树变成了一棵二叉树

将图六变变形，如下图


图七
  • 这样就可以充分利用二叉树的特性和算法来处理这棵树了

总结

没有哪一种结构可以解决所有的问题，在具体的问题中我们应该针对问题来设计结构

存储结构的设计是一个非常灵活的过程

一个存储结构设计得是否合理，取决于基于该存储结构的运算是否合适、是否方便、时间复杂度好不好等

二叉树

二叉树的定义

二叉树（Binary Tree）是n（n ≥ 0）个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成


图八

二叉树特点

  • 每个结点最多有两棵子树，所以二叉树中不存在度大于2的结点
  • 左子树和右子树是有顺序的，次序不能任意颠倒
  • 即使树中某结点只有一棵子树，也要区分它是左子树还是右子树

二叉树具有五种基本形态

  • 空二叉树
  • 只有一个根结点
  • 根结点只有左子树
  • 根结点只有右子树
  • 根结点既有左子树又有右子树

特殊二叉树

1.斜树

所有结点都是只有左子树的二叉树叫左斜树，所有结点都是只有右子树的二叉树叫右斜树，这两者统称为斜树

斜树的每一层都只有一个结点，结点的个数与二叉树的深度相同

线性表结构就可以理解为是斜树的一种极其特殊的表现形式

2.满二叉树

在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树

满二叉树的特点

  • 叶子只能出现在最下一层
  • 非叶子结点的度一定是2
  • 在同样深度的二叉树中，满二叉树的节点个数最多，叶子树最多

3.完全二叉树

对一棵具有n个结点的二叉树按层序编号，如果编号为i（1 ⩽ i ⩽ n ）的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树

满二叉树一定是一棵完全二叉树，但完全二叉树不一定是满的

完全二叉树的特点

  • 叶子结点只能出现在最下两层
  • 最下层的叶子一定集中在左部连续位置
  • 倒数二层，若有叶子结点，一定都在右部连续位置
  • 如果结点度为1，则该结点只有左孩子，即不存在只有右子树的情况
  • 同样结点数的二叉树，完全二叉树的深度最小

二叉树的性质

  • 在二叉树的第i层上至多有2^i-1^个结点（i ≥ 1）
  • 深度为k的二叉树至多有2^k^-1个结点（k ≥ 1）
  • 对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1
  • 具有n个结点的完全二叉树的深度为$\lfloor log2n\rfloor$+1（$\lfloor x\rfloor$表示不大于x的最大整数）
  • 如果对一棵有n个结点的完全二叉树（其深度为$\lfloor log2n\rfloor$+1）的结点按层序编号（从第1层到第$\lfloor log2n\rfloor$+1层，每层从左到右），对任一结点i（1 ≤ i ≤ n）有：
    • 如果i = 1，则结点i是二叉树的根，无双亲；如果i ＞ 1，则其双亲是结点$\lfloor $$\frac{i}{2}$$\rfloor$
    • 如果2i ＞ n，则结点i无左孩子（结点i为叶子结点）；否则其左孩子是结点2i
    • 如果2i + 1 ＞ n，则结点i无右孩子；否则其右孩子是结点2i + 1

二叉树的存储结构

顺序存储适用性不强，所以只考虑链式存储结构

二叉链表

二叉树每个结点最多有两个孩子，所以为它设计一个数据域和两个指针域

这样的链表叫作二叉链表

lchild data rchild

其中data是数据域，lchild和rchild都是指针域，分别存放左孩子和右孩子的指针

结构代码

1
2
3
4
5
typedef struct BiTNode
{
    int data; // 可以为任意类型 
    struct BiTNode *l, *r;
} BiTNode, *BiTree;

二叉树的建立