大话数据结构7-树1

发表于 更新于 分类于 ， Valine：

I 定义

树是n个结点的有限集合，在任意一棵非空的树中，1- 有且仅有一个特定的 “根” （root）结点；2- 当 $n>1$ 时，其余结点可分为 $m (m>0)$ 个互不相交的有限集合，其中每个集合本身又是一棵树，并且称为根的子树(SubTree)。

可以看出，树的定义中使用了递归的方法（Fun: another interesting recursion example: “GNU is Not UNIX”），也即“树”是由“子树”构成的。需要注意的两点是：1- 根结点是唯一的；2- 子树的数量没有限制，但子树之间不能相交。

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

结点的子树的根 称为该结点的 孩子(child), 相应的，该结点称为 child 的 parent。同一个parent 结点的 child 之间互称 sibling。结点的祖先是从根到该结点所经分支上的所有结点。

此外，结点的 层次（Level） 从根开始定义，根为第一层，根的 child 是第二层。树中结点的最大层次称为树的 深度（Depth）。上述的定义可以通过下图直观的表达：

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

森林（Forest）是 $m(m \geq 0)$ 棵互不相交的树的集合。

II 树的存储结构

不同于线性表可以与线性存储结构自然的结合，树结构需要同时利用线性存储和链表存储的特点，来优化它的性能。

Parent 表示法

我们知道，对于树中的结点，除了根结点之外，任何一个结点都有 parent。因此，我们构造树的存储结点的结构 = data(数据域) + parent的地址(指针域)。具体的，我们可以看下面的定义代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
//树的 parent 表示法的定义
# define MAX_TREE_SIZE 100
typedef int TElemType;      //树结点的 数据的 数据类型

typedef struct PTNode{      //结点结构
    TElemType data;
    int parent;         //parent 的位置
}PTNode;

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

此外，对于特殊的根结点，我们将它的地址域设为 -1。但这种结构对于寻找结点的child很不方便。

Child 表示法

另一种思路，是将 child 的信息存放在结点信息中。但不同于 “除头结点外，每个结点都只有一个parent”，每个结点的child 的数量是非常不确定的。因此，我们可以通过链表的形式存储 child。也就是说，将一个结点的所有 child 以单链表的形式进行存储。

此外，我们还可以使用 child&sibling 表示法，也就是在一个结点中不仅存储孩子的信息，还将该结点的 right sibling 的地址也进行存储。这种方法非常适用于后面的二叉树结构。

III 二叉树

对于 “是” 或 “非” 的判断程序，相当于一个结点下面总是只有两个分支，因此，我们引入一种特殊的树状结构，二叉树：

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

二叉树有如下几个特点：

  1. 每个结点最多有两棵子树，即有0，1，2 棵子树都可以。所以，二叉树的 度 最大为2。
  2. 左子树和右子树是有顺序的。即使树中某结点只有一棵子树，我们也要区分它是左子树还是右子树。

一些特殊的树的结构

斜树，所有的结点都只有左子树的二叉树叫做左斜树，所有的结点都只有右子树的二叉树叫做右斜树。二者统称为斜树。（其实感觉就跟线性表一样… 所以说，线性表是树结构的一种极特殊形式）

满二叉树，所有的结点都存在左子树和右子树，并且所有的 叶结点 都在同一层上。

完全二叉树，对于一个 n 个结点的二叉树按照 层序编号，如果编号为 $i (1\leq i\leq n)$ 的结点与同样深度的满二叉树中编号为 i 的结点在二叉树中的位置完全相同，则这棵二叉树称为完全二叉树。 实际上是满二叉树去掉最后 k 个元素（从最后一层开始，从右往左去除）的树。

便于后续的分析，我们总结二叉树具有的一些 性质如下：

  1. 在二叉树的第 i 层上至多有 $2^{i-1}$ 个结点。（$i\geq 1$）
  2. 深度为 k 的二叉树至多有 $2^k - 1$ 个结点。
  3. 对任何一棵二叉树 $T$, 如果其终端结点数（叶子结点）为 $n_0$, 度为2的结点数为 $n_2$，则 $n_0 = n_2 + 1$。
  4. 具有 n 个结点的完全二叉树的深度为 $[log_2n]+1$。（[x] 表示不大于x的最大整数）
  5. 如果对一棵有$n$个结点的完全二叉树的结点按照层序编号（从第一层到第$[log_2n]+1$层，每层从左到右），对任一结点 i 有：
    1. 如果 $i = 1$,则结点i 是二叉树的根，无 parent；如果 $i>1$，则其parent 的结点是 $[i/2]$.
    2. 如果 $2i>n$, 则结点无左孩子（即结点 $i$ 为叶子结点）,否则其左孩子是结点 $2i$.
    3. 如果 $2i+1>n$,则结点 i 无 right child，否则它的 right child 为结点 $2i+1$.

