1、树形结构

1.1、二叉树和多叉树

二叉树：指各节点的分叉数均不超过2的树。
多叉树：指存在节点的分叉数超过2的树。

注：使用树形结构可以大大提高数据（或文件）增、删、改、查的效率。

1.2、树形结构的应用

如：

公司组织架构
文件夹组织架构

2、树（Tree）的基本概念

2.1、节点（node）

节点：指树的每一个数据元素。

2.1.1、根节点

根节点是树中唯一没有入边的节点。

2.1.2、父节点

一个节点是它出边所连接的所有节点的父节点。

2.1.3、子节点

一个节点是它入边所连接的节点的子节点。

2.1.4、叶子节点

没有子节点的节点称为叶子节点。

2.1.5、兄弟节点

具有相同父节点的节点互为兄弟节点。

如：上述多叉树中，21与22互为兄弟节点，21与31并不是兄弟节点。

注：

一棵树可以没有任何节点，称为“空树”。
一棵树最多只有一个根节点。
一棵树可以只有1个节点，即：只有根节点。

2.2、边（edge）

边：指连接两个节点的有向线段。

2.2.1、入边

入边：指从其它节点指向该节点的边。

2.2.2、出边

出边：指从该节点指向其它节点的边。

2.3、路径

路径：指由边连接起来的节点的有序排列。

2.4、空树

空树：指没有任何节点的树。

2.5、子树

一个节点的某个子节点的所有边和后代节点所构成的集合，称为该节点的子树。

2.5.1、左子树

二叉树指每个节点最多只能有两个子树的有序树。通常二叉树上某节点的左边子树称之为左子树。

2.5.2、右子树

二叉树上某节点的右边子树称之为右子树。

2.6、度（degree）

2.6.1、节点的度

节点的度：该节点子树的个数。

叶子节点：度为0的节点。
非叶子节点：度不为0的节点。

（二叉树：梅开二度）

2.6.2、树的度

树的度：所有节点的度中的最大值。

2.7、层数（level）

层数：从根节点到该节点的路径中的边的数目（+1）。

我们定义根节点为树的第一层，根节点的子节点为树的第二层，以此类推。

注：有的教材也从第0层开始计算，我们这里从第一层开始计算。

2.8、深度（depth）和高度（height）

2.8.1、节点的深度和高度

节点的深度：从根节点到当前节点的唯一路径上的节点总数。
节点的高度：从当前节点到最远叶子节点的路径上的节点总数。

注：高度和深度计算的是节点数不是边数。

2.8.2、树的深度和高度

树的深度：所有节点深度中的最大值。
树的高度：所有节点高度中的最大值。

注：树的深度 = 树的高度。

2.9、有序树和无序树

2.9.1、有序树

有序树：树中任意节点的子节点之间有顺序关系。

注：

交换有序树中节点的位置，得到的是完全不同的两棵树。
我们后面使用的树，默认都是有序树。

2.9.2、无序树

无序树：树中任意节点的子节点之间没有顺序关系。

3、二叉树（Binary Tree）

3.1、二叉树的定义

二叉树：是指树中节点的度不大于2的有序树。

二叉树各节点的度均不超过2。（最多拥有2棵子树）
二叉树是有序树，其左子树和右子树是有顺序的，两者是不能任意交换顺序的。

注：即使某节点只有一棵子树，也要区分左右子树，不能任意交换顺序。

3.2、二叉树的性质

非空二叉树的第i层，最多有$2^{i-1}$个节点（i >= 1)。
在高度为h的二叉树上最多有$2^{h-1}$个节点（h >= 1)。

注：$2^0+2^1+…+2^{h-1}=2^h-1$ 。

对于任何一棵非空二叉树，如果叶子节点个数为$n_{0}$，度为2的节点个数为$n_{2}$，则$n_{0}=n_{2}+1$。

证：假设度为1的节点个数为$n_{1}$，那么二叉树的节点总数$n=n_{0}+n_{1}+n_{2}$。

$\because$ ①度为2的节点的边数为2、度为1的节点的边数为1、叶子节点的边数为0；

②除根节点以外所有节点的顶部都有且只有一条边。

$\therefore$ 二叉树的边数$E=n_{1}+2n_{2}=n-1=n_{0}+n_{1}+n_{2}-1$，即$n_{0}=n_{2}+1$。

注：

度为2的节点的出边边数为2、度为1的节点的出边边数为1、叶子节点的出边边数为0。
除根节点以外的所有节点的顶部都有且只有一条入边。

4、真二叉树（Proper Binary Tree）

真二叉树：所有节点的度均不为1的二叉树。（即：所有节点的度要么为0，要么为2。）

