SWUST软件技术基础实验（2）二叉树的遍历及哈夫曼算法（代码部分完成，尚未分析实验二）

川长思鸟来 2021-09-23 10:54 222阅读 0赞

实验目的：  
1.掌握二叉树的二叉链表存储结构。  
2.掌握利用二叉树创建方法。  
3.掌握二叉树的先序、中序、后序的递归实现方法。  
4.掌握哈夫曼树的概念。  
5.掌握哈夫曼树的构造过程。  
6.掌握哈夫曼树编码。  
7.掌握哈夫曼树译码。  
实验内容：  
1.在计算机中创建如附图1-1所示的二叉树，分别对它进行中序、先序、后序遍历，并输出遍历结果。注：采用二叉链表作为二叉树的存储结构。  
2.输入n个叶子结点的权值构造哈夫曼树；根据哈夫曼树构造哈夫曼编码，以指向字符串的指针数组来存放，从叶子到根逆向求每个叶子结点的哈夫曼编码；对密文完成解码工作。注：n个叶子结点的权值。  
实验要求：  
1.编写创建如附图1-1所示二叉树的函数，函数名：create。  
2.编写递归实现二叉树的中序、先序和后序遍历算法。函数名分别为inorder，preorder，postorder。  
3.编写主函数测试以上二叉树的创建和遍历函数。  
4.编写哈夫曼构造函数。  
5.编写哈夫曼编码函数和解码函数。  
6.编写主函数构造哈夫曼树，并显现编码和解码功能测试。

难点：  
实验一：本实验的难点在于树的创建  
让我们来分析一下  
一棵树可以通过任意结点遍历整树，我们选择根结点指针作为返回值

Bitree* CreateTree()

需要输入插入的数据ch 对于该数的指针信息用队列进行存储 对于队列 需要设置front和rear 然后需要临时的结点s和存放根结点的root

{ 
        //用队列存放各结点地址
        char ch;
        Bitree* Q[maxsize];
        int front,rear;
        Bitree* root,*s;
        root=NULL;
        front=1;
        rear=0;//设置队列指针变量初始值

输入需要的数据

printf("请输入二叉树的各个结点，@表示虚结点，#表示结束：\n");
        scanf("%c",&ch);

然后判断输入的字符是否表示结束，如果不表示结束的话 再将其打印到屏幕上（这步操作方便看所有结点的信息）

while(ch!='#')
        { 
            putchar(ch);//返回输入的除#之外的所有结点
            s=NULL;
            if(ch!='@')
            { 
                s=(Bitree*)malloc(sizeof(Bitree));
                s->data=ch;
                s->lchild=NULL;
                s->rchild=NULL;
            }

将新申请的结点地址存放在队列中

rear++;//队列 尾指针加1 指向新结点地址应存放的单元
            Q[rear]=s;//将新节点地址入队或者虚结点NULL入队

判断rear是否为1 如果为1 也就是队列指向第一个结点 也就是树的根结点

if(rear==1)
            root=s;

如果不为1的话 也就是根结点的子树 则

else
            {    //Q[front]的作用：记录双亲 
                if(s&&Q[front])//孩子和双亲均不是虚结点
                    if(rear%2==0)
                        Q[front]->lchild=s;//孩子为左孩子
                    else
                        Q[front]->rchild=s;//孩子为右孩子
                if(rear%2==1)
                //rear和front的关系只有三种
                //第一种rear=front 根结点
                //第二种rear=front*2
                //第三种rear=front*2+1 如果是这种情况 
                //说明front这个双亲的两个孩子都处理完了
                front++;//结点Q[front]的两个孩子处理完毕 出队列
            }

继续输入ch，并最终返回

scanf("%c",&ch);//在while循环内部
        }
        return root;
    }

综上所述：实验一的全部代码应为：

