| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 2022 人关注过本帖
标题:谁知道 最优查找树 的算法?
只看楼主 加入收藏
rayii
Rank: 1
等 级:新手上路
帖 子:31
专家分:0
注 册:2005-10-24
收藏
 问题点数:0 回复次数:5 
谁知道 最优查找树 的算法?
有没有通俗易懂的 帮忙贴一下
我是搞不懂啊
搜索更多相关主题的帖子: 算法 
2007-11-30 22:15
missiyou
Rank: 5Rank: 5
等 级:贵宾
威 望:16
帖 子:531
专家分:218
注 册:2007-10-9
收藏
得分:0 
好像和哈夫曼树差不多,根据权植,然后找到最小权植,然后,相加变为双亲,

我也不太懂,好像是这样吧
2007-12-05 22:38
appleflower
Rank: 1
等 级:新手上路
帖 子:13
专家分:0
注 册:2007-12-9
收藏
得分:0 
哈夫曼树
#include<iostream.h>
#include<string.h>
#include<stdlib.h>
#include<stdio.h>
#define INT_MAX 100000
#define N 10000
typedef struct HTNode//类型定义
{                        
 int weight;
 int parent;
 int lchild;
 int rchild;
 char data;
 char code[20];
}*HuffmanTree;
void Select(HuffmanTree HT,int end,int &s1,int &s2)      //查找权值最小的两个字符序号
{
  int i,j,t;
  int min1=INT_MAX;
  int min2;
  
     for (i=1;i<=end;i++)
  {
          if (HT[i].parent==0&&HT[i].weight<min1)
    {
          s1=i;
          min1=HT[i].weight;
    }
  }
   min2=INT_MAX;
     
     for(j=1;j<=end;j++)
  {
          if (HT[j].parent==0&&(s1!=j)&&min2>HT[j].weight)
    {
              s2=j;
              min2=HT[j].weight;
          }
     }
  if(s1>s2)
  {
   t=s1;
   s1=s2;
   s2=t;
  }
}
void Initialization(HuffmanTree &ht,int a,int b)   //初始化HuffmanTree,建立该树
{
 int i,start,f,c,s1,s2;
 char *cd;
 char *str;
 int *w;
 str=new char[a+1];
    w=new int[a+1];
 cout<<"输入源字符:"<<endl;
 for(i=1;i<=a;i++)                              
  //初始化输入字符时,注意:应连续输入,再按回车键!  
  cin>>str[i];
 cout<<"输入权值:"<<endl;
    for(i=1;i<=a;i++)
  cin>>w[i];
 ht=new HTNode[b+1];
 for(i=1;i<=a;i++)
 {
  ht[i].weight=w[i];
  ht[i].parent=0;
  ht[i].lchild=0;
  ht[i].rchild=0;
  ht[i].data=str[i];
 }
 for(;i<=b;i++)
 {
  ht[i].weight=0;
  ht[i].parent=0;
  ht[i].lchild=0;
  ht[i].rchild=0;
  ht[i].data='\0';
  ht[i].code[0]='\0';
 }
   for(i=a+1;i<=b;i++){
        Select(ht,i-1,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;
    }
 cd=new char[a];
    cd[a-1]='\0';
      for(i=1;i<=a;++i)            //求出各字符相应的编码
  {
        f=ht[i].parent;
  c=i;
  start=a-1;
        while(f!=0)
  {
           if(ht[f].lchild==c)
      cd[--start]='0';
           else
      cd[--start]='1';
     c=f;
     f=ht[f].parent;
  }
        strcpy(ht[i].code,&cd[start]);
  }
}
void Encoding(HuffmanTree ht)                   //要求输入报文,然后编码!
{
 int i=0,j;
 char str[N];   
 cout<<"输入要编译的字符"<<endl;
    cin>>str;
 cout<<endl<<"编译后的字符为:"<<endl;
 while(str[i]!='\0')
 {
  j=1;
  while(ht[j].data!=str[i])j++;
  cout<<ht[j].code;
  i++;
 }
 cout<<endl<<endl;
}
void Decoding(HuffmanTree ht,int m)              //要求输入原码,进行译码!
{
 
 int i=0,p;
 char s[N];
 cout<<"输入要译回的数字(二进制):"<<endl;
 cin>>s;
    cout<<"其真实字符为:"<<endl;
 p=m;
 while(s[i]!='\0')
 {
  while(ht[p].lchild!=0&&s[i]!='\0')
  {
   if(s[i]=='0')
    p=ht[p].lchild;
   else
    p=ht[p].rchild;
   i++;
  }   
   
         cout<<ht[p].data;
   p=m;   
 } cout<<endl<<endl;
}
void print(HuffmanTree ht,int n,int m)            //打印HuffmanTree到输出端
{
 int i;
 cout<<"下面将列出创建哈夫曼树的结果:"<<endl<<endl;
 cout<<"loc"<<'\t'<<"w"<<'\t'<<"par"<<'\t'<<"lch"<<'\t'<<"rch"<<'\t'<<"data"<<'\t'<<"code"<<endl;
 
 for(i=1;i<=m;i++)
  cout<<i<<'\t'<<ht[i].weight<<'\t'<<ht[i].parent<<'\t'<<ht[i].lchild<<'\t'<<ht[i].rchild<<'\t'<<ht[i].data<<'\t'<<ht[i].code<<'\t'<<endl;
}
void main()
{
 int n,m;
 char a,b;
 HuffmanTree HT=NULL;
 while(b!='Q')                        //系统界面……
 {
  cout<<"请选择要进行的操作:"<<endl;
  cout<<"创建哈夫曼树型结构(I)"<<'\t'<<"编码(E)"<<'\t'<<"译码(D)"<<'\t'<<"输出(P)"<<'\t'<<"退出程序(Q)"<<endl;
  cin>>a;
  switch(a){
  case 'I':
   cout<<"输入哈夫曼 源字符的个数:"<<endl;
   cin>>n;
   m=2*n-1;
   Initialization(HT,n,m);
   break;
  case 'E':
   Encoding(HT);
   break;
  case 'D':
   Decoding(HT,m);
   break;
  case 'P':
   print(HT,n,m);
   break;
  case 'Q':
   b='Q';
   break;
  }
 }
}
2007-12-09 11:18
康elon
Rank: 2
来 自:西安
等 级:论坛游民
帖 子:179
专家分:24
注 册:2008-4-6
收藏
得分:0 
用哈夫曼树就能实现了
用哈夫曼树就能实现了

我很厉害。。。
2008-05-24 15:23
jiangzw625
Rank: 1
等 级:新手上路
帖 子:119
专家分:0
注 册:2006-3-27
收藏
得分:0 
哈夫曼树和这个不是一个概念。
哈夫曼树并不是查找树,他有左儿子比根节点小,右儿子比根节点大的特性吗。而且哈夫曼树的节点
还不是原始的数据节点。

分两种情况。
1.所有的查找概率相同
那么先把原始序列排序,然后每次取中间节点作为根节点。左右依次递归
2.查找概率不同
这时得用动态规划实现。
先从小到大排序
状态d[i][j]表示序列中第i个数到第j个数的最少平均查找次数
则d[i][j] = min(d[i][k] + d[k][j] + p*w) i<k<j
其中p为每个节点的查找概率,其中w为每个节点的路经长

马马乎乎
2008-06-10 18:35
hainanzai
Rank: 1
等 级:新手上路
帖 子:2
专家分:0
注 册:2011-6-18
收藏
得分:0 
2011-06-21 21:50
快速回复:谁知道 最优查找树 的算法?
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.032639 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved