哈夫曼树的创建

哈夫曼树创建
2018-01-02 20:51:01
这是我自己写的几个实习题目，可以用，也有思想，希望可以通过审核
收起
数据结构
哈夫曼树创建遍历
2012-09-18 13:12:21
程序代码包括创建二叉树，遍历树，创建哈夫曼树，打印哈夫曼树叶子节点的路径。
收起

哈夫曼树创建（C++）笔记

2021-04-26 16:33:10

②创建树：循环n-1次，通过n-1次的选择、删除与合并来创建哈夫曼树。选择是从当前森林中选择双亲为0且权值最小的两个树根节点s1和s2的权值和作为一个新节点的权值依次存入到数组的第n+1之后的单元中同时记录这个新...

算法步骤
 ①：初始化：首先动态分配申请2n个单元：然后循环2n-1次
 从1号单元开始，依次将1☞2n-1所有单元中的双亲、左孩子、右孩子的下标都初始化为0；
 最后再循环n次，输入前n个单元中所有叶子节点的权值。 
②创建树：循环n-1次，通过n-1次的选择、删除与合并来创建哈夫曼树。
 选择是从当前森林中选择双亲为0且权值最小的两个树根节点s1和s2的权值和作为一个新节点的权值依次存入到数组的第n+1之后的单元中
 同时记录这个新结点做孩子的下标为s1，右孩子的结点下标为s2.
   
哈夫曼树的创建： 
//构造哈夫曼树HT
void CreateHuffmanTree(HuffmanTree &HT, int n)
{
	if (n <= 1)
		return;
	int m = 2 * n - 1;
	HT = new HTNode; //0号单元未用，所以需要动态分配m+1个单元，HT[m]表示根节点
	for (int i = 1; i <= m; i++) //将1-m号单元中的双亲、左孩子、右孩子的下标都初始化为0
	{
		HT[i].parent = 0;
		HT[i].lchild = 0;
		HT[i].rchild = 0;
	}

	cout << "请输入你节点的权值" << endl;
	for (int i = 1; i <= n; i++) //输入前n个单元叶子结点的权值
	{
		cin >> HT[i].weight;
	}

	int s1, s2;
	//创建哈夫曼树
	for (int i = n + 1; i <= m; i++)
	{
		//通过n-1次选择、删除、合并创建哈夫曼树
		Select(HT, i - 1, &s1, &s2);
		//在HT[k]（1≤k≤i-1）中选择两个其双亲域为0且权值最小的节点，并返回它们在HT中的序号s1,s2
		HT[s1].parent = i;
		HT[s2].parent = i;
		//得到新节点i，从森林中删除s1，s2，将s1和s2的双亲域由0改为1
		HT[i].lchild = s1; //s1,s2分别为i的左右孩子
		HT[i].rchild = s2;
		HT[i].weight = HT[s1].weight + HT[s2].weight;//i的权值为左右孩子的权值和
	}
}
 
Select函数的实现： 
void Select(HuffmanTree HT,int sum, int *s1, int *s2)
{
	int min1 = 0x7f7f7f7f;
	int min2 = 0x7f7f7f7f;

	//求双亲节点为0且为最小的元素，将其下标传给s1
	for (int i = 1; i <= sum; i++)
	{
		if (HT[i].parent == 0 && min1 > HT[i].weight)
		{
			min1 = HT[i].weight;
			*s1 = i;
		}
	}
	//求双亲节点为0且为倒数第二小的元素，将其下标传给s1
	for (int i = 1; i <= sum; i++)
	{
		if (i != *s1 && HT[i].parent == 0)
		{
			if (HT[i].parent < min2)
			{
				min2 = HT[i].weight;
				*s2 = i;
			}
		}
	}
} 
输出哈法曼树： 
//输出哈夫曼
void put_Tree(HuffmanTree HT, int m)
{
	if (HT == NULL)
	{
		cout << "哈夫曼树为空" << endl;
		return;
	}
	printf("节点   权值    双亲   左孩子   右孩子\n");
	for (int i = 1; i <= m; i++)
	{
		printf("%3d %5d %5d %5d %5d\n", i, HT[i].weight, HT[i].parent, HT[i].lchild, HT[i].rchild);
	}
} 
完整代码： 
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;