#include <iostream>
    #include<cstring>
    #include<cstdlib>
    #include<cstdio>
    using namespace std;
    const int maxsize=1024;
    typedef char datatype;
    typedef struct node
    { 
        datatype data;
        struct node *lchild,*rchild;
    } Bitree;
    Bitree* CreateTree()
    { 
        //用队列存放各结点地址
        char ch;
        Bitree* Q[maxsize];
        int front,rear;
        Bitree* root,*s;
        root=NULL;
        front=1;
        rear=0;//设置队列指针变量初值？
        printf("请输入二叉树的各个结点，@表示虚结点，#表示结束：\n");
        scanf("%c",&ch);
        while(ch!='#')
        { 
            putchar(ch);//返回输入的除#之外的所有结点
            s=NULL;
            if(ch!='@')
            { 
                s=(Bitree*)malloc(sizeof(Bitree));
                s->data=ch;
                s->lchild=NULL;
                s->rchild=NULL;
            }
            rear++;//队列 尾指针加1 指向新结点地址应存放的单元
            Q[rear]=s;//将新节点地址入队或者虚结点NULL入队
            if(rear==1)
            root=s;
            else
            { 
                if(s&&Q[front])//孩子和双亲均不是虚结点
                    if(rear%2==0)
                        Q[front]->lchild=s;
                    else
                        Q[front]->rchild=s;
                if(rear%2==1)
                    front++;//结点Q[f]的两个孩子处理完毕 出队列
            }
            scanf("%c",&ch);
        }
        return root;
    }
    void preorder(Bitree* p)
    { 
        if(p!=NULL)
        { 
            printf(" %c ",p->data);
            preorder(p->lchild);
            preorder(p->rchild);
        }
    }
    void inorder(Bitree* p)
    { 
        if(p!=NULL)
        { 
            inorder(p->lchild);
            printf(" %c ",p->data);
            inorder(p->rchild);
        }
    }
    void postorder(Bitree* p)
    { 
        if(p!=NULL)
        { 
            postorder(p->lchild);
            postorder(p->rchild);
            printf(" %c ",p->data);
        }
    }
    int main()
    { 
        Bitree *root;
        root=CreateTree();
        printf("\n 先序遍历结果如下：\n");
        preorder(root);
        printf("\n 中序遍历结果如下：\n");
        inorder(root);
        printf("\n 后序遍历结果如下：\n");
        postorder(root);
        printf("\n");
        return 0;
    }
    //ABCD@EF@G@@@@H#

实验2的代码：这段代码似乎只能用float和%1d进行格式化输入 至于为什么 尚未深究 待更新

#include<cstdio>
    #include<cstring>
    #include<cstdlib>
    using namespace std;
    const int n=6;
    const int m=11;
    const int maxval=1;
    typedef char datatype;
    typedef struct{ 
        float weight;
        datatype data;
        int lchild,rchild,parent;
    }hufmtree;
    hufmtree tree[m];
    typedef struct{ 
        char bits[n];
        int start;
        datatype data;
    }codetype;
    codetype code[n];
    HUFFMAN(hufmtree tree[]){ 
        int i,j,p1,p2;
        char ch;
        float small1,small2,f;
        for(i=0;i<m;i++){ 
            tree[i].parent=0;
            tree[i].lchild=0;
            tree[i].rchild=0;
            tree[i].weight=0.0;
            tree[i].data='0';
        }
        for(i=0;i<n;i++){ 
            scanf("%f ",&f);
            tree[i].weight=f;
            scanf("%c",&ch);
            tree[i].data=ch;
        }
        for(i=n;i<m;i++){ 
            p1=0;
            p2=0;
            small1=maxval;
            small2=maxval;
            for(j=0;j<=i-1;j++)
                if(tree[j].parent==0)
                if(tree[j].weight<small1){ 
                    small2=small1;
                    small1=tree[j].weight;
                    p2=p1;
                    p1=j;
                }
                else if(tree[j].weight<small2){ 
                    small2=tree[j].weight;
                    p2=j;
                }
                tree[p1].parent=i;
                tree[p2].parent=i;
                tree[i].lchild=p1;
                tree[i].rchild=p2;
                tree[i].weight=tree[p1].weight+tree[p2].weight;
            }
    }
    HUFFMANCODE(codetype code[],hufmtree tree[])//code存放求出的哈夫曼编码的结果
    { 
        int i,c,p;
        codetype cd;
        for(i=0;i<n;i++){ 
            cd.start=n;
            c=i;
            p=tree[c].parent;
            cd.data=tree[c].data;
            while(p!=0){ 
                cd.start--;
                if(tree[p].lchild==c)
                   cd.bits[cd.start]='0';
                else
                   cd.bits[cd.start]='1';
                c=p;
                p=tree[c].parent;
            }
            code[i]=cd;
            printf("%c:",cd.data);
            for(int k=cd.start;k<n;k++)
                printf("%c",cd.bits[k]);
            printf("\n");
        }
    }
    HUFFMANDECODE(codetype code[],hufmtree tree[]){ 
        int i,c,p,b;
        int endflag=2;
        i=m-1;
        scanf("%1d",&b);
        while(b!=endflag){ 
            if(b==0)
                i=tree[i].lchild;
            else
                i=tree[i].rchild;
            if(tree[i].lchild==0){ 
               printf("%c",code[i].data);
               i=m-1;
            }
            scanf("%1d",&b);
        }
            if((tree[i].lchild!=0)&&(i!=m-1))
            printf("\nERROR\n");
    }
    int main(){ 
        printf("输入结点的权值和结点字母，用空格隔开：（如0.4 a）\n");
        HUFFMAN(tree);
        printf("\n编码结果\n");
        HUFFMANCODE(code,tree);
        printf("\n开始译码，请输入密码：\n");
        HUFFMANDECODE(code,tree);
        printf("\n");
    }
    //0.4 A
    //0.3 B
    //0.1 C
    //0.1 D
    //0.02 E
    //0.08 F