树和二叉树

太过爱你忘了你带给我的痛 2023-02-20 10:57 189阅读 0赞

### 树和二叉树 ###

*   *  树的定义和基本术语
     *  二叉树的定义
     *  二叉树的性质
     *  线索二叉树
     *  森林与二叉树的转换
     *  哈夫曼树的基本概念
     *   *   构造哈夫曼树口诀

## 树的定义和基本术语 ##

**树（Tree）** 是 n (n >= 0)个结点的有限集。

在任意一颗非空树中：

1. 有且仅有一个 **根（root）** 结点

2. 当 n > 1 时，其余结点可分为 m（m > 0）个互不相交的有限集T1、T2，… ，Tm，其中每一个集合本身又是一颗树，并且称为根的 **子树（SubTree）**。

树的 **结点** 包含一个数据元素及或干个指向子树的分支。

**根结点**：非空树中无前驱结点的结点。

**结点的度**：结点拥有的子树数。

度为 0 的结点称为 **叶子（Leaf）或 终端结点**。

结点的子树的根称为该结点的 **孩子**，该结点称为孩子的 **双亲**。

**树的度**：树内各结点的度的最大值。

**树的深度**：树中结点的最大层次。

![树的基本概念和术语][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjI5ODU3_size_16_color_FFFFFF_t_70]

**有序树**：树中结点的各子树从左至右有次序（最左边的为第一个孩子）。

**无序树**：树中结点的各子树无次序。

**森林**：是 m（m >= 0）棵互不相交的树的集合。

*  把根结点删除，树就变成了森林。
 *  一棵树可以看成是一个特殊的森林。
 *  给森林中的各子树加上一个双亲结点，森林就变成了树。

**树 一定是 森林**

**森林 不一定是 树**

## 二叉树的定义 ##

**二叉树（Binary Tree）是 n (n >= 0)个结点的有限集，它或者是空集 (n= 0),或者由一个根结点** 及 **两棵互不相交** 的分别称作这个根的 **左子树** 和 **右子树** 的二叉树组成。

**特点**：

1.  每个结点最多有俩孩子（**二叉树中不存在度大于 2 的结点**）。
2.  子树有左右之分，其次序不能颠倒。
3.  二叉树可以是空集合，根可以有空的左子树或空的右子树。

**注：虽然二叉树与树概念不同，但有关树的基本术语对二叉树都适用。**

## 二叉树的性质 ##

**性质1**：在二叉树的第 i 层上 **至多** 有  2 i − 1 2^\{i-1\} 2i−1 个结点（ i > = 1 i >= 1 i>=1）。

**性质2**：深度为 k 的二叉树 **至多** 有  2 k − 1 2^k-1 2k−1 个结点（ k > = 1 k >= 1 k>=1）。

**性质3**：对任何一颗二叉树 T，如果其叶子树为  n 0 n\_0 n0，度为 2 的结点数为  n 2 n\_2 n2，则  n 0 = n 2 + 1 n\_0 = n\_2 + 1 n0=n2\+1

**小扩展**：

*  在二叉树的第 i 层上 **至少** 有 1 个结点（ i > = 1 i >= 1 i>=1）。
 *  深度为 k 的二叉树 **至少** 有 k 个结点（ k > = 1 k >= 1 k>=1）。

**满二叉树**：一棵深度为 k 且有  2 k − 1 2^k - 1 2k−1 个结点的二叉树称为 **满二叉树**

*  满二叉树在同样深度的二叉树中 **结点** 个数最多。
 *  满二叉树在同样深度的二叉树中 **叶子结点** 个数最多。

**完全二叉树**：深度为k的具有n个结点的二叉树，当且仅当其每一个结点都与深度为k的 **满二叉树中编号** 为1 ~ n的结点一一对应时， 称之为完全二叉树。

**满二叉树 一定是 完全二叉树**

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