// 哈夫曼树的储蓄表示
typedef struct HTNode
{
	int weight; //结点的权值
	int parent, lchild, rchild;//节点的双亲、左孩子、右孩子的下标
}*HuffmanTree;

/*算法步骤
①：初始化：首先动态分配申请2n个单元：然后循环2n-1次
从1号单元开始，依次将1☞2n-1所有单元中的双亲、左孩子、右孩子的下标都初始化为0；
最后再循环n次，输入前n个单元中所有叶子节点的权值。

②创建树：循环n-1次，通过n-1次的选择、删除与合并来创建哈夫曼树。
选择是从当前森林中选择双亲为0且权值最小的两个树根节点s1和s2的权值和作为一个新节点的权值依次存入到数组的第n+1之后的单元中
同时记录这个新结点做孩子的下标为s1，右孩子的结点下标为s2.
*/

bool cmp(struct HTNode x, struct HTNode y)
{
	return x.weight > y.weight;
}

void Select(HuffmanTree HT,int sum, int *s1, int *s2)
{
	int min1 = 0x7f7f7f7f;
	int min2 = 0x7f7f7f7f;

	//求双亲节点为0且为最小的元素，将其下标传给s1
	for (int i = 1; i <= sum; i++)
	{
		if (HT[i].parent == 0 && min1 > HT[i].weight)
		{
			min1 = HT[i].weight;
			*s1 = i;
		}
	}
	//求双亲节点为0且为倒数第二小的元素，将其下标传给s1
	for (int i = 1; i <= sum; i++)
	{
		if (i != *s1 && HT[i].parent == 0)
		{
			if (HT[i].parent < min2)
			{
				min2 = HT[i].weight;
				*s2 = i;
			}
		}
	}
}

//输出哈夫曼
void put_Tree(HuffmanTree HT, int m)
{
	if (HT == NULL)
	{
		cout << "哈夫曼树为空" << endl;
		return;
	}
	printf("节点   权值    双亲   左孩子   右孩子\n");
	for (int i = 1; i <= m; i++)
	{
		printf("%3d %5d %5d %5d %5d\n", i, HT[i].weight, HT[i].parent, HT[i].lchild, HT[i].rchild);
	}
}

//构造哈夫曼树HT
void CreateHuffmanTree(HuffmanTree &HT, int n)
{
	if (n <= 1)
		return;
	int m = 2 * n - 1;
	HT = new HTNode; //0号单元未用，所以需要动态分配m+1个单元，HT[m]表示根节点
	for (int i = 1; i <= m; i++) //将1-m号单元中的双亲、左孩子、右孩子的下标都初始化为0
	{
		HT[i].parent = 0;
		HT[i].lchild = 0;
		HT[i].rchild = 0;
	}

	cout << "请输入你节点的权值" << endl;
	for (int i = 1; i <= n; i++) //输入前n个单元叶子结点的权值
	{
		cin >> HT[i].weight;
	}

	int s1, s2;
	//创建哈夫曼树
	for (int i = n + 1; i <= m; i++)
	{
		//通过n-1次选择、删除、合并创建哈夫曼树
		Select(HT, i - 1, &s1, &s2);
		//在HT[k]（1≤k≤i-1）中选择两个其双亲域为0且权值最小的节点，并返回它们在HT中的序号s1,s2
		HT[s1].parent = i;
		HT[s2].parent = i;
		//得到新节点i，从森林中删除s1，s2，将s1和s2的双亲域由0改为1
		HT[i].lchild = s1; //s1,s2分别为i的左右孩子
		HT[i].rchild = s2;
		HT[i].weight = HT[s1].weight + HT[s2].weight;//i的权值为左右孩子的权值和
	}
}


int main()
{

	HuffmanTree HT;
	int n;
	cout << "请输入你想创建的节点数" << endl;
	cin >> n;
	CreateHuffmanTree(HT, n);
	put_Tree(HT,2*n-1);
	return 0;
}

收起

展开全文

数据结构

JAVA数据结构与算法 11（3）树-哈夫曼树的基本介绍、哈夫曼树创建实现、哈夫曼编码、利用哈夫曼编码压缩

2020-10-14 16:35:00

