数据结构-树 Posted on 2019-06-03 Edited on 2020-09-04 In 大二-数据结构 Views: 关于树的算法及其复杂度和适用场景分析$HuffmanTree$(哈夫曼树)小知识点 因为哈夫曼树除了叶子结点外,其他节点都是两个结点合并构成的,所以不存在度为1的结点。 因为$n_{sum}=n_0+n_1+n_2$,并且$n_1=0$。 且总的分支数加根结点就是总的结点个数,所以$n_{sum}=2n_2+1$。 综上可得$n_{sum}=2n_0-1$。 存储结构如下: 1234typedef struct{ int weight; //结点的权值 int parent,lchild,rchild; //结点的双亲,左孩子,右孩子的下标}HTNode,*HuffmanTree; //动态分配数组存储哈夫曼树