实验要求

• 实现二叉树的抽象数据类型
• 实现二叉树的建立的运算
• 实现二叉树的遍历运算
• 实现创建哈夫曼树的算法

实验代码

• 实现二叉树的抽象数据类型

typedef struct BiTNode   //define tree Node
{   TElemType data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

• 实现二叉树的建立的运算

int CreateBiTree(BiTree &T) //CreateBiTree function()
{
    TElemType ch;
    cout<<"Please input data(/ for NULL node!):";
    cin>>ch;
    if(ch=='/') T=NULL;
    else{
        if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))
        {
            cout<<"Overflow!";
            return(ERROR);
        }//end of if
        T->data=ch;
        CreateBiTree(T->lchild);
        CreateBiTree(T->rchild);
    }//end of else
    return(OK);
}//end of CreateBiTree function()

• 实现二叉树的遍历运算（中序遍历）

int InOrderTravers(BiTree T) //InOrderTravers sub-function
{
    if(T)
    {
        if(InOrderTravers(T->lchild))
        {
            cout<<T->data<<"->";
            if(InOrderTravers(T->rchild))   return 1;
        }//end of if lchild
        return 0;
    }//end of if T
    return 1;
}//end of InOrderTravers sub-function

• 实现创建哈夫曼树的算法

void HuffmanCoding(HuffmanTree &HT,HuffmanCode&HC,int *w,int n) //sub-function
{
    int m,i,s1,s2,start,c,f;
    HuffmanTree p;
    if(n<=1) return;
    m=2*n-1;
    HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
    for(p=HT+1,i=1;i<=n;++i,++p,++w)    //initial HT[1...n]
    {
        p->weight=*w;
        cout<<endl<<"HT["<<i<<"].weight="<<p->weight<<" ";
        p->parent=0;
        p->lchild=0;
        p->rchild=0;
    }
    for(;i<=m;++i,++p)    //initial HT[n+1...2+n1]
    {
        p->weight=0;
        p->parent=0;
        p->lchild=0;
        p->rchild=0;
    }
    cout<<endl<<endl<<"HuffmanTree is created in following order :";
    for(i=n+1;i<=m;++i)
    {
        Select(HT,i-1,s1,s2);  //s1 is the least,s2 is the second least
        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;
        cout<<endl<<"HT["<<s1<<"] and HT["<<s2<<"] create";
        cout<<" HT["<<i<<"], weight="<<HT[i].weight;
    }
    HC=(HuffmanCode)malloc((n+1)*sizeof(char *));
    char *cd;
    cd=(char *)malloc(n*sizeof(char));
    cd[n-1]='\0';
    cout<<endl<<endl<<"HuffmanTree Code is as follows :"<<endl;
    for(i=1;i<=n;++i)
    {
        start=n-1;
        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';
            HC[i]=(char *)malloc((n-start)*sizeof(char));
            strcpy(HC[i],&cd[start]);
            printf("\nHT[%d] node's Huffman code is:%s",i,HC[i]);
    }
    free(cd);
}  // HuffmanCoding() end

相关文章：
数据结构之栈（C语言版）
数据结构之图、广度优先搜索以及佛洛依德算法