2 哈夫曼树 2.1 哈夫曼树的基本介绍给定n个权值作为n个叶子结点，构造一颗二叉树，若该树的带权路径长度（WPL）达到最小，称这样的二叉树为最优二叉树，也称哈夫曼树。因此权值较大的结点距离根节点较近。 ...

JAVA数据结构与算法 11.树 
2 哈夫曼树 
2.1 哈夫曼树的基本介绍 
 给定n个权值作为n个叶子结点，构造一颗二叉树，若该树的带权路径长度（WPL）达到最小，称这样的二叉树为最优二叉树，也称哈夫曼树。因此权值较大的结点距离根节点较近。 
哈夫曼中的一些概念： 
 路径和路径长度：在一颗树中，从一个结点往下可以达到的孩子或孙子结点hi前的通路，称为路径。通路中分支的数目称为路径长度。若规定根节点的层数为1，则从根节点到第L层结点的路径长度为L-1。 
 结点的权和带权路径长度：若将树中结点赋给一个有某种含义的数值，则这个数值称为该结点的权。从根节点到该结点之间的路径长度与该节点的权的乘积，称为结点的带权路径长度。 
 树的带权路径长度：树的带权路径长度规定所有叶子结点带权路径长度的和，记作WPL 
 
2.2 哈夫曼树创建实现 
问题：给一个数列{13,7,8,3,29,6,1}，要求转换成一颗哈夫曼树 
 
实现思路分析： 
从小到大进行排序，将每一个数据看作每一个结点，将每一个结点看作一颗最简单的二叉树。
取出根节点权值最小的两颗二叉树，组成一颗新的二叉树，这两颗树分别作为新二叉树的左右子树，新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和
再将这颗新的二叉树添加到原来的序列中，以根节点的全职大小再进行排序，不断重复1、2、3的步骤，直到数列中，所有的数据都被处理，就得到一颗哈夫曼树。 
代码实现： 
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class HuffmanTreeDemo {
    public  static void main(String args[]){
        int[] arr = {13,7,8,3,29,6,1};
        HNode huffmanTree = createHuffmanTree(arr);

        preOrder(huffmanTree);
        //{value=67}=>{value=29}=>{value=38}=>{value=15}=>{value=7}=>{value=8}=>
        //{value=23}=>{value=10}=>{value=4}=>{value=1}=>{value=3}=>{value=6}=>{value=13}=>
    }
    /**
     *
     * @param arr 需要创建哈夫曼树的数列
     * @return  哈夫曼树的头节点
     */
    public static HNode createHuffmanTree(int[] arr){
        //1.对数列进行排序，将每一个数据看作一个结点，看作一颗最简单的二叉树（左右子结点为空）
        List<HNode> nodes = new ArrayList<>();
        for (int num: arr){
            nodes.add(new HNode(num));
        }//[{value=13},{value=7},{value=8},{value=3},{value=29},{value=6},{value=1}]

        while (nodes.size() > 1){
            Collections.sort(nodes);
            //2.一轮构建哈夫曼子树
            //2.1取出根节点权值最小的两颗二叉树
            HNode leftNode = nodes.remove(0);
            HNode rightNode = nodes.remove(0);
            //2.2组成一颗新的二叉树，这两颗树分别作为新二叉树的左右子树，新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和
            HNode node = new HNode(leftNode.value + rightNode.value);
            node.left = leftNode;
            node.right = rightNode;
            //2.3将这颗新的二叉树添加到原来的序列中
            nodes.add(node);
        }
        //3.循环结束后，数组
       return nodes.get(0);
    }

    public static void preOrder(HNode node){
        if(node != null){
            node.preOrder();
        }else System.out.println("空树不可遍历");
    }

}
class HNode implements Comparable<HNode>{
    public int value;
    public HNode left;
    public HNode right;

    public HNode(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return "{" +
                "value=" + value +
                '}';
    }

    @Override
    public int compareTo(HNode o) {
        return this.value - o.value;
    }

    //前序遍历
    public void preOrder(){
        System.out.print(this+"=>");
        if(this.left != null) this.left.preOrder();
        if(this.right != null) this.right.preOrder();
    }
}
 
