OK,昨天我们对huffman数的基本知识,以及huffman树的创建做了一些简介,http://www.cnblogs.com/Frank-C/p/5017430.html
今天接着聊:
huffman树创建完成之后,我们如何去得到huffman编码呢?
图12.4_1 huffman树形结构
图12.4_2 huffman存储结构(数组)
首先,以上面的树为例,我们必须明白几个要点:
1:从什么地方开始访问这颗树:根节点 , index 2n-1 = 15
2:访问的规则:向左为0 向右为1
3:以什么样的访问循序去访问呢?
好说,
(1): 询问是否有左孩子,一直向左走,直到左孩子为零,如果此时右孩子也为零,证明已经找到了一个叶子结点(信息元)。(当然,在访问的同时进行编码记录)
(2): 原路返回一层(编码同时减一),询问是否有右孩子,有,进入右孩子,无,再返回上一层
一直重复(1)和(2)步,直到最终回退到更节点,在回到根节点的parent,即此时迭代器(index)为零
当然,我只是说了一下大概的步骤,具体的代码实现,还得是细之又细,往下看!!!!!! 有木有
*HC=(HuffmanCode)malloc((n+)*sizeof(char*));
/* 分配n个字符编码的头指针向量([0]不用) */
cd=(char*)malloc(n*sizeof(char)); /* 分配求编码的工作空间 即传递(temp)空间*/
c=m; //直接指向最上面那个非叶子节点
cdlen=;
for(i=;i<=m;++i)/* 遍历赫夫曼树时用作结点状态标志 直接把全部节点置为零 此时这棵树已经建立了 故权重已经没有多大用处了*/
(*HT)[i].weight=;
while(c)
{
if((*HT)[c].weight==) //负责向左
{ /* 向左 */
(*HT)[c].weight=; /* ************* */
if((*HT)[c].lchild!=) /*如果权为零的左孩子节点不是第一个元素(下标为0)*/
{
c=(*HT)[c].lchild;
cd[cdlen++]='';
}
/*看这个左孩子有没有右孩子 如果右孩子为零(即没有右孩子),那么是一个叶子节点*/
else if((*HT)[c].rchild==)
{ /* 登记叶子结点的字符的编码 */
(*HC)[c]=(char *)malloc((cdlen+)*sizeof(char));
cd[cdlen]='\0';
strcpy((*HC)[c],cd); /* 复制编码(串) */
}
}
/*条件改变*/
else if((*HT)[c].weight==) /*负责向右 只会回退 不会动 判断是左孩子是叶子节点还是中间的内点*/
{ /* 向右 */
(*HT)[c].weight=; /////************
if((*HT)[c].rchild!=) //决定你这个权值此时会不会被清零
{
c=(*HT)[c].rchild;
cd[cdlen++]='';
}
}
else //负责回退
{ /* HT[c].weight==2,退回 */
(*HT)[c].weight=; /////**************
c=(*HT)[c].parent;
--cdlen; /* 退到父结点,编码长度减1 迭代:利用前面走过的路*/
}
}
free(cd);
上面代码通过一个weight(在while语句执行之前就已经被清零了哦哦哦),来判断当前节点(叶子节点的情况除外):(只作为过程说明,不是状态判断条件)
未被访问或已经被访问且没有用了: 0
正在访问左树且“右树还没有访问”(当然这是废话): 1
正在访问右树且 ”左树已经访问“ (当然这也是废话): 2
什么时候回退,左节点没有或已经访问完,且,右节点没有或已经访问玩,如何保证之前这些个条件呢。简单,if else分支语句的作用体现出来了,把负责回退的判断语句放在最后,前面来判断有左孩子木有哈,有右孩子木有啊,没有,证明找到一个叶子节点(信息元),记录信息,此时,此叶子节点weight已经被置为1,那么最中被置为2且没有右节点,进入最后一个else分支,置为零且回退。
当分支节点为1是(此时左节点已经被访问),会首先被置为2,询问是否有右节点,有进入,即注意,当前节点如果是父节点的右孩子,字此时的父节点weight定被置为了二,当此节点为叶子节点且符合上面的叶子节点回退规则时,回退到父节点,父节点有为2,继续回退。
总结:代码分支语句分成了三个主分支块 weight为0(判断是否未访问过的节点) weight为1(判断是否为左树已经访问) weight为2,节点weight需要进行清零且回退
对于叶子节点,则主要有第一个分支块进行处理,并由第二和三个分支块进行辅助判断与回退。
如何去通过编码反编译成信息或信息元,我想着就再简单不过了,至少比编码的创建容易吧,直接根据树以一定的规则去找(如,0:左孩子, 1:右孩子), 鉴于每个信息元的独立性与信息元之间的无包含性,既适合反编码,有适合找错误。
OK,That’s all!!!