数据结构实验7-二叉树

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

发表评论

目前评论:1