2.3 哈夫曼编码 
算法介绍：哈夫曼编码，是一种可变字长编码方式，属于一种程序算法。哈夫曼编码是利用了哈夫曼树的特性再电讯通信中的经典的应用之一。被广泛的用于数据文件的压缩，其压缩率通常在20%~90%之间。 
问题：对传输的字符串i like like like java do you like a java，进行哈夫曼编码，输出各字母的编码和总字符串编码。 
实现思路： 
 对传输的字符串进行处理，获取到各个字符对应的个数；
 
 
 将各个字符的个数作为权值，构建一颗哈夫曼树，此时各个字符在哈夫曼树的均叶子结点上；
 
 根据哈夫曼树，给各个字符规定编码，向左的路径为0，向右的路径为1：得到编码：
  
 
 
可以看出，权值越大的字符层数越低，编码长度越短。 
import java.util.*;

public class HuffmanCode {
    public  static void main(String args[]){
        String s = "i like like like java do you like a java";
        HNode huffmanTree = createHuffmanTree(s);
        /**
         * {value=null,weight=40}=>{value=null,weight=17}=>{value=null,weight=8}=>
         * {value=108,weight=4}=>{value=null,weight=4}=>{value=106,weight=2}=>
         * {value=111,weight=2}=>{value=32,weight=9}=>{value=null,weight=23}=>
         * {value=null,weight=10}=>{value=97,weight=5}=>{value=105,weight=5}=>
         * {value=null,weight=13}=>{value=null,weight=5}=>{value=null,weight=2}=>
         * {value=100,weight=1}=>{value=117,weight=1}=>{value=null,weight=3}=>
         * {value=121,weight=1}=>{value=118,weight=2}=>{value=null,weight=8}=>
         * {value=101,weight=4}=>{value=107,weight=4}=>
         */
//        preOrder(huffmanTree);
        Map<Byte, String> huffmanCode = getHuffmanCode(huffmanTree);
        System.out.println(huffmanCode);
        /**
         * {32=01, 97=100, 100=11000, 117=11001, 101=1110,118=11011,
         * 105=101, 121=11010, 106=0010, 107=1111, 108=000, 111=0011}
         */
    }
    private static List<HNode> getNodes(String s){
        byte[] bytes = s.getBytes();
        Map<Byte, Integer> map = new HashMap<>();
        for (byte b:bytes){
            Integer count = map.get(b);
            if(count == null){
                map.put(b,1);
            }else {
                count ++;
                map.put(b,count);
            }
        }
        List<HNode> nodes = new ArrayList<>();
//        for (Map.Entry<Byte,Integer> entry : map.entrySet()){
//            nodes.add(new HNode(entry.getKey(),entry.getValue()));
//        }
        map.forEach((k,v)->{
            nodes.add(new HNode(k,v));
        });
        System.out.println(nodes);
        /**
         * [{value=32,weight=9}, {value=97,weight=5}, {value=100,weight=1},
         * {value=101,weight=4}, {value=117,weight=1}, {value=118,weight=2},
         * {value=105,weight=5}, {value=121,weight=1}, {value=106,weight=2},
         * {value=107,weight=4}, {value=108,weight=4}, {value=111,weight=2}]
         */
        return nodes;
    }

    public static HNode createHuffmanTree(String s){
        List<HNode> nodes = getNodes(s);
        while (nodes.size() > 1){
            Collections.sort(nodes);
            //2.一轮构建哈夫曼子树
            //2.1取出根节点权值最小的两颗二叉树
            HNode leftNode = nodes.remove(0);
            HNode rightNode = nodes.remove(0);
            //2.2组成一颗新的二叉树，这两颗树分别作为新二叉树的左右子树，新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和
            HNode node = new HNode(null,leftNode.weight + rightNode.weight);
            node.left = leftNode;
            node.right = rightNode;
            //2.3将这颗新的二叉树添加到原来的序列中
            nodes.add(node);
        }
        //3.循环结束后，数组
        return nodes.get(0);
    }

