先序遍历哈夫曼树幷求其编码

更新时间2018-07-23 07:27:52

先序遍历哈夫曼树，即从根结点出发，遍历哈夫曼树，输出其编码

以先根次序遍历二叉树。然后还要定义一整数a，初始值为1。在访问某一节点时将其作为参数传入，如果访问的是左节点传入a*2，访问右节点传入a*2+1，也就是在a的二进制数据中，向左走在末尾加个0，向右走加个1（初始化为1是为了避免开始时向左走，无法加零的情况，输出时要将首位的1去掉），即visit（root，a），visit（left，a*2），visit（right，a*2+1）。访问到叶子节点时将a转化成二进制，再将首位的1去掉即可。当然你也可以定义一个字符串，然后在末尾加0加1，只是这样递归起来开销比较大，用整数*2的方法比较简单，但是最后需要转化处理。