您的位置: 首页  >  文章  >  数据结构上机实践第十周项目1 - 二叉树算法验证

数据结构上机实践第十周项目1 - 二叉树算法验证

分类: 文章 • 2024-11-17 13:54:27


二叉树算法验证
本次实践主要是对于二叉树算法的验证，达成对于算法熟练掌握的目的。
实践所用的二叉树算法库点击此处可以参考（编译环境：VC++6.0）

一、层次遍历算法验证
验证具体要求如下：
实现二叉树的层次遍历算法，并对用”A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))”创建的二叉树进行测试。
注：在main函数中，创建的用于测试的二叉树如下—— 
数据结构上机实践第十周项目1 - 二叉树算法验证
实现源代码：
[cpp] view plain copy
  1. //*Copyright  (c)2017,烟台大学计算机与控制工程学院*                   
  2. //*All rights reservrd.*                   
  3. //*文件名称 ：main.cpp*                   
  4. //*作者：侯成健*                
  5. //*完成时间：2017年11月23日*                    
  6. //*版本号：v1.0*                
  7. //*问题描述:测试函数*                   
  8. //*输入描述:无*                   
  9. //*程序输出:无*     
  10. #include <stdio.h>  
  11. #include "btree.h"  
  12.   
  13. void LevelOrder(BTNode *b)  
  14. {  
  15.     BTNode *p;  
  16.     BTNode *qu[MaxSize];    //定义环形队列,存放节点指针  
  17.     int front,rear; //定义队头和队尾指针  
  18.     front=rear=-1;      //置队列为空队列  
  19.     rear++;  
  20.     qu[rear]=b;     //根节点指针进入队列  
  21.     while (front!=rear) //队列不为空  
  22.     {  
  23.         front=(front+1)%MaxSize;  
  24.         p=qu[front];        //队头出队列  
  25.         printf("%c ",p->data);  //访问节点  
  26.         if (p->lchild!=NULL)    //有左孩子时将其进队  
  27.         {  
  28.             rear=(rear+1)%MaxSize;  
  29.             qu[rear]=p->lchild;  
  30.         }  
  31.         if (p->rchild!=NULL)    //有右孩子时将其进队  
  32.         {  
  33.             rear=(rear+1)%MaxSize;  
  34.             qu[rear]=p->rchild;  
  35.         }  
  36.     }  
  37. }  
  38.   
  39. int main()  
  40. {  
  41.     BTNode *b;  
  42.     CreateBTNode(b,"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))");  
  43.     printf("二叉树b: ");  
  44.     DispBTNode(b);  
  45.     printf("\n");  
  46.     printf("层次遍历序列:\n");  
  47.     LevelOrder(b);  
  48.     DestroyBTNode(b);  
  49.     return 0;  
  50. }  


运行结果截图如下：
数据结构上机实践第十周项目1 - 二叉树算法验证

二、构造算法的验证
1、由先序和中序序列构造二叉树
实现源代码如下：
[cpp] view plain copy
  1. //*Copyright  (c)2017,烟台大学计算机与控制工程学院*                   
  2. //*All rights reservrd.*                   
  3. //*文件名称 ：main.cpp*                   
  4. //*作者：侯成健*                
  5. //*完成时间：2017年11月23日*                    
  6. //*版本号：v1.0*                
  7. //*问题描述:测试函数*                   
  8. //*输入描述:无*                   
  9. //*程序输出:无*     
  10. #include <stdio.h>  
  11. #include <malloc.h>  
  12. #include "btree.h"  
  13.   
  14. BTNode *CreateBT1(char *pre,char *in,int n)  
  15. /*pre存放先序序列,in存放中序序列,n为二叉树结点个数,  
  16. 本算法执行后返回构造的二叉链的根结点指针*/  
  17. {  
  18.     BTNode *s;  
  19.     char *p;  
  20.     int k;  
  21.     if (n<=0) return NULL;  
  22.     s=(BTNode *)malloc(sizeof(BTNode));     //创建二叉树结点*s  
  23.     s->data=*pre;  
  24.     for (p=in; p<in+n; p++)                 //在中序序列中找等于*ppos的位置k  
  25.         if (*p==*pre)                       //pre指向根结点  
  26.             break;                          //在in中找到后退出循环  
  27.     k=p-in;                                 //确定根结点在in中的位置  
  28.     s->lchild=CreateBT1(pre+1,in,k);        //递归构造左子树  
  29.     s->rchild=CreateBT1(pre+k+1,p+1,n-k-1); //递归构造右子树  
  30.     return s;  
  31. }  
  32.   
  33. int main()  
  34. {  
  35.     ElemType pre[]="ABDGCEF",in[]="DGBAECF";  
  36.     BTNode *b1;  
  37.     b1=CreateBT1(pre,in,7);  
  38.     printf("b1:");  
  39.     DispBTNode(b1);  
  40.     printf("\n");  
  41.     return 0;  
  42. }  