    /**
     * 生成哈夫曼编码的：
     *  1.将哈夫曼编码保存在Map<Byte,String> 中
     *  2.在生成哈夫曼编码时，需要频繁拼接字符串，因此定义一个StringBuilder
     */
    private static Map<Byte,String> huffmanCode = new HashMap<>();
    private static StringBuilder stringBuilder = new StringBuilder();
    public static void getCodes(HNode node,String code,StringBuilder stringBuilder){
        StringBuilder stringBuilder1 = new StringBuilder(stringBuilder);
        stringBuilder1.append(code);
        if(node != null){   //如果node == null 不处理
            if(node.value == null){ //此时为非叶子结点
                getCodes(node.left,"0",stringBuilder1);
                getCodes(node.right,"1",stringBuilder1);
            }else { //此时为叶子结点
                huffmanCode.put(node.value,stringBuilder1.toString());
            }
        }
    }
    public static Map<Byte,String> getHuffmanCode(HNode root){
        if(root ==  null){
            return null;
        }
        getCodes(root.left,"0",stringBuilder);
        getCodes(root.right,"1",stringBuilder);
        return huffmanCode;
    }


    public static void preOrder(HNode node){
        if(node != null){
            node.preOrder();
        }else System.out.println("空树不可遍历");
    }

}


class HNode implements Comparable<HNode>{
    public Byte value;
    public Integer weight;
    public HNode left;
    public HNode right;

    public HNode(Byte value,Integer weight) {
        this.value = value;
        this.weight = weight;
    }

    @Override
    public String toString() {
        return "{" +
                "value=" + value +
                ",weight=" + weight +
                '}';
    }

    @Override
    public int compareTo(HNode o) {
        return this.weight - o.weight;
    }
    //前序遍历
    public void preOrder(){
        System.out.print(this+"=>");
        if(this.left != null) this.left.preOrder();
        if(this.right != null) this.right.preOrder();
    }
}
 
2.4 利用哈夫曼编码压缩 
实现思路： 
利用已经获得的哈夫曼编码map，将传输的字符转成哈夫曼对应的字符串；
将哈夫曼对应的字符串按照每八位转换成一个byte值放入byte数组中返回； 
/**
     * 将字符数串string，通过生成的哈夫曼编码表，返回一个哈夫曼编码压缩后的byte[]
     * @param string
     * @param huffmanCode
     * @return  编码后的byte，将执行的编码后的String按8位对应一个byte
     *            byte[0] = 1010100(补码) => 去符号位1 => 1  0101000 => -1变反码 10100111 => (原码) 11011000 = -88
     */
    public static byte[] zip(String string,Map<Byte,String> huffmanCode){
        byte[] bytes = string.getBytes();
        StringBuilder stringBuilder = new StringBuilder();
        //1.利用huffmanCode将bytes 转成哈夫曼码对应的字符串
        for (byte b : bytes) {
            stringBuilder.append(huffmanCode.get(b));
        }
        //2.将哈夫曼码对应的字符串8位一转换成byte放入byte数组中
        int length = stringBuilder.length()%8 == 0? stringBuilder.length() / 8 :stringBuilder.length() / 8 +1;
        byte[] huffmanCodeBytes = new byte[length];
        for (int i = 0,index = 0; i <stringBuilder.length()  ; i+=8,index++) {    //每8位转换成一个byte
            String s;
            if(i+8 <stringBuilder.length()){
                s = stringBuilder.substring(i, i + 8);
            }else {
                s = stringBuilder.substring(i);
            }
            huffmanCodeBytes[index] = (byte)Integer.parseInt(s,2);  //将8位二进制字符转换为十进制值
        }

        return huffmanCodeBytes;
    }

收起

展开全文

算法数据结构 java 二叉树

哈夫曼树创建（.cpp )
2012-06-16 20:22:34
#define M 2*N-1 /*树中结点总数*/ typedef struct { char data[5]; /*结点值*/ int weight; /*权重*/ int parent; /*双亲结点*/ int lchild; /*左孩子结点*/ int rchild; /*右孩子结点*/ } HTNode; typedef ...
收起

哈夫曼树创建和哈夫曼码生成

2018-01-28 16:23:06

//初始化哈夫曼树结点 void GetMin(HTreeNode* array , int start, int end, int &s1, int &s2); //取两个权重最新的结点 void CreateHTree(HTreeNode* array , int num); //创建哈弗曼树 ...

直接上代码。 
 HTree.h 
typedef struct HTreeNode {
    char data;
    int weight;
    int parent, lchild, rchild;
}HTreeNode; 
main.cpp 
#include<stdio.h>
#include<stdlib.h>
#include<string>
#include"HTree.h"