Remark: 性质3可以从分支线的角度进行推导，我们知道，二叉树系统中结点的度总共只有3种可能, 分别记有0个，1个，2个子结点的结点个数为 $n_0,n_1,n_2$，因此，我们有 总结点数 $n$， $n = n_1 + n_2 + n_3$。从连接线的角度，我们可以发现，除根结点外，每个结点与parent 之间有一根连接线，所以线的总数 $l$ 有：$l = n-1$。我们又知道，连接线与结点的子节点数有关，$l$ 又可以表示为：$l = n_1 + n_2 *2$, 因此，最终我们有：$n_1+n_2 * 2 + 1 = n_1+ n_2+n_0$ , 即 $n_2+1 = n_0$ .

IV 二叉树的存储结构

首先，由于二叉树的度最大为2，它占用的空间大小是相对确定的，因此我们可以用数组（顺序存储结构）的形式来存储二叉树。

思想是利用之前所讲的 满二叉树的层序编号 作为数组下标，来定位树中的元素。当对应的元素不存在时，给数组中元素赋值为空。可以发现，完全二叉树适合存储在这种结构中，但结点的child 结点为1的情况较多的二叉树（例如：斜二叉树），使用数组存储就非常的浪费空间。

由于顺序存储的局限性，我们因此更加推荐使用链式结构来储存。根据二叉树的特性，我们为存储它的链中的结点设计如下形式：

$$lchild + data + rchild$$

也就是具有一个数据域和两个指针域，两个指针域中分别存储指向结点 left child 和 right child 的指针。我们也称这样的链表为 二叉链表。

V 遍历二叉树

二叉树的遍历 （traversing binary tree）是指从根结点出发，按照某种 次序 依次访问 二叉树中的所有结点，使得每个结点被访问一次且仅被访问一次。

二叉树的遍历方法主要可以分为4种：

  1. 前序遍历：从根结点开始，先遍历左子树，再遍历右子树。
  2. 中序遍历：先遍历根结点的左子树，再访问根结点，最后中序遍历右子树。
  3. 后序遍历：从左到右以先叶子后结点的方式遍历访问左右子树，最后访问根结点。
  4. 层序遍历：从树的第一层（根结点）开始，从上向下逐层遍历，同一层中，从左到右遍历。

由于二叉树是使用递归进行定义，所以在遍历算法中也可以采用递归方法，可以使得代码更加简洁。

具体的，我们可以参考如下的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
//前序遍历递归算法
void PreOrderTraverse(BiTree T){
    if(T == NULL)   
        return;
    printf("%C", T->data);      //显示结点数据
    PreOrderTraverse(T->lchild);       //先遍历左子树
    PreOrderTraverse(T->rchild);       //遍历右子树
}

//中序遍历递归算法
void InOrderTraverse(BiTree T){
    if(T == NULL)
            return;
    InOrderTraverse(T->lchild);    //中序遍历，左子树
    printf("%c",T->data);       //显示结点数据
    InOrderTraverse(T->rchild);     //中序遍历右子树
    }
}

//后序遍历递归算法
void PostOrderTraverse(BiTree T){
    if(T == NULL)
        return;
    PostOrderTraverse(T->lchild);   //后序遍历左子树
    PostOrderTraverse(T->rchild);   //后序遍历右子树
    printf("%c",T->data); 
}

根据上面的分析，我们可以总结：

  • 前序的顺序是：根结点-》左子树-》右子树。（也就是只有一个根结点的本身和它的所有的右子树结点结束后，才会跳去左子树，这时候，左子树又是一个单独的树，重复上面的逻辑）
  • 中序的顺序是：左子树-》根结点-》右子树。（也就是说，只有把一个结点的左子树部分遍历完才会执行根结点）
  • 后序的顺序是：左子树-》右子树-》根结点。

其实，上面所说的这些顺序也很好理解，首先需要建立一个前提，就是所有的遍历，实际上都是从根结点开始的（但不一定最先执行根结点）。例如 前序遍历法，在程序中，它是将执行操作放在最前面，然后是递归左子树再是右子树，所以是先执行根结点，然后是左子树-》右子树。中序遍历将执行放在左子树递归和右子树递归的中间，因此，是先执行左子树的内容，然后是根结点再最后右子树。

最后，是一个关于二叉树遍历的 性质：已知前序遍历序列 和 中序遍历序列 或者 已知 后序遍历序列 和 中序遍历序列，可以唯一确定一棵二叉树；但是已知前序遍历序列和后序遍历序列是无法确定一棵二叉树的。

VI 二叉树的建立

为了生成一棵二叉树，我们首先是将一棵 general 的二叉树扩展成一个完全二叉树。然后，二叉树的生成就与上面遍历过程非常类似了，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//输入前序遍历序列，构造二叉树T
void CreateBiTree(BiTree *T){
    TElemType ch;
    scanf("%c",&ch);    //键盘输入二叉树的值，每个值为一个字符
    if(ch == '#')       //在将二叉树补充成完全二叉树时，用`#`补充空位
        *T = NULL;
    else{
        *T = (BiTree)malloc(sizeof(BiTNode));
        if(!*T)
            exit(OVERFLOW);
        (*T)->data = ch;    //生成根结点
        CreateBiTree(&(*T)->lchild);    //构造左子树
        CreateBiTree(&(*T)->lchild);    //构造右子树
    }
}

用中序和后序遍历输入的字符要做相应的更改，此外在生成树的代码中也要相应的调整生成结点和构造左右子树的代码顺序。