运行结果截图如下：
数据结构上机实践第十周项目1 - 二叉树算法验证
2、由后序和中序序列构造二叉树
实现源代码如下：
[cpp] view plain copy
  1. //*Copyright  (c)2017,烟台大学计算机与控制工程学院*                   
  2. //*All rights reservrd.*                   
  3. //*文件名称 ：main.cpp*                   
  4. //*作者：侯成健*                
  5. //*完成时间：2017年11月23日*                    
  6. //*版本号：v1.0*                
  7. //*问题描述:测试函数*                   
  8. //*输入描述:无*                   
  9. //*程序输出:无*     
  10. #include <stdio.h>  
  11. #include <malloc.h>  
  12. #include "btree.h"  
  13.   
  14. BTNode *CreateBT2(char *post,char *in,int n)  
  15. /*post存放后序序列,in存放中序序列,n为二叉树结点个数,  
  16. 本算法执行后返回构造的二叉链的根结点指针*/  
  17. {  
  18.     BTNode *s;  
  19.     char r,*p;  
  20.     int k;  
  21.     if (n<=0) return NULL;  
  22.     r=*(post+n-1);                          //根结点值  
  23.     s=(BTNode *)malloc(sizeof(BTNode));     //创建二叉树结点*s  
  24.     s->data=r;  
  25.     for (p=in; p<in+n; p++)                 //在in中查找根结点  
  26.         if (*p==r)  
  27.             break;  
  28.     k=p-in;                                 //k为根结点在in中的下标  
  29.     s->lchild=CreateBT2(post,in,k);         //递归构造左子树  
  30.     s->rchild=CreateBT2(post+k,p+1,n-k-1);  //递归构造右子树  
  31.     return s;  
  32. }  
  33.   
  34. int main()  
  35. {  
  36.     ElemType in[]="DGBAECF",post[]="GDBEFCA";  
  37.     BTNode *b2;  
  38.     b2=CreateBT2(post,in,7);  
  39.     printf("b2:");  
  40.     DispBTNode(b2);  
  41.     printf("\n");  
  42.     return 0;  
  43. }  