HTreeNode* InitHTree(int num);          //初始化哈夫曼树结点
void GetMin(HTreeNode* array, int start, int end, int &s1, int &s2);    //取两个权重最新的结点
void CreateHTree(HTreeNode* array, int num);                            //创建哈弗曼树
void CreateHuffmanCode(HTreeNode* array, int numOfLeaf, char** code);   //创建哈弗曼码

int main() {
    int numOfLeaf;
    scanf_s("%d\n", &numOfLeaf);

    HTreeNode* array;                   //哈弗曼树指针
    array = InitHTree(2 * numOfLeaf);
    CreateHTree(array, numOfLeaf);
    int i;
    for (i = 1; i <= 2 * numOfLeaf - 1; i++) {
        printf("%c ", array[i].data);
        printf("%d ", array[i].weight);
    }

    char** huffmanCode;             //哈弗曼码指针
    huffmanCode = (char**)malloc(sizeof(char*) * (numOfLeaf + 1));
    CreateHuffmanCode(array, numOfLeaf, huffmanCode);

    printf("\n");
    for (i = 1; i <= numOfLeaf; i++) {
        printf("%c: ", array[i].data);
        printf("%s\n", huffmanCode[i]);
    }

    return 0;
}

HTreeNode* InitHTree(int num) {
    HTreeNode* array;
    array = (HTreeNode*)malloc(sizeof(HTreeNode) * num);
    for (int i = 1; i < num; i++) {
        array[i].data = array[i].lchild = array[i].parent = array[i].rchild = array[i].weight = 0;
    }
    return array;
}

void CreateHTree(HTreeNode* array, int numOfLeaf) {
    for (int i = 1; i <= numOfLeaf; i++) {
        char c;
        c = getchar();
        array[i].data = c;      //赋值结点数据值
        c = getchar();
        array[i].weight = int(c - '0'); //赋值结点权重值
    }
    /*建树*/
    int num = numOfLeaf;
    while (num < 2 * numOfLeaf - 1) {
        int s1, s2;
        GetMin(array, 1, num, s1, s2);      //找权重最小的两个结点
        array[num + 1].lchild = s1;
        array[num + 1].rchild = s2;
        array[num + 1].weight = array[s1].weight + array[s2].weight;
        num++;
        array[s1].parent = num;
        array[s2].parent = num;

    }
}

void GetMin(HTreeNode* array, int start, int end, int &s1, int &s2) {   //s1记录最小值的下标，s2记录第二小值的下标
    int min1 = 9999;
    int min2 = min1;
    for (int i = start; i <= end; i++) {
        if (array[i].parent != 0)
            continue;
        if (array[i].weight < min1) {
            min2 = min1;
            min1 = array[i].weight;
            s2 = s1;
            s1 = i;
        }
        else {
            if (array[i].weight < min2) {
                min2 = array[i].weight;
                s2 = i;
            }
        }
    }
}

void CreateHuffmanCode(HTreeNode* array, int numOfLeaf, char** code) {
    char *temp;
    temp = (char*)malloc(sizeof(char) * numOfLeaf);
    temp[numOfLeaf - 1] = '\0';
    int start;
    int c, f;
    for (int i = 1; i <= numOfLeaf; i++) {
        start = numOfLeaf - 1;
        c = i; f = array[i].parent;
        while (f != 0) {
            --start;
            if (array[f].lchild == c)   //左侧为0
                temp[start] = '0';
            else
                temp[start] = '1';      //右侧为1
            c = f;
            f = array[c].parent;
        }
        code[i] = (char*)malloc(sizeof(char) * (numOfLeaf - start));
        strcpy_s(code[i], numOfLeaf - start, &temp[start]);     //注意strcpy和strcpy_s的区别
    }
    free(temp);
}

收起

展开全文

哈夫曼树创建和译码

2019-12-10 08:39:29

题目描述假设某通信报文的字符集由A,B,C,D...构建哈弗曼树时：左子树根结点权值小于等于右子树根结点权值。生成编码时：左分支标0，右分支标1。输入第一行：依次输入6个整数，依次代表A,B,C,D,E,F的频度，用空格...

题目描述
 假设某通信报文的字符集由A,B,C,D,E,F这6个字符组成，它们在报文中出现的频度（频度均为整数值）。
 (1)构造一棵哈弗曼树，依次给出各字符编码结果。
 (2)给字符串进行编码。
 (3)给编码串进行译码。 
