数据结构-树 | 李博的博客
0%

数据结构-树

关于树的算法及其复杂度和适用场景分析

$HuffmanTree$(哈夫曼树)

小知识点

  1. 因为哈夫曼树除了叶子结点外,其他节点都是两个结点合并构成的,所以不存在度为1的结点。
  2. 因为$n_{sum}=n_0+n_1+n_2$,并且$n_1=0$。
  3. 且总的分支数加根结点就是总的结点个数,所以$n_{sum}=2n_2+1$。
  4. 综上可得$n_{sum}=2n_0-1$。

存储结构如下:

1
2
3
4
typedef struct{
int weight; //结点的权值
int parent,lchild,rchild; //结点的双亲,左孩子,右孩子的下标
}HTNode,*HuffmanTree; //动态分配数组存储哈夫曼树
如果对您有帮助,请我喝杯奶茶?