精华内容
下载资源
问答
  • 哈夫曼树的创建
    2022-04-11 21:42:59

    #define _CRT_SECURE_NO_WARNINGS

    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    typedef struct huffman {
        int weight;
        int parent, lchild, rchild;//parent放双亲再数组中的下标
    }Hufnode,*HufTree;

    typedef char** HuffmanCode;//动态二维数组,可看作若干个一维数组组成
    void Creat_Huffmancode(HufTree HT, HuffmanCode * HC, int n)//寻找字符对应的编码,我们从叶子结点出发
    //一直到根结点
    {
        *HC = (HuffmanCode)malloc((n + 1) * sizeof(char*));
        char* ch = (char*)malloc(n * sizeof(char));//森林有n个根结点,临时数组ch就需要n个空间
        //(实际是n-1,但最后一个存放'\0')
        ch[n - 1] = '\0';
        for (int i = 1; i <= n; i++)//n个森林中的根结点存放在哈夫曼树数组中的1-n中
        {
            int start = n - 1;
            int c = i;
            int f = HT[i].parent;
            while (f != 0)
            {
                start--;
                if (HT[f].lchild = c)
                    ch[start] = 0;
                else
                    ch[start] = 1;
                c = f;
                f = HT[f].parent;
            }
            (*HC)[i] = (char*)malloc((n - start) * sizeof(char));
            strcpy((*HC)[i], &ch[start]);//将临时数组中不为0的第一个元素开始复制到
        }
    }
    void select(HufTree HT, int i, int& s1, int& s2)//&是传址调用,会将形参中s1的值返回给实参
    {
        int min = 1;
        
        for (int n = 2; n <= i; n++)
        {
            if (HT[n].parent==0)//双亲是0表示是森林中的根结点
            {
                if ( HT[min].weight> HT[n].weight)//选取权最小的元素的下标
                    min = n;
            }
        }
        s1 = min;
        min = 1;
        for (int n = 2; n <= i; n++)
        {
            if (HT[n].parent==0&&n!=s1)//不能是权第一小元素的下标
            {
                if (HT[min].weight > HT[n].weight)
                    min = n;
            }
        }
        s2 = min;
    }
    HufTree Creat_HuffmanTree(int n)
    {
        int x;
        int m = 2 * n-1;
        HufTree HT;//定义一个指针,指针就相当于数组,把指针看作数组
        HT = (HufTree)malloc((m+1)*sizeof(Hufnode));//给数组开辟空间,数组中要放m+1个元素
        //初始化
        for (int i = 1; i <= m; i++)//从下标为1到m
        {
            HT[i].parent = 0;
            HT[i].lchild = 0;
            HT[i].rchild = 0;
        }
        for (int i = 1; i <= n; i++)
        {
            scanf_s("%d", &x);
            HT[i].weight = x;
        }
        int s1, s2;
        for (int i = n - 1; i <= m; i++)
        {
            select(HT, i-1,s1,s2);//选用两小造新树
            HT[s1].parent = i;
            HT[s2].parent = i;
            HT[i].lchild = s1;
            HT[i].rchild = s2;
        }
        return HT;
    }
    void Unite_Huffmancode(HufTree HT, int code[],int num,int n)//解码
    {
        int p=n;
        for (int i = 0; i < num; i++)
        {
            while (HT[p].lchild != 0)
            {
                if (code[i] = 0)
                    p = HT[p].lchild;
                else
                    p = HT[p].rchild;
            }
            printf("%d ", HT[p].weight);
            p = n;
        }
        
    }
    int main()
    {
        HufTree HT = Creat_HuffmanTree(3);


        return 0;
    }

    更多相关内容
  • 数据结构,哈夫曼树创建与先序遍历
  • 哈夫曼树创建

    2018-01-02 20:51:01
    这是我自己写的几个实习题目,可以用,也有思想,希望可以通过审核
  • 文章结构:基本思路 + 代码实现 基本思路: 在根结点到叶子结点的路径上,从叶子结点开始依次...1)哈夫曼编码类型声明: typedef struct { int code[MaxSize]; int start; }HFCode; 2)实现算法: void creat...
    文章结构:基本思路 + 代码实现
    1. 基本思路:
      在根结点到叶子结点的路径上,从叶子结点开始依次逆向判断每个结点是左还是右孩子,根据判断结果将编码存储到数组中,直到当前结点没有双亲结点——即根结点。

    2. 代码实现:

    1)哈夫曼编码类型声明:

    typedef struct
    {
    	int code[MaxSize];
    	int start;
    }HFCode;
    

    2)实现算法:

    void create_huffmancode(HFTree hft[], HFCode hfc[], int n0)
    {
    	int i, chd, prt;
    	HFCode cd;
    	for(i=0; i<n0; i++){
    		chd = i;
    		prt = hft[i].parent;
    //哈夫曼树最长叶子编码位数为叶子数-1
    		cd->start = n0-1;
    		cd->code[cd->satrt+1] = '\0';
    		while(prt != -1){
    			if(chd == hft[i].lchild)
    				cd->code[cd->start++] = 0;
    			else
    				cd->code[cd->start++] = 1;
    			chd = prt;
    			prt = hft[prt].parent;
    		}
    		cd->start++;
    		hfc[i] = cd;
    	}
    }
    
    展开全文
  • 主要介绍了C++实现哈夫曼树简单创建与遍历的方法,对于C++算法的学习来说不失为一个很好的借鉴实例,需要的朋友可以参考下
  • 通过 最小堆,来构建 哈夫曼树,再通过 遍历,借一个数组 来保存 路径 上的 编码。 #include<iostream> using namespace std; // 哈夫曼树节点 typedef struct huff{ int data; struct huff * left; ...

    通过 最小堆,来构建 哈夫曼树,再通过 遍历,借一个数组 来保存 路径 上的 编码。

    #include<iostream>
    using namespace std;
    // 哈夫曼树节点 
    typedef struct huff{
    	int data;
    	struct huff * left;
    	struct huff * right;
    }*huffman;
    
    // 最小堆 
    typedef struct zui_xiao_dui{
    	huffman elements[10];
    	int num;
    }*min_heap;
    
    // 创建 最小堆 
    min_heap Create(int num){
     	min_heap H=new struct zui_xiao_dui;
    // 	H->elements=new huffman[num+1];	// 从 下标为 1 的地方开始存放 
     	H->num=0;
    //  这里 由于 H->elements[0]中的元素 指向的地方未初始化
    //  所以切记 不可以 直接 H->elements[0]->data=-10;
    	huffman temp=new struct huff;
     	H->elements[0]=temp;
    	H->elements[0]->data=-10;		// 定义哨兵 , 这里放一个很小的数 
     	return H;
     } 
     
    // 将 H中以 H->Data[p]为根的子堆调整为最大堆 
    void PercDown( min_heap H, int p ){ 
        int Parent, Child;
        int X;
        X = H->elements[p]->data; 
    	huffman temp=H->elements[p];	//  这里 注意 保存								
        for( Parent=p; Parent*2<=H->num; Parent=Child ) {
            Child = Parent * 2;
            if( (Child!=H->num) && (H->elements[Child]->data>H->elements[Child+1]->data) )
                Child++;  /* Child指向左右子结点的较小者 */
            if( X <= H->elements[Child]->data ) 
    			break; 										//  找到了合适位置 
            else  											 
                H->elements[Parent] = H->elements[Child];			//  将那个较大值调上来, 之后在下一层继续找
        }
        H->elements[Parent] = temp;
    }
    void BuildHeap( min_heap H ){
        int i;
        for( i = H->num/2; i>0; i-- )
            PercDown( H, i );
    }
    
    // 取出 最小堆 的最小节点 
    huffman DeleteMin(min_heap H){
    	int parent,child;
    	huffman MinItem,temp;
    	MinItem=H->elements[1];			// 取出最小元素
    	temp=H->elements[H->num--];	// 指向 最后一个元素 
    	
    	//寻找 temp 应该放置的地方: parent, 先放在 根节点, 然后 逐层的 寻找 合适的位置
    	for(parent=1;parent*2<=H->num;parent=child){
    		child=parent*2;
    		if((child!=H->num)&&(H->elements[child]->data>H->elements[child+1]->data))
    			child++;					//  找出 左右儿子 中 较小的一个 
    		if(temp->data<=H->elements[child]->data)	//  如果 temp 比 这个位置的左右儿子 都大, 那 temp 放在这里就是合适的
    			break;
    		else
    			H->elements[parent]=H->elements[child];
    	}
    	H->elements[parent]=temp;
    	return MinItem;
    }
    // 向 堆中 插入元素
    void Insert(min_heap H,huffman item){
    // H->Elements[0] 已被 设置为 哨兵 
    	int i;
    	i=++H->num; 
    	for(;H->elements[i/2]->data>item->data;i/=2){			//  将 比 item 大的 父节点元素 向下移 
    		H->elements[i]=H->elements[i/2];	 
    	}
    	H->elements[i]=item;	// 找到要插入的位置 
    }
    
    // 建立 哈夫曼 树 
    huffman huffman_build(min_heap H){
    	huffman T;
    	BuildHeap(H);			//  调整为最小堆 	       O(n) 复杂度 
    	int count=H->num;
    	for(int i=1;i<count;i++){			// Size-1 次 合并
    		T=new struct huff;
    		T->left=DeleteMin(H);	//  从堆中 取出两个 最小的 
    		T->left->data;
    		T->right=DeleteMin(H);
    		T->right->data;
    		T->data=T->left->data+T->right->data;
    		Insert(H,T); 	// 构建形成的新的节点插入到堆里 
    	}
    	T=DeleteMin(H);
    	return T;
    }
    
    // len 是 路径长
    // bian_ma 数组里放的是 编码
    void Mid_order(huffman L, int (&bian_ma)[10],int &len){
    	if(L){
    		if(L->left==NULL&&L->right==NULL){
    			cout<<L->data<<ends;
    			for(int j=0;j<len;j++){
    				cout<<bian_ma[j];
    			}
    			cout<<'\n';
    			len--;
    			return;
    		}
    		bian_ma[len++]=0;
    		Mid_order(L->left,bian_ma,len);
    		bian_ma[len++]=1;
    		Mid_order(L->right,bian_ma,len);
    		len-=1;
    	}
    }
    
    int main(){
    	int num;
    	cin>>num; // 元素个数
    	min_heap P=Create(num);				// 建 堆
    	for(int i=1;i<num+1;i++){
    		huffman jie_dian =new struct huff;
    		cin>>jie_dian->data;
    		jie_dian->left=jie_dian->right=NULL;
    		P->elements[i]=jie_dian;
    		P->num++;
    	}
    	huffman L=huffman_build(P);			// 建 哈夫曼树
    	static int bian_ma[10]={0};
    	static int len=0;
    	Mid_order(L,bian_ma,len);			//  遍历
    
    }
    

    在这里插入图片描述
    在这里插入图片描述

    展开全文
  • 2.根据创建好的哈夫曼树创建一张哈夫曼编码表 3.输入一串哈夫曼序列,输出原始字符 三.设计思想: 1.首先要构造一棵哈夫曼树,哈夫曼树的结点结构包括权值,双亲,左右孩子;假如由n个字符来构造一棵哈夫曼树,则...
  • 哈夫曼树创建遍历

    2012-09-18 13:12:21
    程序代码包括创建二叉树,遍历树,创建哈夫曼树,打印哈夫曼树叶子节点的路径。
  • 哈夫曼树创建

    2021-11-05 11:35:44
    创建哈夫曼树2.1 创建树节点TreeNode2.2 构建哈夫曼树2.3 测试 1. 什么是哈夫曼树 2. 创建哈夫曼树 2.1 创建树节点TreeNode //树的节点 public class TreeNode { /** * 值 * 左右孩子 */ private int value; ...

    哈夫曼树

    1. 什么是哈夫曼树

    在这里插入图片描述

    2. 创建哈夫曼树

    2.1 创建树节点TreeNode

    //树的节点
    public class TreeNode {
        /**
         * 值
         * 左右孩子
         */
        private int value;
        public TreeNode left;
        public TreeNode right;
    
        public TreeNode() {
    
        }
    
        public TreeNode(int value) {
            this.value = value;
        }
    
        public int getValue() {
            return value;
        }
    
    }
    

    2.2 构建哈夫曼树

      首先,需要一个list来储存所有要被创建的节点,这里我是用LinkedList来实现List接口。创建完毕,就要对这个list初始化。
    构建步骤:

    • 创建list,以及根节点root,对list进行初始化。
    • 对list进行升序排序,目的是为了找出value最小的两个节点。(我这里为了方便,用的选择排序,可以试试手撕快排)
    • 取出list最小的两个节点,然后创建父节点,再子父相连 。(一定要子父相连)
    • 最后,初始化根节点。
    • (后面中序遍历是为了测试建树是否正确)
    //哈夫曼树
    public class HfmTree {
    
        public TreeNode root = new TreeNode();
        public List<TreeNode> list = new LinkedList<>();
    
        public HfmTree() {
        }
    
        public HfmTree(int[] value) {
            for(int val:value){
                list.add(new TreeNode(val));
            }
        }
    
        //排序
        public void sort(){
            for(int i=0; i<list.size()-1; i++)
                for(int j=i+1; j<list.size(); j++){
                    if(list.get(i).getValue() > list.get(j).getValue()){
                        TreeNode node = list.get(i);
                        list.set(i,list.get(j));
                        list.set(j,node);
                    }
                }
        }
    
        public void creatTree() {
            while(list.size() > 1) {
                //排序
                sort();
                //取最小的两个
                TreeNode left = list.remove(0);
                TreeNode right = list.remove(0);
    
                TreeNode node = new TreeNode(left.getValue() + right.getValue());
                //建立子父联系
                node.left = left;
                node.right = right;
                //新节点加入List中
                list.add(node);
    
            }
            //把根节点初始化
            root = list.remove(0);
        }
    
        //中序遍历
        public void inOrder(TreeNode root) {
            if(root != null) {
                if(root.left != null) {
                    inOrder(root.left);
                }
                System.out.print(root.getValue()+" ");
                if(root.right != null) {
                    inOrder(root.right);
                }
            }
        }
    }
    

    2.3 测试

    代码如下:

    public class TestHfmTree {
    
        public static void main(String[] args) {
    
            int[] value = {1,6,5,8,4};
            //初始化
            HfmTree hfmTree = new HfmTree(value);
            //构建hfm树
            hfmTree.creatTree();
            //中序遍历
            hfmTree.inOrder(hfmTree.root);
        }
    }
    

    输出结果:
    在这里插入图片描述
    “手动建树”:
    在这里插入图片描述
    中序遍历:5 10 1 5 4 24 6 14 8,与输出相同,说明哈夫曼树构建正确。

    展开全文
  • } } void PrintHuffTree(HTNode ht[],int n0) { //输出哈夫曼树 int i,n; printf("\n哈夫曼树各项数据如下表所示:\n"); printf(" 结点i weight parent lchid rchild\n"); for(i=1;i*n0;i++) printf("\t%d\t%d\t%d...
  • 本文实例为大家分享了C++实现哈夫曼树的编码解码,供大家参考,具体内容如下 代码: #pragma once #include #include using namespace std; #define m 20 stack<int> s; /*哈夫曼树结点类HuffmanNode声明*/ ...
  • C++实现哈夫曼树算法

    2020-12-20 18:16:44
    如何建立哈夫曼树的,网上搜索一堆,这里就不写了,直接给代码。 1.哈夫曼树结点类:HuffmanNode.h #ifndef HuffmanNode_h #define HuffmanNode_h template struct HuffmanNode { T weight; // 存储权值 ...
  • 哈夫曼树创建(.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 ...
  • 主要为大家详细介绍了C语言实现哈夫曼树的构建,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • ###哈夫曼树创建和遍历import java.util.*;public class huffman{public static void main(String[] args){int []arr={13,7,8,3,29,6,1};Node root=huff(arr);//前序遍历打印赫夫曼树if(root!=null){System.out....
  • 2 哈夫曼树 2.1 哈夫曼树的基本介绍 ​ 给定n个权值作为n个叶子结点,构造一颗二叉树,若该树的带权路径长度(WPL)达到最小,称这样的二叉树为最优二叉树,也称哈夫曼树。因此权值较大的结点距离根节点较近。 ...
  • 哈夫曼树python实现

    2022-04-10 20:08:30
    文章目录HuffmanTree的python实现 -- 潘登同学的图论笔记哈夫曼树构建哈夫曼树的过程树节点实现HuffmanTree实现绘制HuffmanTree测试代码 哈夫曼树 当用 n 个结点(都做叶子结点且都有各自的权值)试图构建一棵树时,...
  • 哈夫曼树创建和译码

    2019-12-10 08:39:29
    题目描述 假设某通信报文的字符集由A,B,C,D...构建哈弗曼时:左子树根结点权值小于等于右子根结点权值。 生成编码时:左分支标0,右分支标1。 输入 第一行:依次输入6个整数,依次代表A,B,C,D,E,F的频度,用空格...
  • //创建哈夫曼树 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,...
  • 哈夫曼树的构建

    2022-07-20 17:48:47
    哈夫曼树的构建
  • 一、哈夫曼树概述 哈夫曼树又称最优二叉树,是一种带权路径长度最短的二叉树。 所谓树的带权路径长度,就是树中所有的叶结点的权值乘上其到根结点的路径长度(若根结点为0层,叶结点到根结点的路径长度为叶结点的...
  • 好,前面我们介绍了一般二叉树、完全二叉树、满二叉树,这篇文章呢,我们要介绍的是哈夫曼树哈夫曼树也叫最优二叉树,与哈夫曼树相关的概念还有哈夫曼编码,这两者其实是相同的。哈夫曼编码是哈夫曼在1952年提出的...
  • 哈夫曼树构建

    2021-01-08 03:14:38
    哈夫曼树是带权值的树节点结构,且目标节点都存储在叶子节点上。下面使用Go实现哈夫曼树 哈弗曼树构建过程 将带权值的节点进行排序,形成有序的链表。 取出链表头两个节点,权值相加形成新节点,并加入上述链表中...
  • //初始化哈夫曼树结点 void GetMin(HTreeNode* array , int start, int end, int &s1, int &s2); //取两个权重最新的结点 void CreateHTree(HTreeNode* array , int num); //创建哈弗曼树 ...
  • 哈夫曼树原理 秉着能不写就不写的理念,关于哈夫曼树的原理及其构建,还是贴一篇博客吧。 https://www.jb51.net/article/97396.htm 其大概流程 哈夫曼编码代码 # 树节点类构建 class TreeNode(object): def __...
  • 利用哈夫曼树进行文件压缩与解压

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 7,706
精华内容 3,082
关键字:

哈夫曼树的创建