规定：
 构建哈弗曼树时：左子树根结点权值小于等于右子树根结点权值。
 生成编码时：左分支标0，右分支标1。 
输入
 第一行：依次输入6个整数，依次代表A,B,C,D,E,F的频度，用空格隔开。
 第二行：待编码的字符串
 第三行：待译码的编码串
 输出
 前6行依次输出各个字符及其对应编码，格式为【字符:编码】（冒号均为英文符号）
 第7行：编码串
 第8行：译码串
 样例输入 Copy
 3 4 10 8 6 5
 BEE
 0010000100111101
 样例输出 Copy
 A:000
 B:001
 C:10
 D:01
 E:111
 F:110
 001111111
 BADBED 
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define N 6
#define M 2*N-1
#define MAXINT 32767
#define ch 30
#define NUM 100
typedef struct{
    int weight;
    int parent;
    int lchild;
    int rchild; 
}HTNode,HuffmanTree[M]; 
typedef char* HuffmanCode[N];
void select(HuffmanTree ht,int pos,int *s1,int *s2){
    int i,j,m1,m2;/*m1存放最小权值，s1是m1在数组的下标*/
    m1=m2=MAXINT;/*m2存放次小权值，s2是m2在数组的下标*/ 
    for(j=0;j<=pos;j++) {
        if(ht[j].weight<m1&&ht[j].parent==-1){
            m2=m1;*s2=*s1;
            *s1=j;m1=ht[j].weight;
        }
        else if(ht[j].weight<m2&&ht[j].parent==-1){
            m2=ht[j].weight;
            *s2=j;
        }
    }
}
void CrtHuffmanTree(HuffmanTree ht,int w[],int n){
	int m = 2 * n - 1;
	int s1,s2;
	int i;
	for(i = 0;i < n;i++){
        ht[i].weight = w[i];
		ht[i].parent = -1;
        ht[i].lchild = -1;
		ht[i].rchild = -1;
    }
	for(i = n;i < m;i++){
        ht[i].weight = -1;
		ht[i].parent = -1;
        ht[i].lchild = -1;
		ht[i].rchild = -1;
    }
	for(i = n;i < m;i++){
		select(ht,i - 1,&s1,&s2);
		ht[i].weight = ht[s1].weight + ht[s2].weight;
		ht[i].lchild = s1;
		ht[i].rchild = s2;
		ht[s1].parent = i;
		ht[s2].parent = i;
	}
}
void CrtHuffmanCode(HuffmanTree ht,HuffmanCode hc ,int n){
	char *cd;
	int start,c,p,i;
	cd = (char*)malloc(n*sizeof(char));//按照倒序将哈夫曼编码存入cd数组， 
	cd[n - 1] = '\0';
	for(i = 0;i < n;i++){
		start = n-1;
		c = i;
		p = ht[i].parent;
		while(p != 0){
			--start;
			if(ht[p].lchild == c){
				cd[start] = '0';
			}else{
				cd[start] = '1';
			}
			c = p;
			p = ht[p].parent;
			
		}
		hc[i] = (char*)malloc((n - start)*sizeof(char));
		strcpy(hc[i],&cd[start]);
	}
	free(cd);
}
void printcode(char s[],HuffmanCode hc){
    for(int i=0;i<N;i++){
        printf("%c:", s[i]);
        printf("%s\n", hc[i]);
    }
}
void Alphagetnum(char charcode[],char s[],HuffmanCode hc){
	char *p = charcode;
	while(*p != '\0'){
		for(int j = 0;j < N;j++){
			if(*p == s[j]){
				printf("%s",hc[j]);
			}
		}
		p++;
	}
}

