精华内容
下载资源
问答
  • 给定N个权值作为N个叶子结点,构造一棵二叉树,若该的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼(Huffman Tree)。哈夫曼是带权路径长度最短的,权值较大的结点离根较近。
  • c语言构造哈夫曼-哈夫曼编码

    万次阅读 多人点赞 2018-12-05 14:59:59
    构造哈夫曼 首先,我们需要了解哈夫曼是什么: 一.相关知识点 路径: 路径是指从一个节点到另一个节点的分支序列。 路径长度: 指从一个节点到另一个结点所经过的分支数目。 ,从根节点到a的分支数目是2, 数...

    构造哈夫曼树
    首先,我们需要了解哈夫曼树是什么:

    一.相关知识点
    路径: 路径是指从一个节点到另一个节点的分支序列。
    在这里插入图片描述
    路径长度: 指从一个节点到另一个结点所经过的分支数目。 ,从根节点到a的分支数目是2,
    在这里插入图片描述
    数的路径长度: 树中所有结点的路径长度之和为树的路径长度PL 如图pl为10
    在这里插入图片描述
    节点的权: 给树的每个结点赋予一个具有某种实际意义的实数,我们称该实数为这个结点的权
    在这里插入图片描述
    带权路径长度: 从树根到某一结点的路径长度与该节点的权的乘积,叫做该结点的带权路径长度
    树的带权路径长度: 树的带权路径长度为树中所有叶子节点的带权路径长度之和。

    路径长度为0,最多有一个(根)
    路径长度为1,最多有2个(两个孩子)
    路径长度为2,最多有4个叶结点。
    

    构造Huffman树的步骤:
    1) 根据给定的n个权值,构造n棵只有一个根结点的二叉树,n个权值分别是这些二叉树根结点的权;
    2) 设F是由这n棵二叉树构成的集合,在F中选取两棵根结点权值最小的树作为左、右子树,构造成一颗新的二叉树,置新二叉树根结点的权值等于左、右子树根结点的权值之和。为了使得到的哈夫曼树的结构唯一,规定根结点权值最小的作为新二叉树的左子树。
    3) 从F中删除这两棵树,并将新树加入F;
    4) 重复2)、3)步,直到F中只含一棵树为止,这棵树便是Huffman树。
    说明:n个结点需要进行n-1次合并,每次合并都产生一个新的结点,最终的Huffman树共有2n-1个结点。
    如何构建哈夫曼树:在网上找了个比较好用的图片:
    在这里插入图片描述
    如上即可较为清晰的理解最优二叉树的构造了。
    三.哈夫曼树代码的实现。

    我们给出5个值为:2   3   5   7   8的权值,构造最优二叉树。
    从上图可以看出:我们有权值:weight,左右孩子:LChild,RChild,双亲结点:parent,
    

    所以:我们构成了一个哈夫曼树的结点结构HTNode:

    Typedef struct
    	{
    		Int weight;
    		Int parent , LChild,RChild;
    }HTNode, *HuffmanTree;
    
    void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n){//根据输入的结点的权值和个数来构建赫夫曼树 
    	int m=2*n-1;//n个叶子,有2*n-1个结点 
    	int i;	HuffmanTree   p;
    	for(p=HT+1,i=1;i<=n;i++,p++,w++) {//叶子结点赋值 
    	p->weight=*w;p->parent=0;p->lchild=0;p->rchild=0;
    

    在这里插入图片描述

    	}
    	for(;i<=m;i++,p++) {//非叶子结点初始化 
    	p->weight=0;p->parent=0;p->lchild=0;p->rchild=0;
    	} 此图为上述两个循环的意思。
    	for(i=n+1;i<=m;i++){循环次数为n-1次,进行构造哈夫曼树。
    	select(ht,i-1,&s1,&s2);
    	/*选择parent为0且weight最小的两个结点,其序号分别赋值给s1,s2*/
    	ht[s1].parent=i;
    	ht[s2].parent=i;
    	ht[i].Lchild=s1;
    	ht[i].Rchild=s2;
    	上述代码是先找出两个最小值,先将其合并,构造出一个有根节点和两个左右结点的树,再取出其根节点再次合并
    	ht[i].weight=ht[s1].weight+ht[s2].weight;
    	/*哈夫曼树建立完毕*/
    	
    最后得出: 
    

    在这里插入图片描述

    	}
    /*从叶子节点到根逆向求每个字符或者指令的哈夫曼编码*/
    	hc=(haffmancode)malloc(n*sizeof(char*));申请一个字符给指针,字符的区域hc
    给hc分配n个字符编码的头指针	
    /*分配n个字符编码的头指针*/ 
    	cd=(char*)malloc(n*sizeof(char));cd为中间辅助单元,n个结点的位置为cd
    	cd[n-1]='\0';cd的最后一位为编码结束符, 
    	for(j=0;j<n;j++){n次循环,
    	start=n-1;
    	for(c=j;f=ht[j].parent;f!=0;c=f,f=ht[f].parent)
    		/*从叶子到根结点求编码*/
    		if(ht[f].Lchild==c) cd[--start]='0';
    		else cd[--start]='1';
    		hc[j]=(char*)malloc((n-start)*sizeof(char));
    		/*为第j个指令编码分配空间*/
    		strcpy(hc[j],&cd[start]);
    

    下面给出具体实现代码:

    #include<stdio.h>
    #include<iostream>
    #include<stdlib.h>
    #include<string.h>
    #include<algorithm>
    #define MAX_NUM 100//最大数字个数为100
    #define inf 2000000000 //最大值为
    using namespace std;
    typedef struct {
    	unsigned int weight;//权值 
    	unsigned int parent,lchild,rchild;//父节点,孩子结点的权值 
    }HTNode,*HuffmanTree;
    typedef char * * HuffmanCode;//二维字符数组 
    int s1,s2;//最小的两个结点 
    
    
    
    
    
    
    
    
    
    void Select(HuffmanTree &HT,int x){//选出无父结点,并且权值最小的两个结点,赋值给s1,s2 
    	int i,min1=inf,min2=inf;
    	for(i=1;i<=x;i++){//找最小 
    		if(HT[i].weight<min1&&HT[i].parent==0){min1=HT[i].weight;s1=i;}
    	}
    	for(i=1;i<=x;i++){//找次小 
    		if(HT[i].weight<min2&&i!=s1&&HT[i].parent==0){
    			min2=HT[i].weight;s2=i;
    		}
    	}
    }
    
    
    
    
    
    
    
    
    
    
    void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n){//根据输入的结点的权值和个数来构建赫夫曼树 //创建数 和编码的地址
    	if(n<=1)return;
    	int m=2*n-1;//n个叶子,有2*n-1个结点 
    	int i;
    	HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0号单元未用 开辟空间
    	HuffmanTree p;
    	for(p=HT+1,i=1;i<=n;i++,p++,w++) {//叶子结点赋值 
    	p->weight=*w;p->parent=0;p->lchild=0;p->rchild=0;
    	}
    	for(;i<=m;i++,p++) {//非叶子结点初始化 
    	p->weight=0;p->parent=0;p->lchild=0;p->rchild=0;
    	}
    	for(i=n+1;i<=m;i++){
    		Select(HT,i-1);//选出最小的两个无父节点的结点 
    		HT[s1].parent=i;HT[s2].parent=i;
    		HT[i].lchild=s1;HT[i].rchild=s2;
    		HT[i].weight=HT[s1].weight+HT[s2].weight;
    	}
    	//----------下面是将每个结点的赫夫曼编码存入二维字符数组
    	
    
    
    
    	HC=(HuffmanCode)malloc((n+1)*sizeof(char *));//申请一段以HC为首地址的内存,可以看成二维字符数组 ,这里先申请了第一维 
    	char *cd=(char *)malloc(n*sizeof(char));//申请一段临时工作空间 
    	cd[n-1]='\0';//编码结束符 
    	for(i=1;i<=n;i++){
    		int start=n-1,c,f;
    		for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent){//从叶子到根逆向求编码 
    			if(HT[f].lchild==c)cd[--start]='0';//如果当前结点是父节点的左孩子,则存一个1 
    			else cd[--start]='1';//反之 
    		}
    		HC[i]=(char *)malloc((n-start)*sizeof(char));//申请第二维 
    		strcpy(HC[i],&cd[start]);//将编码从工作空间存入赫夫曼编码表中 
    	}
    	free(cd); //释放临时空间 
    }
    
    
    
    
    
    
    
    
    
    int main(){
    	HuffmanTree HT;//自定义结构体  ht
    	HuffmanCode HC;
    	int w[MAX_NUM],n;
    	int i;
    	printf("输入结点的个数:\n"); 
    	scanf("%d",&n);
    	printf("输入每个结点的权值:\n");
    	for( i=0;i<n;i++)
    	scanf("%d",&w[i]);
    	HuffmanCoding(HT,HC,w,n);
    	for( i=1;i<=n;i++)
    	printf("%d的赫夫曼编码为:%s\n",HT[i].weight,HC[i]);
    	return 0;
    } 
    

    因为刚好学到这里,便做了个总结。

    展开全文
  • C语言构造哈夫曼、哈夫曼编码

    千次阅读 2019-04-22 20:20:15
    1.构造哈夫曼 #include <stdio.h> #include <stdlib.h> #define MAXVALUE 10000 /* 节点最大权值 */ #define MAXLEAF 30 /* 哈夫曼叶子节点最大个数 */ #define MAXNODE MAXLEAF * 2 - 1 /* ...

    四个叶子节点{1,3,5,5},构造Huffman树,并进行Huffman编码
    设编码时:左分支为‘0’,右分支为‘1’

    0
    1
    0
    1
    0
    1
    14
    5
    9
    4
    5
    1
    3
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    #define MAXVALUE 10000           // 节点最大权值
    #define MAXLEAF  30              // 哈夫曼树叶子节点最大个数
    #define MAXNODE  MAXLEAF * 2 - 1 // Huffman树中节点总数
    typedef struct {
        int weight; // 节点权值
        int parent; // 无双亲节点时为-1,否则为双亲节点下标
        int lchild; // 无左孩子时为-1,否则为左孩子下标
        int rchild; // 无右孩子时为-1,否则为右孩子下标
    } HNode, HuffmanTree[MAXNODE];
    
    typedef struct CodeNode // 编码表的存储结构
    {
        int weight; // 存放要表示的符号
        char *code; // 存放相应符号编码
    } CodeNode, HuffamanCode[MAXLEAF];
    
    /*
     * @description: 构造Huffman树
     * @param w[]:传递n个叶子节点权值
     *          n:叶子节点个数
     */
    void CreateHuffmanTree(HuffmanTree HTree, int w[], int n)
    {
        /*
         * min1: 集合中最小权值
         * min1: 集合中次小权值
         * index1:最小权值节点下标
         * index2:次小权值节点下标
         */
    
        int i, j, min1, min2, index1, index2;
        // 树中节点初始化
        for (i = 0; i < 2 * n - 1; i++) {
            HTree[i].weight = 0;
            HTree[i].parent = -1;
            HTree[i].lchild = -1;
            HTree[i].rchild = -1;
        }
    
        for (i = 0; i < n; i++)
            HTree[i].weight = w[i];
        printf("Huffman树初态\nindex | weight | parent | lchild | rchild\n");
        for (i = 0; i < 2 * n - 1; i++) {
            printf("%3d%9d%9d%9d%9d\n", i, HTree[i].weight, HTree[i].parent,
                   HTree[i].lchild, HTree[i].rchild);
        }
        /*
         * 设n0(叶子节点)、n1(分支为1)、n2(分支为2)分别为二叉树中度为0、1、2的节点个数,
         * n为总节点个数,则 n = n0 + n1 + n2;
         * 设二叉树分支数为B,则 B = n + 1, B = n1 + 2 * n2;
         * 联立上述三个方程--->n0 = n2 + 1;
         *
         * Huffman树中只有度为0、2的节点:
         * n = n0 + n1 + n2 = n0 + n2;
         * n0 = n2 + 1;
         * Huffman树中:n = 2 * n0 - 1.
         */
        // 构造除n个叶子节点外的其余 n - 1 个双亲节点
        for (i = 0; i < n - 1; i++) {
            min1 = min2 = MAXVALUE;
            index1 = index2 = 0;
    
            for (j = 0; j < n + i; j++) {
                // 若节点权值比min1小且该节点无双亲节点,则更新最小节点
                if (HTree[j].weight < min1 && HTree[j].parent == -1) {
                    min2 = min1;
                    index2 = index1; // 更新次小节点
                    index1 = j;
                    min1 = HTree[j].weight;
                }
                // 若 min1 < 节点权值 < min2, 且该节点无双亲节点,则更新次小节点
                else if (HTree[j].weight < min2 && HTree[j].parent == -1) {
                    index2 = j;
                    min2 = HTree[j].weight;
                }
            }
    
            HTree[index1].parent = n + i;
            HTree[index2].parent = n + i;
            HTree[n + i].weight = HTree[index1].weight + HTree[index2].weight;
            HTree[n + i].lchild = index1;
            HTree[n + i].rchild = index2;
        }
    }
    
    /*
     * 从叶子节点-->根节点逆向搜索,若当前节点是其双亲左孩子,置‘0’,否则置‘1’
     * @param:HTree:构造好的Huffman树
     *         HCode:Huffman树叶子节点编码
     *      n:叶子节点个数
     */
    void HuffmanCoding(HuffmanTree HTree, HuffamanCode HCode, int n)
    {
        char *cd;
        int i, child, parent, start;
    
        // n个叶子节点的Huffman树,叶子节点最长路径为 n-1,加上'\0',共n个空间
        cd = (char *)malloc(n * sizeof(char));
        cd[n - 1] = '\0';
    
        // 求n个叶子节点的Huffman编码
        for (i = 0; i < n; i++) {
            start = n - 1;
            child = i;                // child:当前节点下标
            parent = HTree[i].parent; // parent:当前节点双亲节点下标
    
            // 若未搜寻至根节点,则一直循环
            while (parent != -1) {
                start--;
                if (HTree[parent].lchild == child)
                    cd[start] = '0'; // 左孩子,置‘0’
                else
                    cd[start] = '1'; // 右孩子,置‘1’
    
                child = parent; // 旧双亲节点作为新孩子节点
                parent = HTree[parent].parent; // 旧双亲节点的双亲节点作为新双亲节点
            }
    
            HCode[i].code = (char *)malloc((n - start) * sizeof(char));
            HCode[i].weight = HTree[i].weight;
            strcpy(HCode[i].code, &cd[start]);
        }
        free(cd);
    }
    
    int main(void)
    {
        int w[] = {1, 3, 5, 5}, n = 4;
        HuffmanTree ht;
        HuffamanCode hc;
    
        CreateHuffmanTree(ht, w, n);
        printf("Huffman树终态\nindex | weight | parent | lchild | rchild\n");
        for (int i = 0; i < 2 * n - 1; i++) {
            printf("%3d%9d%9d%9d%9d\n", i, ht[i].weight, ht[i].parent, ht[i].lchild,
                   ht[i].rchild);
        }
    
        HuffmanCoding(ht, hc, n);
        printf("Huffman编码\n节点值  编码\n");
        for (int i = 0; i < n; i++) {
            printf("%4d\t%s\n", hc[i].weight, hc[i].code);
        }
    
        return 0;
    }
    
    
    

    在这里插入图片描述

    展开全文
  • 许多打印在最后没有注释掉,是debug时用的,参考了一些其他的博客,可以睡了,明天有是新的一周 #include <stdio.h> #include <stdlib.h> #define LEN 3 typedef struct Huffman.../*创建Huffman*/ Huffm

    许多打印在最后没有注释掉,是debug时用的,参考了一些其他的博客,可以睡了,明天有是新的一周

    #include <stdio.h>
    #include <stdlib.h>
    #define LEN 3
    typedef struct Huffman{
        int weight; //权重
        struct Huffman* lch;
        struct Huffman* rch;
    }HuffmanNode,*HuffmanTree;
    
    /*创建Huffman树*/
    HuffmanTree CreateHuffman(int m[],int n);
    /*寻找当前节点的最小与次小,返回节点下标*/
    void Select(HuffmanTree HPtr[],int n,int* k1,int* k2);
    /*先序遍历打印二叉树*/
    void PreOrder(HuffmanTree HPtr);
    /*打印二叉树*/
    void PrintTree(HuffmanTree T,int i);
    int main()
    {
        printf("1234\n");
        int n = 6;
        int w[6] = {0,1,2,3,4,5};
        printf("1234\n");
        HuffmanTree HPtr = CreateHuffman(w,n);
        printf("Hello world!\n");
        printf("%d\n",HPtr->weight);
        PreOrder(HPtr);
        printf("\nHello world!\n");
        PrintTree(HPtr,LEN);
        return 0;
    }
    /*创建Huffman树*/
    HuffmanTree CreateHuffman(int w[],int n)
    {
        printf("我进来了\n");
       HuffmanTree H_all[n];//保存节点
       int i,k1,k2;
       HuffmanTree H_root = NULL;//合并所用的根结点
       printf("准备初始化\n");
       printf("n = %d\n准备打印数组\n");
       for(i = 0;i < n;i++)
        printf("%d ",w[i]);
       printf("\n");
       /*初始化节点*/
       for(i = 0;i < n;i++)
       {
           printf("i = %d\n",i);
           H_all[i] = (HuffmanTree)malloc(sizeof(HuffmanNode)); //malloc
           if(!H_all[i]) exit(-1); //defeat
           (H_all[i]->weight) = w[i];
           (H_all[i]->lch) = NULL;
           (H_all[i]->lch) = NULL;
       }
       /*合并节点,需要合并n-1次*/
       printf("已经初始化完成\n");
       for(i = 1;i < n;i++)
       {
           /*找到最小值k1.次小值k2*/
           Select(H_all,n,&k1,&k2);
           /*申请结点*/
           H_root = NULL;
           H_root = (HuffmanTree)malloc(sizeof(HuffmanNode));//申请内存
           if(!H_root) exit(-1);//失败
           /*合并*/
           H_root->weight = H_all[k1]->weight + H_all[k2]->weight;
           H_root->lch = H_all[k1];
           H_root->rch = H_all[k2];
           /*将合并后的节点移植到k1,把k2置空*/
           H_all[k1] = H_root;
           H_all[k2] = NULL;
           int j;
           for(j = 0;j < n;j++)
           {
               if(H_all[j])
                printf("H_all[%d]->weight = %d\n",j,H_all[j]->weight);
           }
       }
       return H_root;
    }
    /*寻找当前节点的最小与次小,返回节点下标*/
    void Select(HuffmanTree HPtr[],int n,int* k1,int* k2)
    {
        int i;
        (*k1) = -1;
        for(i = 0;i < n;i++)
        {
            if(HPtr[i] && (*k1) == -1)
            {
                (*k1) = i;
            }
            if(HPtr[i] && HPtr[i]->weight < HPtr[*k1]->weight)
            {
                (*k1) = i;
            }
        }
        (*k2) = -1;
        printf("k1 = %d ",(*k1));
        for(i = 0;i < n;i++)
        {
            if(i != (*k1) && HPtr[i] && (*k2) == -1)
            {
                (*k2) = i;
                printf("1~k2 = %d ",(*k2));
            }
            if((*k2) != -1 && HPtr[i] && HPtr[i]->weight < HPtr[*k2]->weight && i != (*k1))
            {
                (*k2) = i;
                printf("2~k2 = %d ",(*k2));
            }
        }
        printf("select函数运行结果:k1=%d,k2=%d\n",(*k1),(*k2));
    }
    /*先序遍历打印二叉树*/
    void PreOrder(HuffmanTree HPtr)
    {
        if(HPtr)
        {
        printf("%d ",HPtr->weight);
        PreOrder(HPtr->lch);
        PreOrder(HPtr->rch);
        }
    }
    void PrintTree(HuffmanTree T,int i)
    {
        if(T != NULL)
        {
            PrintTree(T->rch,i+LEN);
            printf("%*d\n",i,T->weight);
            PrintTree(T->lch,i+LEN);
            i -= LEN;
        }
    }
    
    
    
    
    展开全文
  • c语言哈夫曼树构造代码 博主就很掘的一个人,最近学哈夫曼,想着用指针去实现,觉得用指针实现,内存消耗会更少,写到后面发现越来与麻烦,且内存开销并没有减少,于是还是使用结构体数组中规中矩的去实现哈夫曼...

    c语言哈夫曼树构造代码

    博主就很掘的一个人,最近学哈夫曼树,想着用指针去实现,觉得用指针实现,内存消耗会更少,写到后面发现越来与麻烦,且内存开销并没有减少,于是还是使用结构体数组中规中矩的去实现哈夫曼树,博主不爱看别人的代码,知道原理便直接上手实现,所以,我的代码往往更加简单,因为,自己写,越简单越好,谁愿意写复杂的代码呢,学习哈夫曼树得小伙伴可以学习学习下面的代码。

    #include<stdio.h>
    #include<stdlib.h>
    
    typedef struct Tree {
    	int data = -1;
    	int parent = -1;
    	int  lchild = -1;
    	int rchild = -1;
    
    }Tree;
    
    void InitHuffmanTree(Tree HT[],int a[],int n) {
    	int i;
    	for (i = 0; i < n; i++) {
    		HT[i].data= a[i];
    	//	HT[i].rchild = NULL;
    		//HT[i].lchild = NULL;
    	}
    
    }
    
    void HuffmanTree_print(Tree HT[], int  n ) {
    
    	int i;
    	for (i = 0; i < n; i++) {
    		printf("%d ", HT[i].data);
    	//	printf("%d ", HT[i].parent);
    	}
    }
    void select(Tree HT[],int n) {
    	int min1, min2, min1_index, min2_index;
    	int ju1=0 ,ju2=0;
    	for (int i = 0; i < n; i++) {
    		if (HT[i].parent == -1 && ju1==0) {
    			min1 = HT[i].data;
    			min1_index = i;
    			ju1 = 1;
    
    		}
    		if (HT[i].parent == -1 && ju1 != 0&& min1> HT[i].data) {
    			min1 = HT[i].data;
    			min1_index = i;
    		}
    	}
    	HT[min1_index].parent = n;
    	for (int i = 0; i < n; i++) {
    		if (HT[i].parent == -1 && ju2 == 0) {
    			min2 = HT[i].data;
    			min2_index = i;
    			ju2 = 1;
    
    		}
    		if (HT[i].parent == -1 && ju2 != 0 && min2 > HT[i].data) {
    			min2 = HT[i].data;
    			min2_index = i;
    			
    
    		}
    	}
    	HT[min2_index].parent = n;
    	HT[n].data = HT[min2_index].data + HT[min1_index].data;
    
    	HT[n].lchild = min1_index;
    	HT[n].rchild = min2_index;
    	
    	//printf("%d", HT[n].data);
    
    }
    
    void CreateHuffmanTree(Tree HT[], int n) {
    	int min1, min2, min1_index, min2_index;
    	int i;
    	for (i = n; i < 2 * n - 1; i++) {
    		select(HT, i);
    		HuffmanTree_print(HT, i);
    		printf("\n");
    	}
    	
    }
    void HuffmanTree_erfodic(Tree HT[], int top) {
    	
    	printf("%d ", HT[top].data);
    	if (HT[top].lchild != -1) {
    		HuffmanTree_erfodic(HT,HT[top].lchild);
    	}
    	if (HT[top].rchild != -1) {
    		HuffmanTree_erfodic(HT,HT[top].rchild);
    	}
    
    }
    
    int main() {
    	Tree* T=NULL;
    	int i;
    	int a[] = { 4,6,7,2,5,8,6,9 };
    	
    	Tree HT[16];
    	//sort_data(a, 8);
    	InitHuffmanTree(HT, a, 8);
    	CreateHuffmanTree(HT, 8);
    	//HuffmanTree_print(HT, 8);
    	
    	//data_print(a, 8);//输出数组元素
    	//createTree(T);
    	HuffmanTree_erfodic(HT,14);
    	printf("\n%d ", T);//输出树的根节点地址
    	return 0;
    
    }
    
    展开全文
  • 哈夫曼(霍夫曼)又称为最优树.1、路径和路径长度在一棵中,从一个结点往下可以达到的孩子或孙子结点之间的通路,称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1,则从根结点到第L层结点的路径...
  • c语言实现构造哈夫曼 输入字符和权值,实现哈夫曼构造 #include<stdio.h> #include<string.h> #include<stdlib.h> #define MAXSIZE 50 typedef char DataType; typedef struct // 哈夫曼...
  • C语言构造哈夫曼编码

    2020-09-28 16:35:28
    首先我们定义两个结构体,一个用于定义哈夫曼的结点,一个用来定义每个叶子结点的哈夫曼编码. typedef struct { char data; //结点值 double weight; //权重 int parent; //父亲结点 int lchild; //左...
  • C语言动态构造红黑

    2018-11-02 19:12:08
    贴出核心代码和效果图。希望共同学习交流进步。 void leftRotate(Tnode* root,Tnode x){  Tnode y = x-&gt;r;  x-&gt;r = y-&gt;l;  //y-&gt;l = x;  if(y-&gt;l!... ...
  • C语言 Huffuman

    2020-07-11 09:39:15
    在这里,我们只关心Huffman构造过程。  给出一列数{pi}={p0, p1, …, pn-1},用这列数构造Huffman的过程如下:  1. 找到{pi}中最小的两个数,设为pa和pb,将pa和pb从{pi}中删除掉,然后将它们的和加入到{pi}...
  • 主要为大家详细介绍了C语言实现最小生成树构造算法,利用Prim算法或kruskal算法求解,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • c语言构造哈夫曼输出哈夫曼编码出错,跪求大神帮我找错0youxun0952016.09.07浏览120次分享举报#include #include #include typedef struct node { int weight; char letter; struct node *Lchild; struct node *...
  • c语言 哈夫曼

    2009-07-11 16:38:27
    构造一棵哈夫曼,输出对应的哈夫曼编码证
  • 1.结点的路径长度:从根结点到该结点的路径上分支的数目。2.的路径长度:中每个结点的路径长度之和。3.的带权路径长度:中...5.哈夫曼算法构造最优树:以二叉树为例:(1)根据给定的n个权值{w1, w2, ... ,...
  • C语言 FBI

    千次阅读 2014-02-08 14:14:09
    算法训练 FBI 时间限制:1.0s 内存限制:256.0MB   ... 我们可以把由“0”和“1”组成的字符串分为三类:全“0”串称为B串,全“1”串称为I串,...由一个长度为2N的“01”串S可以构造出一棵FBIT,递归的构造
  • 请计算出每个字符出现的概率,并以概率为权重来构造哈夫曼,写出构造过程、画出最终的哈夫曼,得到每个字符的哈夫曼编码。 请将上述设计哈夫曼编码的过程,用代码来实现,并输出各个字母的哈夫曼编码。(有代码...
  • 构造哈夫曼树c语言程序

    千次阅读 2018-05-29 22:17:37
    #include&lt;string.h&gt;#include&lt;stdlib.h&gt;#include&lt;stdio.h&...typedef struct{ unsigned int weight; unsigned int parent,lchild,...//动态分配数组存储哈夫曼 typedef c...
  • 所以构造哈夫曼时,应该让权重小的结点放在靠下的位置让权重大的放在较上的位置。 代码: #include<stdio.h> #include<stdlib.h> #include<string.h> #define N 30 //叶子结点最大值 #define M...
  • 进行k-1次生成 x=y= 0 ;m=n= 1.0 ; //注意m和n必须大小或等于输入权值里权值最大的数.示例数据的权值都小于1. for (j= 0 ;j;j++){ // 寻找两个权值最小的节点索引. if (T[j].w[j].parent==- 1 ){ n =m;m=T...
  • 运行结果正确 感觉最难的是的合并 ...//构造哈夫曼 typedef struct { int val; int parent,left,right; }node,*tree; //构造哈夫曼编码 typedef struct{ int weight; int code[10]; }code_nod
  • C语言实现二叉排序树构造 查找删除节点 中序遍历 已调试好
  • 哈夫曼构造C语言实现)

    万次阅读 多人点赞 2018-12-06 17:48:27
    哈夫曼构造过程可以详见推荐博客:哈夫曼以及哈夫曼编码的构造步骤 建议先看完推荐博客中的文字说明,或者自己找一本数据结构的来仔细阅读以下关于哈夫曼构造 然后再来看下面给出的code 这里给出的是...
  • 本程序用递归方法把一个中序输入(用txt文本存储) 构造一个,采用标准C,通过看我的代码可以学到很多东西,WIN-TC编译器。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 485
精华内容 194
关键字:

c语言构造树

c语言 订阅