注：真二叉树是真“2”的二叉树。

5、满二叉树（Full Binary Tree）

5.1、概念

满二叉树：每一层的节点数都达到饱和状态的二叉树。

注：所有节点的度都要么为0，要么为2，且所有的叶子节点都在最后一层。

5.2、性质

在同样高度的二叉树中，满二叉树的叶子节点数量最多、总节点数量最多。
满二叉树一定是真二叉树，真二叉树不一定是满二叉树。
若满二叉树的高度为h（h >= 1），则其第i层的节点数量为$2^{i-1}$，叶子节点数量为$2^{h-1}$，总节点数量$n=2^{0}+2^{1}+…+2^{h-1}=2^{h}-1$。
若满二叉树的总节点数量为n，则该满二叉树的高度$h=\log_{2}(n+1)$ 。

6、完全二叉树（Complete Binary Tree）

6.1、概念

完全二叉树：将满二叉树的最后一层从右往左依次删除若干个节点得到的二叉树。

6.2、性质

叶子节点只会出现在最后两层，且最后一层的叶子节点都靠左对齐。
完全二叉树从第一层（根节点）至倒数第二层是一颗满二叉树。
满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。
度为1的节点只有左子树。
度为1的节点数量$n_{1}$要么是1个，要么是0个。
同样节点数量的二叉树，完全二叉树的高度最小。
若完全二叉树的高度为h，则它：
- 至少有$2^{h-1}$个节点（$2^{0}+2^{1}+…+2^{h-2}+1$）。
- 最多有$2^{h}-1$个节点（$2^{0}+2^{1}+…+2^{h-1}$，满二叉树）。
- 总节点数量n满足：$2^{h-1}\le n \lt 2^h$，即：$h-1\le \log_2{n} \lt h $ 。
若完全二叉树的总节点数量为n，则该完成二叉树的高度$h=floor(\log_2{n})+1$ ，其中$floor()$为向下取整函数。
若完全二叉树的总节点数量为n，则该完成二叉树的：
- 叶子节点个数$n_0=floor(\frac{n+1}{2})=ceiling(\frac n 2)$ ，
- 非叶子节点个数$n_1+n_2=floor(\frac n 2)=ceiling(\frac{n-1}{2})$ 。

其中$floor()$为向下取整函数，$ceiling()$为向上取整函数。

证：$\because$ $n=n_0+n_1+n_2$ ，$n_0=n_2+1$

$\therefore n=2n_0+n_1-1$

又$\because$ $n_1$要么是1个，要么是0个。

当$n_1=1$时：n必须为偶数，$n_0=\frac{n}{2}$，$n_1+n_2=\frac{n}{2}$；

当$n_1=0$时：n必须为奇数，$n_0=\frac{n+1}{2}$，$n_1+n_2=\frac{n-1}{2}$。

$\therefore$$n_0=floor(\frac{n+1}{2})=ceiling(\frac n 2)$，

$n_1+n_2=floor(\frac n 2)=ceiling(\frac{n-1}{2})$。

一棵有$n$个节点的二叉树（$n \gt 0$ ），按从上到下、从左到右的顺序从1开始依次对各节点进行编号，对任意第$i$个节点有：
- 若$i$ = 1，则它是根节点。
- 若$i \gt 1$，则它的父节点编号为$floor(\frac{i}{2})$，其中$floor()$为向下取整函数。
- 若$2i\le n$（即$i\le \frac{n}{2}$），则它的左子节点编号为$2i$。
- 若$2i\gt n$（即$i\gt \frac{n}{2}$)，则它没有左子节点。
- 若$2i+1\le n$（即$i\le \frac{n-1}{2}$），则它的右子节点编号为$2i+1$。
- 若$2i+1\gt n$（即$i\gt \frac{n-1}{2}$)，则它没有右子节点。
一棵有$n$个节点的二叉树（$n \gt 0$），按从上到下、从左到右的顺序从0开始依次对各节点进行编号，对任意第$i$个节点有：
- 若$i$ = 0，则它是根节点。
- 若$i$ > 0，则它的父节点编号为$floor(\frac{i-1}{2})$，其中$floor()$为向下取整函数。
- 若$2i+1\le n-1$（即$i\le \frac{n-2}{2}$），则它的左子节点编号为$2i+1$。
- 若$2i+1\gt n-1$（即$i\gt \frac{n-2}{2}$）)，则它没有左子节点。
- 若$2i+2\le n-1$（即$i\le \frac{n-3}{2}$），则它的右子节点编号为$2i+2$。
- 若$2i+2\gt n-1$（即$i\gt \frac{n-3}{2}$)，则它没有右子节点。