void Numgetalpha(char charnum[],HuffmanTree ht,char s[]){
	char *p = charnum;
	int key;
	HTNode g;
	while(*p!='\0'){
		g = ht[M - 1];
		while(g.lchild != -1 && g.rchild != -1 &&(*p != '\0')){
		//由于建立哈夫曼树的时候使用了第0号元素，如果初始化为
		// ht[i].lchild = 0;	ht[i].rchild = 0;
		//在此就需要判断（g.lchild != 0 && g.rchild != 0） 
		//如果这样做的话，由于ht[0]也存有元素，会导致程序逻辑错误
		//解决方法
		//1.初始化得时候将 ht[i].lchild = 0;	ht[i].rchild = 0;
		//改为ht[i].lchild = -1;	ht[i].rchild = -1; 
		//2. ht[i].lchild = 0;	ht[i].rchild = 0;不变，但是
		//ht[0]不能使用，从第一号元素开始建立哈夫曼树。 
			switch(*p){             
            case '0':key=g.lchild;
					 g=ht[g.lchild];
					 break;                  
            case '1':key=g.rchild;
					 g=ht[g.rchild];
					 break;
            }
            p++;
		}
		printf("%c\n",s[key]);
	} 
}
int main(){
	HuffmanTree ht;
	HuffmanCode hc; 
	int i;
	int w[N];
	char charcode[100];
	char charnum[100];
    char s[N]={'A','B','C','D','E','F'};
    printf("Please enter weights:");
	for( i = 0;i < N;i++){
		scanf("%d",&w[i]);
	}
	printf("Please enter the code:");
	scanf("%s", charcode);
	printf("Please enter the password:");
	scanf("%s",charnum);
	CrtHuffmanTree(ht,w,6);//建立哈夫曼树 
	CrtHuffmanCode(ht,hc,6);//哈夫曼编码，将每个字符得权值编成哈夫曼编码 
	printcode(s, hc);//将每个字符的哈夫曼编码输出 
	Alphagetnum(charcode,s,hc);//字符得到密码 
	printf("\n");
	Numgetalpha(charnum,ht,s);//密码得到字符 
}

收起

展开全文

C/C++ 哈夫曼树 创建和 BFS遍历算法
2020-06-08 17:19:17
一、哈夫曼树概述 哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的...
收起
数据结构二叉树 bfs 算法
C语言 哈夫曼树创建输出（静态链表）
2019-11-24 20:37:10
//创建哈夫曼树 void select(HuffmanTree ht,int n,int *s1,int *s2);//在前n个选项中选权值最小，且双亲为0的两个结点 main() { int n=5; HuffmanTree ht; int w[n]={5,7,3,2,8}; Create_HuffmanTree(ht,w,...
收起
算法_根据哈夫曼树创建哈夫曼编码（C/C++）
2020-03-05 18:06:00
文章结构：基本思路 + 代码实现基本思路：在根结点到叶子结点的路径上，从叶子结点开始依次...1）哈夫曼编码类型声明： typedef struct { int code[MaxSize]; int start; }HFCode; 2)实现算法： void creat...
收起
二叉树
哈夫曼树的创建
2018-09-01 17:01:49
实现哈夫曼树的创建算法，并按哈夫曼树实现哈夫曼编码算法。
收起
数据结构试验 哈夫曼树的创建及编码学生模板.rar
2012-06-01 11:00:42
数据结构试验 哈夫曼树 创建及编码学生模板源码
收起
哈夫曼树Huff的创建
2019-08-24 18:58:31
哈夫曼树的创建是基于堆来实现的，所以事先需要对堆有所了解，查看上篇博客QAQ。。 哈夫曼树树的建树原理，想必大家都知道，就是根据权值数组来建立的：过程是：1.从权值数组中挑选出两个最小的权值，建立两个树...
收起
关于java中哈夫曼树中创建哈夫曼树---循环报错数组下标越界
2021-01-28 15:30:18
在调用创建哈夫曼树方法时，当最后一层循环时判断条件second！=-1 报错数组下标越界 </p>
收起
java

哈夫曼树创建

哈夫曼树创建遍历

哈夫曼树创建（C++）笔记

JAVA数据结构与算法 11（3）树-哈夫曼树的基本介绍、哈夫曼树创建实现、哈夫曼编码、利用哈夫曼编码压缩

JAVA数据结构与算法 11.树

2 哈夫曼树

2.1 哈夫曼树的基本介绍

2.2 哈夫曼树创建实现

2.3 哈夫曼编码

2.4 利用哈夫曼编码压缩

哈夫曼树创建（.cpp )

哈夫曼树创建和哈夫曼码生成

哈夫曼树创建和译码

C/C++ 哈夫曼树创建和 BFS遍历算法

C语言哈夫曼树创建输出（静态链表）

算法_根据哈夫曼树创建哈夫曼编码（C/C++）