精华内容
下载资源
问答
  • 第五章 树—哈夫曼树的创建与最优二叉树带权路径和 数据结构基础代码 (严蔚敏 人邮教育出版社) 哈夫曼树 带权路径长度最短的树。 假设给叶子节点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;
    }
    
    

    在这里插入图片描述

    展开全文
  • 哈夫曼树介绍1哈夫曼树的定义哈夫曼(Huffman)树,又称最优二叉树,是由n个带权叶子结点构成的所有二叉树中带权路径长度最短的二叉树。给定n个数值{ W1,W2,…,Wn},若将它们作为n个结点的权,并以这n个结点为叶子结点...

    注意:哈夫曼树并不唯一,但带权路径长度一定是相同的。

    二叉树:每个结点最多含有两个子树的树称为二叉树。

    定理:对于具有n个叶子结点的哈夫曼树,共有2n-1个结点。

    5395467aceeec57127165592f86f2800.png

    哈夫曼树介绍

    1哈夫曼树的定义

    哈夫曼(Huffman)树,又称最优二叉树,是由n个带权叶子结点构成的所有二叉树中带权路径长度最短的二叉树。给定n个数值{ W1,W2,…,Wn},若将它们作为n个结点的权,并以这n个结点为叶子结点构造一颗二叉树,那么就可以构造出多棵具有不同形态的二叉树,其中带权路径长度最短的那棵二叉树称为哈夫曼树,或称最优二叉树。如图(二)所示:

    dfe826fafb4496af3ce6342cede7091f.png

    WPL:树中从根到所有叶子结点的各个带权路径长度之和

    2 构建哈夫曼树的方法

    如下:

    (1)初始化:根据给定的n个权值{W1,W2,….,Wn}构造n棵二叉树的森林T{T1,T2,…Tn},其中每棵二叉树Ti (1≤i≤n)中都只有一个带权Wi为的根结点,其左、右子树均为空。

    (2)找最小树:在森林T中选取两棵结点权值最小的子树分别作为左、右子树构造一棵新的二叉树、且使左子树的权值小于右子树的权值、且置新的二叉树的根结点的权值为其左、右子树上根结点权值之和。

    (3)删除与加入:在森林T中,删除这二棵树,同时将新得到的二叉树加入T中。

    (4)判断:重复(2)与(3)操作,直到T只含一棵二叉树树为止,这棵树便是哈夫曼树。如图(三)所示:

    6d53f23b05be2daf1b162360448e99e1.png

    因为权值的不同,哈夫曼树的样子有点不同,为了加深对哈夫曼树构建过程的认识,笔者再列举一个哈夫曼树的构建,见图(四):

    80e86f7f0782c605c36a7387685038ed.png

    (1)8个结点的权值大小如下:

    415644fa9e5523091b40dc73c43ad87f.png

    (2)从19,21,2,3,6,7,10,32中选择两个权小结点。选中2,3。同时算出这两个结点的和5。

    337171faaeb84ef7f7318cbdea0609c2.png

    (3)从19,21,6,7,10,32,5中选出两个权小结点。选中5,6。同时计算出它们的和11。

    716d835feee311509c8619f7930dfd26.png

    (4)从19,21,7,10,32,11中选出两个权小结点。选中7,10。同时计算出它们的和17。

    (注:如果两个数的和正好是下一步的两个最小数的其中的一个,那么这个树直接往上生长就可以了,如果这两个数的和比较大,不是下一步的两个最小数的其中一个,那么就并列生长。)比如比较最小两个   7 10 11  所以只能另起一个

    d55d7b0d5ab318f1794787771c652afd.png

    (5)从19,21,32,11,17中选出两个权小结点。选中11,17。同时计算出它们的和28。

    43756df494ec7b9a9b430e3ab019ac80.png

    (6)从19,21,32,28中选出两个权小结点。选中19,21。同时计算出它们的和40。另起一颗二叉树。

    b22182c64f2be6f919d033b39926b793.png

    (7)从32,28, 40中选出两个权小结点。选中28,32。同时计算出它们的和60。

    3df59858c90b2681304954f5c5aa80a1.png

    (8)从 40, 60中选出两个权小结点。选中40,60。同时计算出它们的和100。 好了,此时哈夫曼树已经构建好了。

    42ab072462e40871e469027a62f44978.png

    展开全文
  • 根据网上的相关资料,通过构造哈夫曼树求解最优二叉树所有叶子结点的带权路径长度之和   # 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;
    }

    附图一张:

     

    展开全文
  • 简介哈夫曼树(Huffman)树又称最优二叉树,是指对于一组带有确定权值的叶子结点所构造的具有带权路径长度最短的二叉树。从树中一个结点到另一个结点之间的分支构成了两结点之间的路径,路径上的分支个数称为路径长度。...

    简介

    哈夫曼树(Huffman)树又称最优二叉树,是指对于一组带有确定权值的叶子结点所构造的具有带权路径长度最短的二叉树。从树中一个结点到另一个结点之间的分支构成了两结点之间的路径,路径上的分支个数称为路径长度。二叉树的路径长度是指由根结点到所有叶子结点的路径长度之和。如果二叉树中的叶子结点都有一定的权值,则可将这一概念拓展:设二叉树具有n个带权值的叶子结点,则从根结点到每一个叶子结点的路径长度与该叶子结点权值的乘积之和称为二叉树路径长度,记做:

    WPL = W1L1 + W2L2 + ...... + WnLn;

    构建过程

    ① 对数据中出现过的元素各产生一个树叶节点,并赋予其出现的频率。

    ② 令N为T1和T2的父节点,其中T1和T2是出现频率最低的两个节点,令N的频率为T1和T2的频率之和

    ③ 消去两个节点,插入N节点,重复前面的步骤。

    代码实现

    HuffmanTree.java

    import java.util.ArrayDeque;

    import java.util.ArrayList;

    import java.util.Collections;

    import java.util.List;

    public class HaffmanTree {nodes;

    private Node root;

    // 实现排序接口,添加结点自动排序,从小到大排序

    private int value;

    private Node left;

    private Node right;

    public Node(int value) {

    this.value = value;

    }

    public Node getLeft {

    return left;

    }

    public void setLeft(Node left) {

    this.left = left;

    }

    public Node getRight {

    return right;

    }

    public void setRight(Node right) {

    this.right = right;

    }

    @Override

    public int compareTo(Node o) {

    return this.value - o.value;

    }

    }

    public HaffmanTree {}

    public void bulidHaffmanTree(int arr) {

    nodes = new ArrayList<>;

    for (int i = 0; i < arr.length; i++) {

    nodes.add(new Node(arr[i]));

    }

    root = createHaffmanTree(nodes);

    }nodes) {

    while (nodes.size > 1) {

    // 排序,每次取最小的两个结点

    Collections.sort(nodes);

    // 获得权值最小的两个结点,左结点大于右结点

    Node leftChild = nodes.get(1);

    Node rightChild = nodes.get(0);

    // 生成新结点

    Node newNode = new Node(leftChild.value + rightChild.value);

    newNode.left = leftChild;

    newNode.right = rightChild;

    // 删除权值最小的两个结点

    nodes.remove(0);

    nodes.remove(0);

    // 将新结点加入到集合中

    nodes.add(newNode);

    }

    return nodes.get(0);

    }

    // 先序遍历

    public void preOrder {

    preOrder(root);

    }

    private void preOrder(Node root) {stack = new ArrayDeque<>;

    while (root != null || !stack.isEmpty) {

    System.out.println(root.value);

    stack.push(root);

    root = root.left;

    }

    if (!stack.isEmpty) {

    root = stack.pop;

    root = root.right;

    }

    }

    // 中序遍历

    public void inOrder {

    preOrder(root);

    }

    private void inOrder(Node root) {

    while (root != null || !stack.isEmpty) {

    stack.push(root);

    root = root.left;

    }

    if (!stack.isEmpty) {

    root = stack.pop;

    System.out.println(root.value);

    root = root.right;

    }

    }

    // 非递归后序遍历

    public void postOrder {

    postOrder(root);

    }

    private void postOrder(Node root) {

    Node cur = root;

    Node pre = null;

    while (cur != null || !stack.isEmpty) {

    while (cur != null) {

    stack.push(cur);

    cur = cur.left;

    }

    cur = stack.peek;

    if (cur.right == null || cur.right == pre) {

    System.out.print(cur.value + " ");

    pre = cur;

    stack.pop;

    cur = null;

    } else {

    cur = cur.right;

    }

    }

    }

    // 层序遍历

    public void levelOrder {

    levelOrder(root);

    }

    private void levelOrder(Node root) {ArrayDequequeue = new ArrayDeque<>;

    Node curr = root;

    if (curr == null)

    return;

    queue.add(curr);

    while (!queue.isEmpty) {

    curr = queue.remove;

    System.out.print(curr.value + " ");

    if (curr.left != null)

    queue.add(curr.left);

    if (curr.right != null)

    queue.add(curr.right);

    }

    }

    }

    测试代码

    HuffmanTreeTest.java

    public class HaffmanTreeTest {

    public static void main(String args) {

    int arr = {13, 7, 8, 3, 29, 6, 1};

    HaffmanTree haffmanTree = new HaffmanTree;

    haffmanTree.bulidHaffmanTree(arr);

    haffmanTree.postOrder;

    System.out.println;

    haffmanTree.levelOrder;

    }

    }

    展开全文
  • 最优二叉树

    2019-11-30 10:13:40
    叶子结点的权值:给叶子节点一个有意义的数值 带权路径长度:从根节点到各个叶子节点的路径...最优二叉树带权路径长度最小的二叉树,也成为哈夫曼树 思路:权值越大的叶子节点越远离根节点,且不存在度为1的节点 ...
  • 哈夫曼树(带权最优二叉树

    万次阅读 2018-05-24 19:52:34
      哈夫曼树(Huffman)树又称最优二叉树,是指对于一组带有确定权值的叶子结点所构造的具有带权路径长度最短的二叉树。从树中一个结点到另一个结点之间的分支构成了两结点之间的路径,路径上的分支个数称为路径长度。...
  • 一、定义一些定义:节点之间的路径长度:在树中从一个结点到另一个结点所经历的分支,构成了这两个结点间的路径上的...结点的带权路径长度:结点到树根之间的路径长度与该结点上权的乘积。树的带权路径长度(Weighte...
  •   一:什么是最优二叉树?...在权为wl,w2,…,wn的n个叶子所构成的所有二叉树中,带权路径长度最小(即代价最小)的二叉树称为最优二叉树或哈夫曼树。 二:下面先弄清几个几个概念: 1.路径长度 .
  • 哈夫曼树=带权路径长度最短的树(要么都比二叉树或者三叉树) 1.哈夫曼树权值越大的叶子越靠近根 2.具有相同带权节点的哈夫曼树不为一 步骤 1.构造森林全是根 2.选俩个小的为左右子树,根为权之和 3.将这棵树放进...
  • 最优二叉树也称哈夫曼树,讲的直白点就是每个结点都带权值,我们让大的值离根近、小的值离根远,实现整体权值(带权路径长度)最小化。哈夫曼算法的思想我认为就是上面讲的,而它的算法实现思路是这样的:从根结点中...
  • 最优二叉树带权路径长度最短的二叉树。根据结点的个数,权值的不同,最优二叉树的形状也各不相同。它们的共同点是:带权值的结点都是叶子结点。权值越小的结点,其到根结点的路径越长。 官方定义: 在权为wl,...
  • 给定N个权值作为N个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树。 哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。 二,哈夫曼编码 以下...
  • 最优二叉树最优二叉树相关概念 最优二叉树 最优二叉树又称哈夫曼(Huffman)树,在编码和决策等方面有着广泛的应用。 相关概念 路径:树中两个结点之间所经过的分支,称为它们之间的路径路径长度:一条路径上的...
  • 最优二叉树又称哈夫曼树,是带权路径最短的二叉树。根据节点的个数,权值的不同,最优二叉树的形状也不同。 图 6-34 是 3 棵最优二叉树的例子,它们共同的特点是带权节点都是叶子节点,权值越小,就离根节点也远,...
  • 哈夫曼(最优二叉树

    千次阅读 2016-09-08 16:15:48
    最优二叉树: 定义: 路径:数的路径就是从书中的一个节点到树中的另一个节点的分支的个数长度,路径上的分支数目我们称之为长度 树的路径长度:从树根到每一个节点的长度之和(完全二叉树是一种树的路径最短的...

空空如也

空空如也

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

最优二叉树带权路径