Tree

一对多的数据结构——树

树

树（Tree）是$n$个结点的有限集。

空树：$n=0$
非空树：
- $n>0$
- 有且仅有一个特定的根结点（Root）
- 当$n>1$时，其余结点可分为$m(m>0)$个互不相交的有限集$T_1,\cdots,T_m$；其中每一个集合自身是一棵树，称之为根的子树（SubTree）
有序树
如果树中结点的各子树从左至右是有次序的、不能互换左右子树的，则该树为有序树
无序树
树中结点可互换左右子树，则该树为无序树

森林

森林（Forest）：$m$棵互不相交的树的集合

树中的每个结点的子树的集合就是森林

结点

树的结点（Node）包含一个数据元素及若干指向其子树的分支。

度

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

叶结点（Leaf）：度为0的结点
非终端结点/分支结点：度不为0的结点
内部结点：除根结点外的分支结点

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

结点间关系

Child：结点的子树的根，称为该结点的Child
Parent：Child的前一个结点称为Child的Parent
Sibling：同一个Parent的Child之间互称Sibling（兄弟）
祖先：某结点的祖先是从根结点（Root）到该结点所经分支上的所有结点
子孙：以某结点为根的所有子树的结点都称为该结点的子孙
堂兄弟：双亲在同一层的结点互为堂兄弟

层次

结点的层次（Level）：从根开始，根为第一层；根的孩子为第二层；第二层结点的孩子（第二层结点的子树的根）所在的为第三层；依此类推。

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

二叉树

二叉树（Binary Tree）：$n$个结点的有限集合

空二叉树：$n=0$
由一个根结点和两棵互不相交的二叉树组成。这两棵二叉树称为根结点的左子树和右子树

二叉树的特点：

每个结点最多有2棵子树。即，二叉树的所有结点的度$\leq2$
二叉树是有序树。左子树和右子树的次序不能任意颠倒
即使某个结点的子树只有一棵，也必须区分它是左子树还是右子树

二叉树可能的基本形态：

空二叉树（$n=0$）
只有一个根结点（$n=1$）
根结点只有左子树（$n=2$）
根结点只有右子树（$n=2$）
根结点既有左子树又有右子树（$n\geq3$）

具有2个结点的二叉树的可能形态有2种
具有3个结点的二叉树的可能形态有5种

斜树

左斜树和右斜树统称为斜树。

左斜树：所有结点都只有左子树的二叉树
右斜树：所有结点都只有右子树的二叉树
- 斜树的每一层都只有一个结点
- 斜树的结点个数与树的深度相同

满二叉树

所有分支结点都存在左子树和右子树、所有叶子结点都在同一层上的二叉树称为满二叉树(Full Binary Tree)。

满二叉树的特点：

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

完全二叉树

定义（待补充）(Complete Binary Tree)

满二叉树一定是一棵完全二叉树
完全二叉树不一定是满二叉树

完全二叉树的特点：

叶子结点只能出现在最底两层
最底层的叶子结点一定集中在左部连续位置（？？）
倒数第二层，若有叶子结点，一定都在右部连续位置（？？）
完全二叉树不存在只有右子树的情况
同样结点数的二叉树，完全二叉树的深度最小

平衡二叉树

平衡二叉树（BT，Balance Tree），又称AVL树：是一棵空树，或它的左右子树的高度差的绝对值不超过1，且左右子树都是一棵平衡二叉树

二叉树性质

二叉树的第$i$层上最多有$2^{i-1}$个结点（$i\geq 1$）
深度为$k$的二叉树最多有$2^k-1$个结点（$k\geq1$）

$k=1$：最多有$1(2^1-1)$个结点
$k=1$：最多有$1+2=3(2^2-1)$个结点
$k=2$：最多有$1+2+2²⁼⁷⁽²3-1)$个结点
……
对任意的$k$，最多有$2⁰⁺²1+\cdots+2^k=2k-1$个结点

对任意一棵二叉树$T$，有$n_0$个叶子结点（度为0）、$n_2$个度为2的结点，则有$n_1=n_2+1$
- 度为0的结点数为$n_0$
- 度为1的结点数为$n_1$
- 度为2的结点数为$n_2$
  - 二叉树的结点的度最多为2，所以树$T$的结点总数为
    $$n=n_0+n_1+n_2$$
