精华内容
下载资源
问答
  • 第五章 树—哈夫曼树的创建与最优二叉树带权路径和 数据结构基础代码 (严蔚敏 人邮教育出版社) 哈夫曼树 带权路径长度最短的树。 假设给叶子节点A、B、C、D它们的权值是2、4、5、7.则构成的哈夫曼树如下图所示:...

    第五章 树—哈夫曼树的创建与最优二叉树的带权路径和

    数据结构基础代码 (严蔚敏 人邮教育出版社)
    哈夫曼树 带权路径长度最短的树。
    假设给叶子节点A、B、C、D它们的权值是2、4、5、7.则构成的哈夫曼树如下图所示:
    在这里插入图片描述
    带权路径长度(WPL)
    树中所有叶子结点的带权路径长度和,其中叶子结点的带权路径是该结点到树根之间路径长度与结点上权的乘积。
    上图所示的带权路径长度是:WPL=23+43+52+71=35

    //哈夫曼树的创建
    #include <stdio.h>
    #include<stdlib.h>
    #include<iostream>
    using namespace std;
    
    typedef struct
    {
        int weight;
        int parent,lchild,rchild;
    }HTNode,*HuffmanTree;
    
    void Select(HuffmanTree HT,int n,int &s1,int &s2)   // n表示当前可以构成新的二叉树的根节点个数。
    {
        int minum;                             //定义一个临时变量保存最小值。
        int i;
        for(i=1;i<=n;i++)                     //从给定的根节点中,找到双亲为0,并且权值最小的第一个根节点。
        {
            if(HT[i].parent==0)
            {
                minum=i;
                break;
            }
        }
        for(i=1;i<=n;i++)
        {
            if(HT[i].parent==0)
            {
                if(HT[i].weight<HT[minum].weight)
                {
                    minum=i;
                }
            }
        }
        s1=minum;
        for(i=1;i<=n;i++)                   //从给定的根节点中,找到双亲为0,并且权值最小的第二个根节点。
        {
            if(HT[i].parent==0 && i!=s1)
            {
                minum=i;
                break;
            }
        }
        for(i=1;i<=n;i++)
        {
            if(HT[i].parent==0&&i!=s1)
            {
                if(HT[i].weight<HT[minum].weight)
                {
                    minum=i;
                }
            }
        }
        s2=minum;
    }
    //创建哈夫曼树
    void CreateHuffmanTree(HuffmanTree &HT,int n)        
    {
        int i,m,s1,s2;
        int WPL=0;
        if(n<=1)
        {
            return;
        }
        m=2*n-1;
        HT=new HTNode[m+1];
        for(i=1;i<=m;++i)
        {
            HT[i].parent=0;
            HT[i].lchild=0;
            HT[i].rchild=0;
        }
        for(i=1;i<=n;++i)
        {
            cin >> HT[i].weight;
        }
        cout<<"您所创建的哈夫曼树是:"<<endl;
        for(i=n+1;i<=m;++i)                           //m=2*n-1的总结点数,n个叶子节点,第n+1个是非叶子节点。
        {
            Select(HT,i-1,s1,s2);                    /*从所有节点中,选择parent为0,并且权值最小的两个节点s1,s2。
                                                       传入i-1个节点的原因是因为除去当前第i个节点,其余i-1个都是可以选择的孩子结点*/
            HT[s1].parent=i;                         //把s1、s2节点的parent值定为当前的i。
            HT[s2].parent=i;                         
            HT[i].lchild=s1;                         //当前i节点的左右孩子分别为s1,s2.
            HT[i].rchild=s2;
            HT[i].weight=HT[s1].weight+HT[s2].weight;   
            WPL +=HT[i].weight;                        //最优二叉树的路径和,即哈夫曼树中除根节点以外所有结点的权值之和。
            printf("%d (%d,%d)\n",HT[i].weight,HT[s1].weight,HT[s2].weight);
    
        }
            printf("哈夫曼树的带权路径和是:\n");
            printf("%d\n",WPL);
    
    }
    
    int main()
    {
        HuffmanTree HT;
        int n;
        printf("请输入创建哈夫曼树叶子结点个数\n");
        scanf("%d",&n);
        printf("请输入哈夫曼树叶子结点的权重\n");
        CreateHuffmanTree(HT,n);
        return 0;
    }
    
    

    在这里插入图片描述

    展开全文
  • 根据网上的相关资料,通过构造哈夫曼树求解最优二叉树所有叶子结点的带权路径长度之和   # include #include #define maxsize 30; /*  霍夫曼树求解最佳二叉树  完成时间:2015-7-10 */ typedef struct ptree { ...

    根据网上的相关资料,通过构造哈夫曼树求解最优二叉树所有叶子结点的带权路径长度之和

     

    # include<stdio.h>
    #include<malloc.h>
    #define maxsize 30;
    /*
        霍夫曼树求解最佳二叉树
     完成时间:2015-7-10
    */
    typedef struct ptree
    {
     float w;
     struct ptree *lchild;
     struct ptree *rchild;
    }ptree,*ptt;//二叉树定义,w为权值
    typedef struct pforest
    {
     struct pforest *link;
     struct ptree *root;
    }pforest;//森林定义。
    float WPL=0;
    int n=0;
    struct pforest *inforest(struct pforest *f,struct ptree *t)
    {
     //根据权值的大小将二叉树一个个放到森林里。即将t插入该森林
     struct pforest *p,*q,*r;
     struct ptree *ti;
     //开辟新的空间,便于插入至森林
     r=(pforest *)malloc(sizeof(pforest));
     r->link=NULL;
     r->root=t;
     q=f;
     p=f->link;
     while(p!=NULL)
     {
      ti=p->root;//取出此树的根节点
      if(t->w>ti->w)
      {
       q=p;
       p=p->link;
      }
      else
       p=NULL;
     }//while
     r->link=q->link;
     q->link=r;//插入新的二叉树
     return f;
    }
    struct ptree *hafm(float w[])
    {
      pforest *p1,*p2,*f;
      ptree *t,*t1,*t2;//用于保存取出来的两个节点
      ptree *ti;//新节点
     int i;
     f=(pforest *)malloc(sizeof(pforest));
     f->link=NULL;
    // printf("%d ",n);
     for(i=0;i<n;i++)
     {
      ti=(ptree*)malloc(sizeof(ptree));
      ti->w=w[i];
      ti->lchild=NULL;
      ti->rchild=NULL;
     // printf("%d ",i);
      f=inforest(f,ti);//将ti挂到一棵树上面,初试化的时候形成了n颗树。
     }//初始化
    // printf("\n");
     while(((f->link)->link)!=NULL)//f为一颗森林,如果至少含有两棵树则继续进行
     {
      p1=f->link;
      p2=p1->link;
      //f为一有序链表,取出前2颗二叉树。
      f->link=p2->link;
      t1=p1->root;//取出树
      t2=p2->root;
      free(p1);
      free(p2);
      //接着形成新的节点
      t=(ptree*)malloc (sizeof(ptree));
      t->w=(t1->w)+(t2->w);
      t->lchild=t1;
      t->rchild=t2;//产生新的二叉树
      f=inforest(f,t);//挂到树上
     }
     p1=f->link;
     t=p1->root;//保存最终二叉树
     free(f);//此时为最终情况,即最终的二叉树,*/
     return t;
    }
    void Input_Node(float w[])
    {
     printf("Please Input the sum of node:\n");
     scanf("%d",&n);
     printf("请依次输入权重值:\n");
     for(int i=0;i<n;i++)
     {
      scanf("%f",&w[i]);
     }
    }//正常
    void travel(struct ptree *head,int num)
    {
     struct ptree *p;
     p=head;
     if(p!=NULL)
     {
      if(((p->lchild)==NULL)&&((p->rchild)==NULL))
      {
      // printf("%lf",p->w);
      // printf("\n");
       WPL=WPL+num*(p->w);
      }
      travel(p->lchild,num+1);
      travel(p->rchild,num+1);//
     }
    }
    void main ()
    {

     struct ptree *head;
     float w[20];
     Input_Node(w);
     head=hafm(w);
     travel(head,0);
     printf("\n最优二叉树所有叶子结点的带权路径长度之和:%lf\n",WPL);
     n=0;
    }

    附图一张:

     

    展开全文
  • 哈夫曼树=带权路径长度最短的树(要么都比二叉树或者三叉树) 1.哈夫曼树权值越大的叶子越靠近根 2.具有相同带权节点的哈夫曼树不为一 步骤 1.构造森林全是根 2.选俩个小的为左右子树,根为权之和 3.将这棵树放进...

    1.路径长度:两个节点之间的节点数(不算头算尾)
    2.树的路径长度,:树根到每个节点的路径长度之和
    完全二叉树是路径长度最短的完全二叉树
    3.节点的带权路径长度:从根节点到该节点的权和路经长度的乘积
    4.树的带权路径长度:树中所有叶子节点的带权路径长度之和

    哈夫曼树=带权路径长度最短的树(要么都比二叉树或者三叉树)
    1.哈夫曼树权值越大的叶子越靠近根
    2.具有相同带权节点的哈夫曼树不为一

    步骤
    1.构造森林全是根
    2.选俩个小的为左右子树,根为权之和
    3.将这棵树放进森林里
    4.重复23,直到剩一颗哈夫曼树
    75524 24-6,然后选55造树而不是65
    性质
    1.哈夫曼树节点的度数只有0和2
    2.包含n个叶子节点的哈夫曼树有2n-1个节点(那个节点经过n-1次合并,每次合并产生一个度为2的节点n+n-1=2n-1)
    3.所有节点的度不=1
    算法实现

    哈夫曼编码
    1.由题目构造一棵哈夫曼树
    2.左分支写0,右分支写1
    即可得到每个字符的编码

    为什么能保证前缀编码?
    因为每一个字符都是叶子节点,路径都不一样
    为社么保证编码总长度最短?
    哈夫曼树带权路径长度最短

    展开全文
  • 二叉树带权路径长度问题

    千次阅读 2019-07-02 00:39:36
    二叉树带权路径长度问题问题中的名词解释1 二叉树定义2 二叉树带权路径长度问题解决方法1 先序遍历2 层次遍历个人总结 问题中的名词解释 1 二叉树定义 二叉树是n(n>=0)个节点的有限集合: 1 或者为空...

    问题中的名词解释

    1 二叉树定义

    	二叉树是n(n>=0)个节点的有限集合:
    	1 或者为空二叉树,即n=0
    	2 或者由一个根结点和两个互不相交的的被称为根的左子树和根的右子树组成。其中左子树和右子树又分别是一个二叉树。
    

    2 二叉树的带权路径长度

    	二叉树的带权路径长度为每个叶子结点的深度与权值之积的总和。
    

    问题解决方法

    1 先序遍历

    先序遍历的时候需要采用递归调用来进行二叉树的遍历,把每个结点的深度作为递归函数的一个参数进行传递.具体步骤如下:
    若当前访问结点是叶结点,则总长度加上该结点的深度与权值之积
    若该结点是非叶结点,若左子树不为空,递归调用左子树,若右子树不为空,递归调用右子树,直至最后返回总长度
    

    二叉树结点的数据类型定义如下:

    typedef struct BiNode{
    	int weight;
    	struct BiTNode *lchild,rchild;
    }BiNode,*BiTree;
    
    int  Pre_Weight(BiTree root,int deep){
      static  int sum=0;
      if(root->lchild==NULL && root->rchild==NULL){
      	sum=sum+deep*root->weight;
       }
      if(root->lchild !=NULL){
        Pre_Weight(root->lchild,deep++);
       }
      if(root->rchild !=NULL){
      	Pre_Weight(root->rchild,deep++);
       }
      return sum;
    }
    

    2 层次遍历

    层次遍历的时候需要使用队列进行遍历,并记录当前的层数,具体步骤如下:
    当遍历到叶结点时候,总长度加上该结点的深度与权值之积。
    当遍历到非叶结点的时候,把该结点的子树加入到队列,当某结点为该层最后一个结点的时候,层数加一,队列为空的时候就返回总长度
    

    二叉树结点的数据类型定义如下:

    typedef struct BiNode{
    	int weight;
    	struct BiTNode *lchild,rchild;
    }BiNode,*BiTree;
    

    层次遍历代码

    #define MaxSize 10000 				  //队列长度是情况而定
    int sum_LevelOrder(BiTree root){
    	BiTree queue[MaxSize];  		  //声明队列
    	int end1,end2;					  //队列首和尾指针
    	end1=end2=0;					  //定义了结点首指针指向对头元素,尾指针指向队尾元素的后一位元素 [很重要]
    	int sum=0,deep=0;				  //定义了带权路径长度和深度
    	BiTree currentNode,newcurrentNode //currentNode指向当前访问层的最后一个结点,newcurrentNode指向下一层的最后一个结点
    	currentNode=root;
    	newcurrentNode=NULL;
    	queue[end2]=root;				 //初始时根结点入队
    	end2++; 						 //队尾指针加一
    	while(end1!=end2){				 //队列不为空
         BiTree t = queue[end1++];		 //先赋值再加一	
         if(t->lchild==NULL && t->rchild==NULL){
           sum+=deep*t->weight;
         }
         if(t->lchild != NULL){
          queue[end2++]=t->lchild;
          newlastcurrentNode=t->lchild;
         }
         if(t->rchild != NULL){
          queue[end2++] = t->rchild;
          newcurrentNode = t->rchild;
         }
         if(t==currentNode){         	//当遍历到当前层的最后一个结点的时候就更新层
         currentNode=lastcurrentNode;   //把下一层的结点赋值给当前层,达到换层的作用
         deep+=1;
         }
      }
      return sum;
    }
    

    个人总结

    1 递归先序遍历的时候需要设置static关键字,来保证整个程序执行期间,总长度一直存在
    2 层次遍历的时候要抓住当前层的最后一个结点和下一层的最后的一个结点,作为层次遍历改变的临界情况
    3 层次遍历的时候涉及到循环,需要注意队列的队尾,队首指针的定义,涉及临界条件.需要注意
    
    展开全文
  • 给定N个权值作为N个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。 实现原理...
  • 1、赫夫曼(Huffman)树又称最优二叉树或最优搜索树,是一种带权路径长度最短的二叉树。在许多应用中,常常赋给树中结点一个有某种意义的实数,称此实数为该结点的权。从树根结点到该结点之间的路径长度与该结点上权...
  • 哈夫曼树(带权最优二叉树

    万次阅读 多人点赞 2018-05-24 19:52:34
      哈夫曼树(Huffman)树又称最优二叉树,是指对于一组带有确定权值的叶子结点所构造的具有带权路径长度最短的二叉树。从树中一个结点到另一个结点之间的分支构成了两结点之间的路径,路径上的分支个数称为路径长度。...
  • 给定N个权值作为N个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树。 哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。 二,哈夫曼编码 以下...
  • 本文学习二叉树的一些典型应用,包括二叉排序树、平衡二叉树最优带权二叉树,具体内容见文。
  • 给定n个权值作为n个叶子结点,构造一棵二叉树,若该树的带权路径长度(wpl)达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree),还有的书翻译为霍夫曼树。 赫夫曼树是带权路径长度最短的树,权值较...
  • 哈夫曼树(最优二叉树)

    千次阅读 2019-10-27 16:51:19
    文章目录前言哈夫曼树(最优二叉树)定义与原理树的路径长度带权路径长度构造哈夫曼树哈夫曼树生成代码 前言 二叉树是树结构中的一种特殊形式,适用于折半查找、真假、对错等具有两种情况的事物进行建模。 比如需要对...
  • 最优二叉树

    2021-05-25 11:20:22
    给定n个权值作为n的[叶子]结点,构造一棵二叉树,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。 思路 将输入的...
  • 最优二叉树-哈夫曼树

    2021-04-11 00:14:50
    给定N个权值作为N个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。 哈夫曼树又...
  • 一、哈/赫夫曼树的基本定义 (1)路径:从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。...假设有 n 个权值构建一颗有 n 个叶子结点的二叉树,每个叶子结点带权 ,则其中带权路径长度
  • 当我们知道了数、森林、二叉树之后。我们就很好理解最优二叉树,下面从这两个方面展开讨论来认识最优二叉树。...下面我们根据树的带权路径计算公式来判定一下哪棵树是最优二叉树, WPL=7*2+5*2+2*2+2*4=36——a WP...
  • 出处:最优二叉树 最优二叉树(哈夫曼树) 哈夫曼树相关的几个名词 路径:在一棵树中,一个结点到另一个结点之间的通路,称为路径。图 1 中,从根结点到结点 a 之间的通路就是一条路径路径长度:在一条路径中,每...
  • 二叉树带权路径长度:设二叉树具有n个带权值的叶子结点,从根结点到各个叶子结点的路径长度与相应叶子结点权值的乘积之和。 记为: 哈夫曼树:给定一组具有确定权值的叶子结点,带权路径长度最小的二叉树。 ...
  • 最优二叉树最优二叉树相关概念 最优二叉树 最优二叉树又称哈夫曼(Huffman)树,在编码和决策等方面有着广泛的应用。 相关概念 路径:树中两个结点之间所经过的分支,称为它们之间的路径路径长度:一条路径上的...
  • 最优二叉树 ,也称为赫夫曼树(Huffman Tree)。 赫夫曼树是带权路径长度最短的树,权值较大的结点离根较近。 基本概念 路径长度 :从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径, 路径上的...
  • 最优二叉树是什么? 概述:又称为哈夫曼树或者霍夫曼树,它是一类带权路径长度最短的树。路径是从树中一个结点到另一个结点之间的通路,路径上的分支数目称为路径长度。树的路径长度是从树根到每一个叶子之间的...
  •   一:什么是最优二叉树?...在权为wl,w2,…,wn的n个叶子所构成的所有二叉树中,带权路径长度最小(即代价最小)的二叉树称为最优二叉树或哈夫曼树。 二:下面先弄清几个几个概念: 1.路径长度 .
  • 数据结构与算法—复习:最优二叉树 哈夫曼算法 手画很简单,代码则需要多考虑 /** * 程序说明:复习 最优二叉树(哈夫曼树) 哈夫曼算法 */ #include <... //该点到带权外部路径长度的值 int parent,ll
  • 此篇博客讲最优二叉树也叫哈夫曼树的原理,以及构建步骤,还有哈夫曼编码原理。建议有二叉树基础朋友学习交流。对二叉树基础可以看我的另外一篇博客二叉树的构建以及遍历 文章目录哈夫曼树引出:哈夫曼树原理及实现...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,350
精华内容 2,140
关键字:

最优二叉树带权路径