《零食：二叉树》——2021-02-19

[sworlife]

树

树是 n(n >= 0) 个结点的有限集合。当 n=0 时，称之为空树。

树是由有限个结点组成，那么，结点之间是怎么关联起来的呢？ 有且仅有一个结点作为根结点，其它结点又可分为 m(m>=0) 个互不相交的有限集合，其中每个集合又构成一棵树，并称为根结点的子树。

树的组成特点

由此，可以看出，树具有递归的特性，也就是说一棵树由若干棵子树构成，而子树又由更小的子树构成。这便是树的组成特点。

数据结构的逻辑关系

结点之间由明确的层次关系。对于某个结点来说，它最多只和上一层的一个结点有直接关系，而与其下一层的多个结点有直接关系。

术语

• 双亲：该结点的上一层结点
• 孩子（子树）：该结点的下一层结点
• 兄弟：与该结点拥有有同一个双亲结点的结点
• 结点的度：该结点拥有子树的个数
• 叶子结点（终端结点）：度为 0 的结点
• 内部结点：除根结点之外，度不为 0 的结点
• 结点的层次：根为第一层，根的孩子为第二层，以此类推
• 树的高度（深度）：一棵树的最大层数
• 有序（无序）树：将树中结点的各子树看成是从左到右有次序关系，即不能交换次序，则称为有序树，否则称为无序树
• 森林：m(m>=0) 棵互不相交的树的集合

二叉树

由一个根结点即两颗不相交的、分别称为左子树和右子树的二叉树所组成。

定义描述中都包含递归，无线套娃啊。 因此，二叉树中结点的度最大值为 2。另外，二叉树中结点的子树要区分左子树和右子树，即使只有一棵子树，也需要明确支出该子树是左子树还是右子树。

二叉树的性质

1. 二叉树第 i 层（ i>=1）上至多有 2^(i-1) 个结点
2. 深度为 k 的二叉树至多有 2^k -1 个结点（k >= 1）
3. 对任务一棵二叉树，设叶子结点数为 n0，度为 2 的结点数为 n2，则 n0 = n2 + 1

满二叉树

深度为 k，有 2^k - 1 个结点的二叉树称为：满二叉树。

完全二叉树

从上而下，从左至右的顺序填充结点的二叉树，称为：完全二叉树。 因此，完全二叉树是满二叉树的子集。

二叉树的存储结构

• 顺序存储 用一组连续的存储单元来存储二叉树中的结点，通过将树中的结点排成一个适当的线性序列，并且结点在这个序列中的相互位置能反映出结点之间的逻辑关系。

  那么，顺序存储时，具体是一个什么样的逻辑关系呢？

  1. 若 i = 1，则该结点为根结点
  2. 若 i >= 1，则该结点的双亲结点为 i%2，左子树结点为 2i，右子树结点为 2i + 1

显然，顺序存储结构对完全二叉树而言既简单又节省空间，而对一般二叉树则不适用，虽然可通过添加“虚结点”来构造完全二叉树，但造成了空间浪费，得不偿失。

• 链式存储 二叉树中的结点包含有数据元素，左子树根，右子树根及双亲等信息，因此可用三叉链表或二叉链表来存储二叉树，链表的头指针指向二叉树的根结点。

  我发现，不管是什么样的数据结构，在进行存储的时候，就只有两种可能：连续，不连续。连续地址存储就是数组，只要通过找到数组索引与数据结构所表达的逻辑关系即可。不连续地址存储就是链表，这没什么，就是增加每个结点的存储空间，保存其来源指针以及去向指针。

最优二叉树（哈夫曼树）

带权路径长度最短的树

什么是带权路径长度呢？

• 路径长度：从一个结点到另一个结点所经过的分支数目
• 带权路径长度：该结点到根结点之间的路径长度与该结点权值的乘积 就是：树中所有叶子结点的带权路径长度之和

如何构造最优二叉树

将权值最小的结点放置在树的最底层，以此类推。

1. 给定所有叶子结点的权值：F {w1, w2, ..., wn}
2. 虚增一个根结点，选权值最小的两个叶子结点分别作为其左子树和右子树，其该根结点的权值为：左右子树权值之和
3. 从F 中删除选中的两个结点，将新构造的树放入 F
4. 重复 2 - 2 步，直到 F 只含一棵树为止

二叉查找树（二叉排序树、二叉检索树）

1. 左子树中所有结点的值均小于根结点的值
2. 右子树中所有结点的值均大于根结点的值
3. 左右子树也是二叉查找树

因此，对二叉查找树进行中序遍历，可得到一个递增有序的序列。