数据结构实验7-二叉树

avatar 2016年12月05日12:21:11 0 2643 views
 
  1. /*
  3. 编写算法函数void preorder1(bintree t)实现二叉树t的非递归前序遍历。
  5. */
  7. #include "bintree.h"
  8. char *a="ABC##D#E##F##";  /*扩充二叉树序树t的前序序列*/
  10. /*函数preorder1()的功能是非递归前序遍历二叉树t，请将函数补充完整并调试运行*/
  11. void preorder1(bintree t)
  12. {
  13.     seqstack s;//顺序栈s 
  14.     s.top=0;
  15.     while((t) || (s.top!=0)) //当前处理的子树不为空或栈不为空则循环 
  16.     {
  17.         if(t)
  18.         {
  19.             printf("%c ",t->data);
  20.             push(&s,t);
  21.             t=t->lchild;
  22.         }
  23.         else
  24.         {
  25.             t=pop(&s);
  26.             t=t->rchild;
  27.         }
  28.     }
  29. }
  30. int main()
  31. {   bintree t;
  32.     t=creatbintree();   /*建立二叉树t的存储结构*/
  33.     printf("二叉树的前序序列为：\n");
  34.     preorder1(t);       /*前序非递归遍历二叉树*/
  35.     return 0;
  36. }
 
  1. /*
  2. 编写算法函数void levelbintree(bintree t)，实现二叉树的层次遍历。
  3. */
  5. #include "bintree.h"
  6. char *a="ABC##D#E##F##";              /*扩充二叉树序树t的前序序列*/
  7. void levelbintree(bintree t)
  8. {
  9.     bintree queue[100];
  10.     int f=0,r=1;
  11.     bintree p;
  12.     queue[0]=t;
  13.     while(f<r)
  14.     {
  15.         p=queue[f]; f++; printf("%c",p->data);
  16.         if(p->lchild)
  17.             queue[r++]=p->lchild;
  18.         if(p->rchild)
  19.             queue[r++]=p->rchild;
  20.     }
  21. }
  22. int main()
  23. {   bintree t;
  24.     t=creatbintree();       /*建立二叉树t的存储结构*/
  25.     printf("二叉树的层次序列为：\n");
  26.     levelbintree(t);       /*层次遍历二叉树*/
  27.     return 0;
  28. }
 
  1. /*
  2. 编写函数bintree prelist(bintree t)，bintree postfirst(bintree t)，
  3. 分别返回二叉树t在前序遍历下的最后一个结点地址和后序遍历下的第一个结点地址。
  4. */
  6. #include "bintree.h"
  7. char *a="ABC##D##EF#G###";  /*扩充二叉树序树t的前序序列*/
  8. bintree prelast(bintree t)
  9. {    //右下叶子结点                                                
  10.     bintree p;
  11.     if(t)
  12.     {
  13.         p=t;
  14.         while(p&&p->lchild||p->rchild)
  15.         {
  16.             if(p->rchild)
  17.             {
  18.                 p=p->rchild;
  19.             }
  20.             else
  21.             {
  22.                 p=p->lchild;
  23.             }
  24.         }
  25.     }
  26.     return p; //返回前序序列最后一个结点G 
  27. }
  28. bintree postfirst(bintree t)
  29. {                //后序遍历是左子树-右子树-根结点 ,二叉树的左下叶子结点是第一个 
  30.     bintree p;
  31.     if(t)
  32.     {
  33.         while(p&&p->lchild||p->rchild)
  34.         {
  35.             if(p->lchild)
  36.             {
  37.                 p=p->lchild;
  38.             }
  39.             else
  40.             {
  41.                 p=p->rchild;
  42.             }
  43.         }
  44.     }
  45.     return p;//返回后序序列第一个结点 C
  46. }
  48. int main()
  49. {   bintree t,p,q;
  50.     t=creatbintree();       /*建立二叉树t的存储结构*/
  51.      p=prelast(t);
  52.     //q=postfirst(t);
  53.     if (t!=NULL)
  54.             { printf("前序遍历最后一个结点为：%c\n",p->data);
  55.               // printf("后序遍历第一个结点为：%c\n",q->data);
  56.             }
  57.      else    printf("二叉树为空！");
  58.     return 0;
  59. }
 
  1. /*
  2. 假设二叉树采用链式方式存储，t为其根结点，编写一个函数int Depth(bintree t, char x)，求值为x的结点在二叉树中的层次。
  3. */
  4. #include "bintree.h"
  5. char *a="ABC##D##EF#G###";          /*扩充二叉树序树t的前序序列*/
  7. /*
  8.      函数Depth，功能：求结点x所在的层次
  9. */
  11. int Depth(bintree t,char x)
  12. {
  13.     int num1,num2,n;//num1,num2分别记录在左子树，右子树中查找到x的层数,n记录最终返回的结果层数
  14.     if(t==NULL)
  15.     {
  16.         return 0;
  17.     }
  18.     else
  19.     {
  20.         if(t->data==x)
  21.         {
  22.             return 1;
  23.         }
  24.         num1=Depth(t->lchild,x);
  25.         num2=Depth(t->rchild,x);
  26.         n=num1+num2; //num1和num2之中必有一个为0 
  27.         if(num1!=0||num2!=0) //找到了x ，往回数 
  28.         {
  29.             n++;
  30.         }
  31.     }
  32.     return n;
  33. }
  34. int main()
  35. {  bintree root;
  36.    char x;
  37.    int k=0;
  38.    root=creatbintree();
  39.    printf("请输入树中的1个结点值：\n");
  40.    scanf("%c",&x);
  41.    k=Depth(root,x);
  42.    printf("%c结点的层次为%d\n",x,k);
  43. }
 
  1. /*
  2.    试编写一个函数，将一棵给定二叉树中所有结点的左、右子女互换。
  3. */
  4. #include "bintree.h"
  5. char *a="ABC##D##EF#G###";          /*扩充二叉树序树t的前序序列*/
  6. /*请将本函数补充完整，并进行测试*/
  7. void change(bintree t)
  8. {
  9.     bintree p;
  10.     if(t)
  11.     {
  12.         p=t->lchild; //交换 
  13.         t->lchild=t->rchild;
  14.         t->rchild=p;
  15.         change(t->lchild); //继续递归 
  16.         change(t->rchild);
  17.     }
  18. }
  19. int main()
  20. {  bintree root;
  21.    root=creatbintree();
  22.    change(root);
  23.    preorder(root);
  24. }
  1. /*
  2. 试编写一个递归函数bintree buildBintree(char *pre, char *mid, int length)，
  3. 根据二叉树的前序序列pre、中序序列mid和前序序列长度length，构造二叉树的二叉链表存储结构，
  4. 函数返回二叉树的树根地址。
  5. */
  7. #include "bintree.h"
  8. #include <string.h>
  9. char *a="";
  10. /*请将本函数补充完整，并进行测试*/
  11. bintree buildBintree(char *pre, char *mid,int length)
  12. {
  13.     bintree t;
  14.     int i=0;
  15.     if(length)
  16.     {
  17.         t=(bintree)malloc(sizeof(binnode)); //生成新结点
  18.         t->data=pre[i];
  19.         while(i<length&&mid[i]!=pre[0])     //在中序遍历中查找根结点的位置
  20.             i++;
  21.         t->lchild=buildBintree(pre+1,mid,i);
  22.         t->rchild=buildBintree(pre+i+1,mid+i+1,length-i-1);
  23.     }
  24.     else
  25.         return NULL;
  26.     return t;
  27. }
  28. int main()
  29. {   bintree root;
  30.     char pre[100],mid[100];
  31.     puts("请输入前序序列：");
  32.     gets(pre);
  33.     puts("请输入中序序列：");
  34.     gets(mid);
  35.     root=buildBintree(pre,mid,strlen(pre));
  36.     puts("后序序列是：");
  37.     postorder(root);
  38. }
头文件这里就不贴出来了     本文地址：http://liuyanzhao.com/3411.html 转载请注明
历史上的今天
December
05日
  • 微信
  • 交流学习，有偿服务
  • weinxin
  • 博客/Java交流群
  • 资源分享，问题解决，技术交流。群号：590480292
  • weinxin
avatar

发表评论

avatar 登录者：匿名
可以匿名评论或者登录后台评论，评论回复后会有邮件通知

  

已通过评论：0   待审核评论数：0