数据结构-树

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

$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$。

存储结构如下:

typedef struct{
    int weight;                 //结点的权值
    int parent,lchild,rchild;   //结点的双亲，左孩子，右孩子的下标
}HTNode,*HuffmanTree;           //动态分配数组存储哈夫曼树