树

树

树是一种非线性结构，树中的每一个元素可以有两个或两个以上的直接后继元素，用来描述层次结构关系

• 树的性质
  1. 结点总数为n，分支总数为m，则 n = m + 1
  2. 结点总数为n，度为0的结点总数为n0，度为1的结点总数为n1，则 n = n0 + n1 + n2 + ... ni
  3. 分支总数为m, 度为i的结点总数为ni，则 m = n0*0 + n1*1 + n2*2 + ... ni*i

二叉树

二叉树是n个节点的有限集合，它或者是空树，或者是由一个根节点及两颗互不相交的分别称为左右子树的二叉树组成，与树的区别是二叉树各个节点的度最大为2

• 满二叉树：在一颗二叉树中，如果所有非叶子节点同时具有左孩子与右孩子，并且所有叶子节点都在同一层上，即一颗深度为k并且含有2^k-1个节点的二叉树称为满二叉树

• 完全二叉树：一颗深度为k，有n个节点的二叉树，对树中的节点按从上至下，从左到右的顺序进行编号，如果编号为i(i>=1,i<=n)的节点与满二叉树中编号为i的节点在二叉树中的位置相同，则这棵树称为完全二叉树

• 二叉树的性质

  1. 在二叉树的第i层最多有2^(i-1)个结点
  2. 深度为k的二叉树最多有2^k - 1个结点
  3. 若叶子结点树为n0，度为2的结点数为n2，则 n0 = n2 + 1

• 二叉树的存储

  1. 顺序存储:从上到下，从左到右的顺序将二叉树的节点依次存入数组中。完全二叉树与一般二叉树相比节省了空间，这是因为一般二叉树需要添加一些虚节点而造成了空间的浪费
  2. 链式存储:一般用二叉链表来存储二叉树节点，二叉链表中除了该节点本身的数据外，还存储左孩子节点的指针和右孩子节点的指针，即一个数据两个指针。每个二叉链表结点存储一个二叉树节点，头指针则指向根节点。

• 二叉树的遍历

  flowchart TD a((a)) b((b)) c((c)) d((d)) e((e)) o1((O)) f((f)) g((g)) o2((O)) h((h)) o3((O)) a --- b a --- c b --- d b --- e c -.❌.- o1 c --- f e --- g e -.❌.- o2 g -.❌.- o3 g --- h
  1. 前序遍历：根 左 右 abdeghcf
  2. 中序遍历：左 根 右 dbgheacf
  3. 后续遍历：左 右 根 dhgebfca
  4. 层次遍历：按层次，从上到下，从左到右 abcdefgh
     按照这样的构造之后呢，尽量前驱和后期之后呢？就选择一个牵手反差术

最优二叉树

最优二叉树也称为哈夫曼树，是一种带权路径长度最短的二叉树

概念及定义

• 路径 : 树中一个节点到另外一个节点的通路
• 路径长度 : 通路上分支的个数
• 树的路径长度 : 根节点到每一个叶子节点的路径长度之和
• 权 : 结点代表的值
• 节点的带权路径长度 : 该节点到根节点之间的路径长度与该节点权值的乘积
• 树的带权路径长度 : 树中所有叶子节点的带权路径长度之和

构建哈夫曼树

假设有 n 个权值，则构造出的哈夫曼树有 n 个子节点，n个权值分别为 W1，W2，… Wn，哈夫曼树的构造规则为:

1. 将W1，W2，… Wn 看成是有n棵树的森林(每棵树仅有一个节点)
2. 在森林中选出2个根节点权值最小的树合并，作为一颗新树的左右子树，且新树的根节点权值为其左右子树根节点权值之和
3. 从森林中删除选取的2颗树，并将新树加入森林
4. 重复 2和3 步，直到森林只剩一颗树为止，该树即为所求的哈夫曼树

哈夫曼编码

先构造哈夫曼树，左分支表示字符“0”，右分支表示字符“1”，可得到哈夫曼编码，也就是总字符编码长度最短的编码。 构造哈夫曼树时一般遵循权值左小右大的原则

• 哈夫曼树的节点树 = n0(度为0的叶子节点数) + n2(度为2的合并节点数)，其中 n0 - n2 = 1，则哈夫曼编码个数为 n0

树与森林的转化

转换原理：树的最左边左为二叉树的左子树，树的其他节点作为其左边兄弟节点的右子树，任何一颗与树对应的二叉树其右子树必为空