运行结果截图如下：
数据结构上机实践第十周项目1 - 二叉树算法验证
3、由顺序存储转成二叉链存储
实现源代码如下：
[cpp] view plain copy
  1. //*Copyright  (c)2017,烟台大学计算机与控制工程学院*                   
  2. //*All rights reservrd.*                   
  3. //*文件名称 ：main.cpp*                   
  4. //*作者：侯成健*                
  5. //*完成时间：2017年11月23日*                    
  6. //*版本号：v1.0*                
  7. //*问题描述:测试函数*                   
  8. //*输入描述:无*                   
  9. //*程序输出:无*     
  10. #include <stdio.h>  
  11. #include <malloc.h>  
  12. #include "btree.h"  
  13. #define N 30  
  14. typedef ElemType SqBTree[N];  
  15. BTNode *trans(SqBTree a,int i)  
  16. {  
  17.     BTNode *b;  
  18.     if (i>N)  
  19.         return(NULL);  
  20.     if (a[i]=='#')  
  21.         return(NULL);           //当节点不存在时返回NULL  
  22.     b=(BTNode *)malloc(sizeof(BTNode)); //创建根节点  
  23.     b->data=a[i];  
  24.     b->lchild=trans(a,2*i);                 //递归创建左子树  
  25.     b->rchild=trans(a,2*i+1);               //递归创建右子树  
  26.     return(b);                              //返回根节点  
  27. }  
  28. int main()  
  29. {  
  30.     BTNode *b;  
  31.     ElemType s[]="0ABCD#EF#G####################";  
  32.     b=trans(s,1);  
  33.     printf("b:");  
  34.     DispBTNode(b);  
  35.     printf("\n");  
  36.     return 0;  
  37. }  


运行结果截图如下：
数据结构上机实践第十周项目1 - 二叉树算法验证
三、中序线索化二叉树算法验证
实现源代码如下：
[cpp] view plain copy
  1. #include <stdio.h>  
  2. #include <malloc.h>  
  3.   
  4. #define MaxSize 100  
  5. typedef char ElemType;  
  6. typedef struct node  
  7. {  
  8.     ElemType data;  
  9.     int ltag,rtag;      //增加的线索标记  
  10.     struct node *lchild;  
  11.     struct node *rchild;  
  12. } TBTNode;  
  13.   
  14. void CreateTBTNode(TBTNode * &b,char *str)  
  15. {  
  16.     TBTNode *St[MaxSize],*p=NULL;  
  17.     int top=-1,k,j=0;  
  18.     char ch;  
  19.     b=NULL;             //建立的二叉树初始时为空  
  20.     ch=str[j];  
  21.     while (ch!='\0')    //str未扫描完时循环  
  22.     {  
  23.         switch(ch)  
  24.         {  
  25.         case '(':  
  26.             top++;  
  27.             St[top]=p;  
  28.             k=1;  
  29.             break;      //为左结点  
  30.         case ')':  
  31.             top--;  
  32.             break;  
  33.         case ',':  
  34.             k=2;  
  35.             break;                          //为右结点  
  36.         default:  
  37.             p=(TBTNode *)malloc(sizeof(TBTNode));  
  38.             p->data=ch;  
  39.             p->lchild=p->rchild=NULL;  
  40.             if (b==NULL)                    //*p为二叉树的根结点  
  41.                 b=p;  
  42.             else                            //已建立二叉树根结点  
  43.             {  
  44.                 switch(k)  
  45.                 {  
  46.                 case 1:  
  47.                     St[top]->lchild=p;  
  48.                     break;  
  49.                 case 2:  
  50.                     St[top]->rchild=p;  
  51.                     break;  
  52.                 }  
  53.             }  
  54.         }  
  55.         j++;  
  56.         ch=str[j];  
  57.     }  
  58. }  
  59.   
  60. void DispTBTNode(TBTNode *b)  
  61. {  
  62.     if (b!=NULL)  
  63.     {  
  64.         printf("%c",b->data);  
  65.         if (b->lchild!=NULL || b->rchild!=NULL)  
  66.         {  
  67.             printf("(");  
  68.             DispTBTNode(b->lchild);  
  69.             if (b->rchild!=NULL) printf(",");  
  70.             DispTBTNode(b->rchild);  
  71.             printf(")");  
  72.         }  
  73.     }  
  74. }  
  75.   
  76. TBTNode *pre;                       //全局变量  
  77.   
  78. void Thread(TBTNode *&p)  
  79. {  
  80.     if (p!=NULL)  
  81.     {  
  82.         Thread(p->lchild);          //左子树线索化  
  83.         if (p->lchild==NULL)        //前驱线索  
  84.         {  
  85.             p->lchild=pre;          //建立当前结点的前驱线索  
  86.             p->ltag=1;  
  87.         }  
  88.         else p->ltag=0;  
  89.         if (pre->rchild==NULL)      //后继线索  
  90.         {  
  91.             pre->rchild=p;          //建立前驱结点的后继线索  
  92.             pre->rtag=1;  
  93.         }  
  94.         else pre->rtag=0;  
  95.         pre=p;  
  96.         Thread(p->rchild);          //右子树线索化  
  97.     }  
  98. }  
  99.   
  100. TBTNode *CreaThread(TBTNode *b)     //中序线索化二叉树  
  101. {  
  102.     TBTNode *root;  
  103.     root=(TBTNode *)malloc(sizeof(TBTNode));  //创建根结点  
  104.     root->ltag=0;  
  105.     root->rtag=1;  
  106.     root->rchild=b;  
  107.     if (b==NULL)                //空二叉树  
  108.         root->lchild=root;  
  109.     else  
  110.     {  
  111.         root->lchild=b;  
  112.         pre=root;               //pre是*p的前驱结点,供加线索用  
  113.         Thread(b);              //中序遍历线索化二叉树  
  114.         pre->rchild=root;       //最后处理,加入指向根结点的线索  
  115.         pre->rtag=1;  
  116.         root->rchild=pre;       //根结点右线索化  
  117.     }  
  118.     return root;  
  119. }  
  120.   
  121. void ThInOrder(TBTNode *tb)  
  122. {  
  123.     TBTNode *p=tb->lchild;      //指向根结点  
  124.     while (p!=tb)  
  125.     {  
  126.         while (p->ltag==0) p=p->lchild;  
  127.         printf("%c ",p->data);  
  128.         while (p->rtag==1 && p->rchild!=tb)  
  129.         {  
  130.             p=p->rchild;  
  131.             printf("%c ",p->data);  
  132.         }  
  133.         p=p->rchild;  
  134.     }  
  135. }  
  136.   
  137. int main()  
  138. {  
  139.     TBTNode *b,*tb;  
  140.     CreateTBTNode(b,"A(B(D(,G)),C(E,F))");  
  141.     printf(" 二叉树:");  
  142.     DispTBTNode(b);  
  143.     printf("\n");  
  144.     tb=CreaThread(b);  
  145.     printf(" 线索中序序列:");  
  146.     ThInOrder(tb);  
  147.     printf("\n");  
  148.     return 0;  
  149. }  



