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}$ )，则它没有右子节点。