树与二叉树

目录

• 树与二叉树
  • 目录
  • 1. 哈夫曼树
    • 1.1. 构造过程
    • 1.2. 特点

1. 哈夫曼树

含有$n$个带权叶结点的二叉树中，其中带权路径长度最小的二叉树称为哈夫曼树，也称为最优二叉树。

1.1. 构造过程

给定 $n$ 个权值分别为$w_1$至$w_n$的节点,构造度为2的哈夫曼树的算法描述如下。

1. 将这$n$个节点分别作为 $n$ 棵，仅含一个结点的二叉树，构成森林 $F$。
2. 构造一个新节点，从$F$中选取两棵根结点权值最小的数作为新结点的左右子树，并且将新结点的权值为左右子树上根结点的权值之和。
3. 从$F$中删除刚才选出的两棵树，同时将新得到的数加入$F$之中。
4. 重复步骤 $2$ 和$3$直至$F$中只剩下一棵树为止。

1.2. 特点

从上述构造过程中，可以看出哈夫曼树具有如下特点。

1. 每个初始节点最终都成为叶节点，且权值越小的结点到根结点的路径长度越大。
2. 构造过程中共新建了$n-1$个节点（双分支结点），因此哈弗曼树的结点总数为 $2n-1$。
3. 每次构造都选择两棵树作为新节点的孩子，因此哈夫曼树中不存在度为1的节点。