运行结果截图如下：
数据结构上机实践第十周项目1 - 二叉树算法验证
四、哈夫曼编码的算法验证
实现源代码如下：
[cpp] view plain copy
  1. //*Copyright  (c)2017,烟台大学计算机与控制工程学院*                   
  2. //*All rights reservrd.*                   
  3. //*文件名称 ：main.cpp*                   
  4. //*作者：侯成健*                
  5. //*完成时间：2017年11月23日*                    
  6. //*版本号：v1.0*                
  7. //*问题描述:测试函数*                   
  8. //*输入描述:无*                   
  9. //*程序输出:无*     
  10. #include <stdio.h>  
  11. #include <string.h>  
  12.   
  13. #define N 50        //叶子结点数  
  14. #define M 2*N-1     //树中结点总数  
  15.   
  16. //哈夫曼树的节点结构类型  
  17. typedef struct  
  18. {  
  19.     char data;  //结点值  
  20.     double weight;  //权重  
  21.     int parent;     //双亲结点  
  22.     int lchild;     //左孩子结点  
  23.     int rchild;     //右孩子结点  
  24. } HTNode;  
  25.   
  26. //每个节点哈夫曼编码的结构类型  
  27. typedef struct  
  28. {  
  29.     char cd[N]; //存放哈夫曼码  
  30.     int start;  
  31. } HCode;  
  32.   
  33. //构造哈夫曼树  
  34. void CreateHT(HTNode ht[],int n)  
  35. {  
  36.     int i,k,lnode,rnode;  
  37.     double min1,min2;  
  38.     for (i=0; i<2*n-1; i++)         //所有结点的相关域置初值-1  
  39.         ht[i].parent=ht[i].lchild=ht[i].rchild=-1;  
  40.     for (i=n; i<2*n-1; i++)         //构造哈夫曼树  
  41.     {  
  42.         min1=min2=32767;            //lnode和rnode为最小权重的两个结点位置  
  43.         lnode=rnode=-1;  
  44.         for (k=0; k<=i-1; k++)  
  45.             if (ht[k].parent==-1)   //只在尚未构造二叉树的结点中查找  
  46.             {  
  47.                 if (ht[k].weight<min1)  
  48.                 {  
  49.                     min2=min1;  
  50.                     rnode=lnode;  
  51.                     min1=ht[k].weight;  
  52.                     lnode=k;  
  53.                 }  
  54.                 else if (ht[k].weight<min2)  
  55.                 {  
  56.                     min2=ht[k].weight;  
  57.                     rnode=k;  
  58.                 }  
  59.             }  
  60.         ht[i].weight=ht[lnode].weight+ht[rnode].weight;  
  61.         ht[i].lchild=lnode;  
  62.         ht[i].rchild=rnode;  
  63.         ht[lnode].parent=i;  
  64.         ht[rnode].parent=i;  
  65.     }  
  66. }  
  67.   
  68. //实现哈夫曼编码  
  69. void CreateHCode(HTNode ht[],HCode hcd[],int n)  
  70. {  
  71.     int i,f,c;  
  72.     HCode hc;  
  73.     for (i=0; i<n; i++) //根据哈夫曼树求哈夫曼编码  
  74.     {  
  75.         hc.start=n;  
  76.         c=i;  
  77.         f=ht[i].parent;  
  78.         while (f!=-1)   //循序直到树根结点  
  79.         {  
  80.             if (ht[f].lchild==c)    //处理左孩子结点  
  81.                 hc.cd[hc.start--]='0';  
  82.             else                    //处理右孩子结点  
  83.                 hc.cd[hc.start--]='1';  
  84.             c=f;  
  85.             f=ht[f].parent;  
  86.         }  
  87.         hc.start++;     //start指向哈夫曼编码最开始字符  
  88.         hcd[i]=hc;  
  89.     }  
  90. }  
  91.   
  92. //输出哈夫曼编码  
  93. void DispHCode(HTNode ht[],HCode hcd[],int n)  
  94. {  
  95.     int i,k;  
  96.     double sum=0,m=0;  
  97.     int j;  
  98.     printf("  输出哈夫曼编码:\n"); //输出哈夫曼编码  
  99.     for (i=0; i<n; i++)  
  100.     {  
  101.         j=0;  
  102.         printf("      %c:\t",ht[i].data);  
  103.         for (k=hcd[i].start; k<=n; k++)  
  104.         {  
  105.             printf("%c",hcd[i].cd[k]);  
  106.             j++;  
  107.         }  
  108.         m+=ht[i].weight;  
  109.         sum+=ht[i].weight*j;  
  110.         printf("\n");  
  111.     }  
  112.     printf("\n  平均长度=%g\n",1.0*sum/m);  
  113. }  
  114.   
  115. int main()  
  116. {  
  117.     int n=8,i;      //n表示初始字符串的个数  
  118.     char str[]= {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'};  
  119.     double fnum[]= {0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.1};  
  120.     HTNode ht[M];  
  121.     HCode hcd[N];  
  122.     for (i=0; i<n; i++)  
  123.     {  
  124.         ht[i].data=str[i];  
  125.         ht[i].weight=fnum[i];  
  126.     }  
  127.     printf("\n");  
  128.     CreateHT(ht,n);  
  129.     CreateHCode(ht,hcd,n);  
  130.     DispHCode(ht,hcd,n);  
  131.     printf("\n");  
  132.     return 0;  
  133. }  


运行结果截图如下：
数据结构上机实践第十周项目1 - 二叉树算法验证

相关推荐