关于中序遍历HuffmanTree的问题

holyzfy

InOrderTraverse(HT2+HT->lchild,HT2); //什么意思啊？

1. 
   
2. /*中序遍历HuffmanTree,输出其结点值,并对内部结点作标记*/
   
3. void InOrderTraverse(HuffmanTree HT,HuffmanTree HT2)
   
4. {
   
5.         if(HT->lchild!=0)
   
6.                 InOrderTraverse(HT2+HT->lchild,HT2); //什么意思啊？
   
7.         {//如果某个结点有孩子，显然它是内结点，应将其标记出来
   
8.                 if(HT->lchild!=0)
   
9.                         cout<<","<<HT->weight<<"(内点)";
   
10.                 else
    
11.                         cout<<","<<HT->weight;
    
12.         }
    
13.         if(HT->rchild!=0)
    
14.                 InOrderTraverse(HT2+HT->rchild,HT2);
    
15. }
    
16. 
    
17. //附HuffmanTree的存储结构
    
18. typedef struct
    
19. {  
    
20.         char letter;
    
21.         int weight;
    
22.         int parent;
    
23.         int lchild;
    
24.         int rchild;
    
25. }HTNode,*HuffmanTree;
    

复制代码

[ 本帖最后由 holyzfy 于 2007-5-31 13:35 编辑 ]

MMMIX

原帖由 holyzfy 于 2007-5-31 13:15 发表
InOrderTraverse(HT2+HT->lchild,HT2); //什么意思啊？

[code]
/*中序遍历HuffmanTree,输出其结点值,并对内部结点作标记*/
void InOrderTraverse(HuffmanTree HT,Huf ...

What's your question?

channelV

递归处理,但参数没看明白

holyzfy

这是别人的一段程序，能正确执行，由于没有注释，我也看不明白，又不能联系他本人，只能求助大家了，
递归调用很好理解，只是这句“InOrderTraverse(HT2+HT->lchild,HT2);”里的 参数搞不懂，
如果不用这段程序，还能否用其他的途径实现？

MMMIX

原帖由 holyzfy 于 2007-5-31 16:05 发表
这是别人的一段程序，能正确执行，由于没有注释，我也看不明白，又不能联系他本人，只能求助大家了，
递归调用很好理解，只是这句“InOrderTraverse(HT2+HT->lchild,HT2);”里的 参数搞不 ...

理解算法（晦涩代码）的不二法门：几大张白纸 + 铅笔。

kf701

从每个叶子节点往根遍历不就生成了  huffman code 了嘛

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef struct{
        unsigned long weight;
        int parent, lchild, rchild;
} HTNode, *HuffmanTree;

typedef char** HuffmanCode;

//HuffmanCode HC;

void Select(HuffmanTree HT, int n, int *s1, int *s2);

struct wandc{
        int w;
        int c;
        char *cd;
};

void HuffmanCoding(struct wandc *wc, int n)
{
        int i;
        if( n<=1 ) return;
        int m = 2*n - 1;
        HuffmanTree p;
        HuffmanTree HT = (HuffmanTree)malloc((m+1)*sizeof(HTNode));
        memset(HT, 0, sizeof(HTNode) * (m+1));
        for( p=HT,i=1; i<=n; ++i,++p )
        {
                HT[i].weight = wc[i].w;
        }
        int s1=0, s2=0;
        for( 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;
                HT[i].weight = HT[s1].weight + HT[s2].weight;
        }

        //HC = (HuffmanCode)malloc((n+1)*sizeof(char*));
        char *cd = (char*)malloc(n*sizeof(char));
        cd[n-1] = 0;
        int start;
        unsigned long f;
        for( i=1; i<=n; ++i )
        {
                start = n - 1;
                int c;
                for( c=i, f=HT[i].parent; f!=0; c=f, f=HT[f].parent )
                {
                        if( HT[f].lchild == c ) cd[--start] = '0';
                        else cd[--start] = '1';
                }

                wc[i].cd = (char*)malloc((n-start)*sizeof(char));
                strcpy(wc[i].cd, &cd[start]);
        }
        free( HT );
}

void Select(HuffmanTree HT, int n, int *s1, int *s2)
{
        int i;
        HT[0].weight = (unsigned long)(-1l);
        *s1 = *s2 = 0;
        for( i=1; i<=n; i++ )
                if( HT[i].parent == 0 )
                {
                        if( HT[i].weight < HT[*s1].weight )
                        {
                                *s2 = *s1;
                                *s1 = i;
                        }
                        else if( HT[i].weight < HT[*s2].weight )
                        {
                                *s2 = i;
                        }
                }
}

int main()
{
        char buf[128];
        fgets(buf, sizeof(buf), stdin);
        int len = strlen(buf);
        buf[len-1] = 0;
        len--;
        unsigned long weight[256];
        memset( weight, 0, sizeof(weight));
        int i;
        for(i=0; i<len; i++)
        {
                weight[buf[i]]++;
        }

        int n = 0;
        for(i=0; i<256; i++)
                if( weight[i] )
                        n++;

        printf("num of char = %d\n", n);

        struct wandc *array = (struct wandc*)malloc(sizeof(struct wandc)*(n+1));
        int j =1;
        for(i=0; i<256; i++)
                if( weight[i] )
                {
                        array[j].w = weight[i];
                        array[j].c = i;
                        j++;
                }

        HuffmanCoding( array, n );

        printf("\n");
        for(i=1; i<=n; i++)
                printf("char=%c,w=%d: %s\n", array[i].c,array[i].w,array[i].cd);

        printf("\n");
        for(i=0; i<len; i++)
        {
                for(j=0; j<n; j++)
                        if( buf[i] == array[j].c )
                                break;
                printf("%s",array[j].cd);
        }
        printf("\n");

        return 0;
}

holyzfy

原帖由 MMMIX 于 2007-5-31 16:48 发表
理解算法（晦涩代码）的不二法门：几大张白纸 + 铅笔。

呵呵，我也知道“大白纸 + 铅笔”，可也得先有个思路吧，我最想知道的是具体的解释，或者，一个说下算法思想也可以啊，~
诚恳求教


[ 本帖最后由 holyzfy 于 2007-5-31 17:30 编辑 ]

MMMIX

原帖由 holyzfy 于 2007-5-31 17:23 发表

呵呵，我也知道“大白纸 + 铅笔”，可也得先有个思路吧，我最想知道的是具体的解释，或者，一个说下算法思想也可以啊，~
诚恳求教

老实说，说了也白说！许多东西别人是无法代替你的，例如说学习；同时许多东西也是无法速成的，例如基础；另外还有许多东西是需要积累的，例如经验。

windaoo

原帖由 MMMIX 于 2007-5-31 17:35 发表

许多东西别人是无法代替你的，例如说学习；同时许多东西也是无法速成的，例如基础；另外还有许多东西是需要积累的，例如经验。

说得好

lenovo

希望楼主能贴一个完整的代码出来。