注：在满二叉树中，从最后一个结点开始，**连续** 去掉 **任意** 个结点，即是一棵完全二叉树。（**一定是连续的去掉！！！**）

**性质4**： 具有 n 个结点的完全二叉树的深度为 ⌊ l o g 2 n ⌋ + 1 \\lfloor\{log2^n\}\\rfloor + 1 ⌊log2n⌋\+1

**性质5**：如果对一棵有 n 个结点的 **完全二叉树**（深度为  ⌊ l o g 2 n ⌋ + 1 \\lfloor\{log2^n\}\\rfloor + 1 ⌊log2n⌋\+1的结点按层序编号（从第1层到第 ⌊ l o g 2 n ⌋ + 1 \\lfloor\{log2^n\}\\rfloor + 1 ⌊log2n⌋\+1 层，每层从左到右），则对任一结点 i（1 <= i <= n）,有:

1.  如果 i = 1，则结点 i 是二叉树的根，无双亲；如果 i >1，则其 **双亲是结点**  ⌊ i / 2 ⌋ \\lfloor\{i/2\}\\rfloor ⌊i/2⌋。
2.  如果 2i > n，则结点 i 为叶子结点，无左孩子；否则，其 **左孩子是结点 2i**。
3.  如果 2i + 1 > n，则结点 i 无右孩子；否则，其**右孩子是结点 2i + 1**。

**性质4**：表明了完全二叉树 **结点数n** 与完全二叉树 **深度k** 之间的关系 。

**性质5**：表明了完全二叉树中 **双亲结点编号** 与 **孩子结点编号** 之间的关系。

## 线索二叉树 ##

**利用二叉链表中的空指针域**:

*  如果某个结点的 **左孩子为空**，则将空的左孩子指针域改为 **指向其前驱**
 *  如果某结点的 **右孩子为空**，则将空的右孩子指针域改为 **指向其后继**
 *  这种改变指向的指针称为 **"线索”**
 *  加上了线索的二叉树称为 **线索二叉树(Threaded Binary Tree)**
 *  对二叉树按某种遍历次序使其变为线索二叉树的过程叫 **线索化**

## 森林与二叉树的转换 ##

**树变二叉树：兄弟相连留长子**

**二叉树变树：左孩右右连双亲，去掉原来右孩线**

**森林变二叉树：树变二叉跟相连**

**二叉树变森林：去掉全部右孩线，孤立二叉再还原**

## 哈夫曼树的基本概念 ##

**路径**：从树中一个结点到另一个结点之间的分支构成这两个结点间的路径。

**结点的路径长度**：两个结点间路径上的 **分支数**。

**树的路径长度**：从 **树根** 到每个结点的 **路径长度之和**。记住：TL

结点数目相同的二叉树中，完全二叉树是路径长度最短的二叉树。

**权(weight)**：将树中结点赋给一个有着某种含义的数值，则这个数值称为该 **结点的权**。

**结点的带权路径长度**：从 **根结点** 到该结点之间的 **路径长度** 与该结点的 **权** 的 **乘积**。

**树的带权路径长度**：树中所有 **叶子** 结点的 **带权路径长度之和**。

**哈夫曼树：最优树（带权路径长度（WPL）最短的树）。**

“带权路径长度最短”是在“度相同” 的树中比较而得的结果，因此有最优二叉树、最优三叉树之称等等

**哈夫曼树：最优二叉树（带权路径长度（WPL）最短的二叉树）。**

###  构造哈夫曼树口诀 ###

1. **构造森林全是根**

2. **选用两小造新树**

3. **删除两小添新人**

4. **重复 2、3 剩单根**

包含 n 棵树的森林要经过 n - 1次合并才能形成哈夫曼树，共产生 n - 1 个新结点。

包含 n 个叶子结点的哈夫曼树中共有 2n - 1 个结点。

哈夫曼树的结点的度为 0 或 2，没有度为 1 的结点。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjI5ODU3_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200625191034901.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjI5ODU3,size_16,color_FFFFFF,t_70