UCAS CTF

数据结构入门：树

Author: doyo

基本概念

树（tree） 是一种非常重要的数据结构。与前面介绍的几种数据结构不同，树是非线性的，也就是说，树中的每个元素都可以链接多个元素。

树的严格定义如下：

树是n个结点的有限集，满足：

有且仅有一个结点没有前驱结点（父结点，father或parent），它称之为这棵树的根（root）。

除根外，其它每个结点有且仅有一个父结点（这也说明，有n个结点的树有且仅有n-1条边）。

除根外，其它每个结点有且仅有一条路径与根相连；这条路径从根开始，到它结束，并且路径上每个结点都是前一个结点的后继（子结点，son或child）。

容易发现，树中不会出现封闭的回路，并且有n个结点的树总是具有n-1条边。

二叉树

二叉树是一种非常特殊的树。二叉树中的每个结点最多仅有两个子结点（分别称为左子结点和右子结点），即二叉树是度不大于2的树。

二叉树的基本形态

二叉树有五种基本形态：

空二叉树
只有一个结点的二叉树
只有左子树的二叉树
只有右子树的二叉树
左右子树都有的二叉树

例如，在下面这棵二叉树中，包含了除空二叉树以外的其它五种形态，你能发现吗？

二叉树的性质

二叉树有许多优美的性质。下面的讨论中，我们默认以根为第1层。

性质1： 二叉树的第 $i$ 层最多有 $2^{i-1}$ 个结点。
性质2： 深度为$k$的二叉树最少有$k$个结点，最多有$2^k-1$个结点。
性质3： 有$n_0$个叶结点的二叉树，其度为$2$的非叶结点有$n_0-1$个。

几种特殊的二叉树

满二叉树（Perfect Binary Tree）： 深度为 $k（k \geqslant 1）$ 、具有 $2^k-1$ 个结点的二叉树。
完全二叉树（Complete Binary Tree）： 从根结点到倒数第二层满足满二叉树的条件，最后一层可以不完全填充，但叶结点都靠左对齐。具有n个结点的完全二叉树深度为 $\lfloor \log_2n \rfloor$ .
严二叉树（Full/Proper/Strictly Binary Tree）： 所有非叶结点度均为 $2$。

二叉树的存储

我们可以用类似于链表的方式来存储二叉树：

typedef int ElemType;
struct node {
    int id;                     // 这个结点的id，这个数据不是必须的，此处加上id是为了方便理解
    ElemType data;              // 这个元素所保存的数据
    struct node *lc, *rc;       // 左右子结点指针，分别指向这个节点的左右子结点
};

我们可以发现这一结构与链表的结构高度类似，唯一的区别在于指针变成了两个，因为每个结点需要两个不同的指针来分别指向它的左右子结点。

同样的，我们也需要一个指针来指向二叉树的根：

struct node *root;              // 根结点指针

二叉树的建立

建立一棵二叉树至少需要知道以下信息：

二叉树的根结点在哪里？
每个二叉树结点的左右子结点是什么？

一般情况下，为了叙述方便，我们会为每个结点分配一个从1开始的id，一般以1号结点作为根结点。

构建二叉树的方式与创建链表的方式非常类似，只需注意插入的左右子结点即可。

下面的代码展示了构建二叉树的过程。我们假设每个结点的左右子结点id已被存储在了lchid和rchild这两个数组中。

struct node *build(int id) {
    if (!id) {                      // 按照约定，id为0时代表空结点
        return NULL;
    }
    struct node *now = NewSpace;    // 构建当前结点
    now->id = id;
    now->lc = build(lchild[id]);    // 递归构建左子树
    now->rc = build(rchild[id]);    // 递归构建右子树
}

二叉树的遍历

二叉树的遍历是指顺着某条搜索路径访问二叉树中的每个结点，使得每个结点恰好被访问一次。这里的“访问”与我们之前介绍的链表的“访问”稍有不同，此处是指对该结点进行的某种操作，比如输出其存储的数据或者修改其中的数据等等。

对于链表等线性的数据结构，讨论遍历是没有意义的。因为它们最多只有一个后继，沿着next指针一直向后跳即可，换言之，它们只有一条搜索路径。

依照结点遍历顺序的不同，二叉树的遍历可以分为三种：

先序遍历
中序遍历
后序遍历

先序遍历(Preorder Traversal)

也叫先根序，即按照“子树根结点-左子树-右子树”的顺序遍历，可以简记为“根-左-右”。

例如考虑前文图中的那棵二叉树，它的先序遍历经过的节点次序就是：1 2 4 7 3 5 6 8

代码如下：

void preorder(struct node *now) {   
    if (now == NULL) {              // 走到空结点，直接返回
        return;
    }
    printf("%d ", now->id);         // 访问当前结点
    preorder(now->lc);              // 递归访问左子树
    preorder(now->rc);              // 递归访问右子树
}

不难发现，按前文所述方法构建二叉树的过程其实也是一种先序遍历。

中序遍历（Inorder Traversal）

也叫中根序，即按照“左子树-子树根结点-右子树”的顺序遍历，可以简记为“左-根-右”。

例如考虑前文图中的那棵二叉树，它的中序遍历经过的节点次序就是：4 7 2 1 5 3 8 6

代码如下：

void inorder(struct node *now) {
    if (now == NULL) {              // 走到空结点，直接返回
        return;
    }
    inorder(now->lc);              // 递归访问左子树         
    printf("%d ", now->id);        // 访问当前结点
    inorder(now->rc);              // 递归访问右子树
}

后序遍历（Postorder Traversal）

也叫后根序，即按照“左子树-右子树-子树根结点”的顺序遍历，可以简记为“左-右-根”。

例如考虑前文图中的那棵二叉树，它的中序遍历经过的节点次序就是：7 4 2 5 8 6 3 1

代码如下：

void postorder(struct node *now) {
    if (now == NULL) {              // 走到空结点，直接返回
        return;
    }
    postorder(now->lc);             // 递归访问左子树
    postorder(now->rc);             // 递归访问右子树
    printf("%d ", now->id);         // 访问当前结点
}

扩展到一般的树

对于一般的树，也能进行遍历。但是显然，只能做先序遍历和后序遍历，而不能做中序遍历，因为对于此时每个结点不再只有两个子树，讨论“中”是没有意义的。

代码示例

你可以在我们的wiki中下载tree.c（点击此处下载），该程序接受一棵二叉树的输入，将其构建之后输出三种遍历的顺序。

接收的输入格式为：

第一行一个整数n，表示二叉树中结点的个数。

接下来n行，每行两个整数，分别表示第i个结点的左右子结点id，0表示不存在。

例如，你可以用下列输入来表示前文图中的那棵二叉树：

它对应的输出将是：

Preorder Traversal:
1 2 4 7 3 5 6 8
Inorder Traversal:
4 7 2 1 5 3 8 6
Postorder Traversal:
7 4 2 5 8 6 3 1

UCAS CTF

数据结构入门：树

基本概念

相关术语

二叉树

二叉树的基本形态

二叉树的性质

几种特殊的二叉树

二叉树的存储

二叉树的建立

二叉树的遍历

先序遍历(Preorder Traversal)

中序遍历（Inorder Traversal）

后序遍历（Postorder Traversal）

扩展到一般的树

代码示例