- 只有根结点没有连接线进入，其他结点都有连接线进入，所以连接线总数为$n-1$
- 度为1的结点有一条向下的连接线，度为2的结点有2条向下的连接线，度为0的结点没有向下的连接线，所以连接线总数为$n_1+2n_2$
  - 连接线总数为
    $$n_L=n-1=n_1+2n_2$$
- 由上面两个等式可得
  $$n_0=n_2+1$$
具有$n$个结点的完全二叉树的深度为$[\log_2{n}]+1$（$[x]$表示不大于$x$的最大整数）
- 深度为$k$的满二叉树的结点数为$n=2^k-1$
- 有$n$个结点的满二叉树的深度为$k=\log_2{(n+1)}$
- 完全二叉树的叶子结点只可能出现在最下面两层，则深度为$k$的完全二叉树的结点数$n$一定多于深度为$k-1$的满二叉树、不多于深度为$k$的满二叉树。即
  $$2^{k-1} -1 < n \leq 2^k-1$$
  也即
  $$2^{k-1} \leq n < 2^k$$
  $$k-1 \leq \log_2n <k$$
  所以有
  $$k=[\log_2n]+1$$
对一棵有$n$个结点的完全二叉树（深度为$[\log_2n]+1$）的结点按层序编号（从第1层到第$[\log_2n]+1$层，每层从左到右），对任一结点$i(1\leq i\leq n)$有：
- 如果$i=1$，则结点$i$为二叉树的根结点，无双亲（Parent）
- 如果$i>1$，则结点$i$的双亲是$[\frac{i}{2}]$
- 如果$2i>n$，则结点$i$为叶子结点、无左孩子（Left Child）；否则其左孩子是结点$2i$
- 如果$2i+1>n$，则结点$i$为叶子结点、无右孩子（Right Child）；否则其右孩子是结点$2i+1$

二叉树的存储结构

顺序存储

用一维数组存储二叉树中的结点，数组的下标是结点的存储位置
深度为$k$的二叉树的顺序存储有$2^k-1$个存储单元空间
顺序存储结构一般只用于完全二叉树

二叉链表

一个数据域（存储结点）、两个指针域（分别存储left child和right child）的链式存储结构

二叉树的遍历

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

已知前序遍历序列和中序遍历序列，可以唯一确定一棵二叉树
已知后序遍历序列和中序遍历序列，可以唯一确定一棵二叉树
已知前序和后序遍历序列，不能确定一棵二叉树

前序遍历

二叉树为空

返回空

二叉树非空

$$根结点 \rightarrow前序遍历左子树 \rightarrow 前序遍历右子树$$
$$中\rightarrow左\rightarrow右$$

$$1→2→4→5→3→6→7$$

中序遍历

二叉树为空

返回空

二叉树非空

$$中序遍历根结点的左子树\rightarrow根结点\rightarrow中序遍历右子树$$
$$左\rightarrow中\rightarrow右$$

$$4→2→5→1→6→3→7$$

后序遍历

二叉树为空

返回空

二叉树非空

$$后序遍历左子树\rightarrow后序遍历右子树\rightarrow根结点$$
$$左\rightarrow右\rightarrow中$$

$$4→5→2→6→7→3→1$$

层序遍历

二叉树为空

返回空

二叉树非空

从根结点、从上往下逐层遍历；在同一层，按从左到右的顺序对结点逐个访问

$$1→2→3→4→5→6→7$$

赫夫曼

赫夫曼树

赫夫曼编码

二叉查找树

二叉搜索树/二叉查找树（Binary Search Tree）

是一种数据结构
不能随机访问

左子树上所有结点的值均小于根结点的值，而右子树上所有结点的值均大于根结点的值（？？？）

运行时间

平均运行时间为$O(\log{n})$
最糟的运行时间为$O(n)$

	数组	二叉查找树
查找	$O(\log{n})$	$O(\log{n})$
插入	$O(n)$	$O(\log{n})$
删除	$O(n)$	$O(\log{n})$

最小生成树

最小生成树（MST，Minimum Spanning Tree）：一个有$n$个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有$n$个结点，并且有保持图连通的最少的边。

一个图可以有许多棵不同的生成树
生成树的定点数与图的定点数相同
生成树是图的极小连通子图，去掉一条边则非连通
一个有$n$个顶点的连通图的生成树有$n-1$条边
含$n$个顶点、$n-1$条边的图不一定是生成树

实现

可用

克鲁斯卡尔算法（Kruskal）
普里姆算法（Prim）
实现

B树、红黑树、堆、伸展树

未完

Skye

树

树

树

森林

结点

度