数据结构实验6-树

avatar 2016年12月05日11:42:56 0 5391 views
博主分享免费Java教学视频，B站账号：Java刘哥 ，长期提供技术问题解决、项目定制：本站商品点此
 
  1. /*
  2. 编写算法函数void levelorder(tree t)实现树的层次遍历。
  3. */
  5. #include "tree.h"
  7. void levelorder(tree t)    /* t为指向树根结点的指针*/
  8. {
  9.     tree queue[100];
  10.     int f,r,i; //f,r分别为队头和队尾指针
  11.     tree p;
  12.     f=0; r=1; queue[0]=t;
  13.     while(f<r)
  14.     {
  15.         p=queue[f] ;f++;printf("%c",p->data);  //访问队头元素
  16.         for(i=0;i<m;i++) //将刚被访问的元素的所有子女结点依次进队 
  17.         {
  18.             if(p->child[i])
  19.             {
  20.                 queue[r]=p->child[i];
  21.                 r++;
  22.             }
  23.         }
  24.     }
  25. }
  27.  int main()
  28.  {
  29.    tree t;
  30.    printf("please input the preorder sequence of the tree:\n");
  31.    t=createtree();
  32.    printf("\nthe levelorder is:");
  33.    levelorder(t);
  34.    return 0;
  35.  }

  1. /*
  2. 假设树采用指针方式的孩子表示法表示，试编写一个非递归函数void PreOrder1(tree root)，实现树的前序遍历算法。
  3. */
  4. #include "tree.h"
  5. void  PreOrder1(tree root)
  6. {
  7.     tree stack[MAXLEN];
  8.     int top=-1,i;
  9.     while(top!=-1||root)
  10.     {
  11.         if(root)                        //子树不为空
  12.         {
  13.             printf("%c",root->data);
  14.             for(i=m-1;i>0;i--)
  15.             {
  16.                 if(root->child[i]!=NULL)    //将不为空的子结点进栈
  17.                     stack[++top]=root->child[i];
  18.             }
  19.             root=root->child[0];        //从第一个子结点开始遍历
  20.         }
  21.         else                            //子树为空，出栈
  22.         {
  23.             root=stack[top--];
  24.         }
  25.     }
  26. }
  28. int main ()
  29. {
  30.         tree root;
  31.         printf("please input the preorder sequence of the tree:\n");
  32.         root =createtree();
  33.         printf("前序序列是：\n");
  34.         PreOrder1(root);
  35.         return 0;
  36. }

  1. /*
  2.    假设树采用指针方式的孩子表示法表示，试编写一个非递归函数void PostOrder1(tree t)，实现树的后序遍历算法。
  3. */
  5. #include "tree.h"
  6. int PostOrder1(tree root)
  7. {
  8.     tree treeStack[MAXLEN];     //待处理结点
  9.     tree overStack[MAXLEN];     //已处理完的结点
  10.     int top=-1,top1=-1,i;
  12.     if(root)
  13.         treeStack[++top]=root; //根结点进栈
  14.     while(top!=-1)
  15.     {
  16.         root=treeStack[top--];  //取一个待处理结点
  17.         for(i=0;i<m;i++)        //将root的所有子结点进栈
  18.         {
  19.             if(root->child[i])
  20.                 treeStack[++top]=root->child[i];
  21.         }
  22.         overStack[++top1]=root; //处理完root，将root入overStack
  23.     }
  24.     while(top1!=-1)             //输出
  25.         printf("%c",overStack[top1--]->data);
  26. }
  28. int main ()
  29. {
  30.     tree root;
  31.     printf("please input the preorder sequence of the tree:\n");
  32.     root =createtree();
  33.     printf("后序序列是：\n");
  34.     PostOrder1(root);
  35.     return 0;
  36. }

  1. /*
  2. 假设树采用指针方式的孩子表示法表示，试编写一个函数int equal(tree t1, tree t2)，
  3. 判断两棵给定的树是否等价（两棵树等价当且仅当其根结点的值相等且其对应的子树均相互等价）。
  4. */
  5. #include "tree.h"
  6. #define TRUE  1
  7. #define FALSE 0
  9. int equal(tree t1,tree t2)
  10. {
  11.     int flag=TRUE,i;
  12.     if(!t1&&!t2)                //若两树为空，则相等
  13.         return TRUE;
  14.     else if(!t1&&t2||t1&&!t2)   //若有一树为空，则不相等
  15.         return FALSE;
  16.     else if(t1->data!=t2->data)
  17.         return FALSE;
  18.     else
  19.     {
  20.         for(i=0;i<m;i++)
  21.         {
  22.             if(t1->child[i]==t2->child[i])
  23.                 flag=flag&&equal(t1->child[i],t2->child[i]);
  24.         }
  25.         return flag;
  26.     }
  27. }
  30. int main ()
  31. {
  32.     tree t1,t2;
  33.     printf("please input the preorder sequence of the tree:\n");
  34.     t1=createtree();
  35.     getchar();
  36.     printf("please input the preorder sequence of the tree:\n");
  37.     t2=createtree();
  38.     if ( equal(t1,t2) == TRUE)
  39.     {
  40.         printf ("两树相等\n");
  41.     }
  42.     else
  43.     {
  44.         printf ("两树不相等\n");
  45.     }
  47.     return 0;
  48. }

  1. /*
  2. 假设树采用指针方式的孩子表示法存储结构，试编写一个函数tree Ct(char s[])，
  3. 根据输入的树的括号表示字符串s，生成树的存储结构。例如，若要建立教材图6.4所示的树，
  4. 应输入A（B（E，F）,C,D（G（I，J，K）,H））。（说明，tree.h中定义的常量m表示树的最
  5. 大度，请根据建树的需要自行修改m的值）
  6.  
  7. */
  9. #include "tree.h"
  10. /*请将本函数补充完整，并进行测试*/
  11. tree Ct(char s[MAXLEN])
  12. {
  13.    tree stack[MAXLEN],parent=NULL,child=NULL;
  14.    int n=0,top=0,done=0,i;
  16.    while(done==0&&s[n]!='\0')   //未完成并且字符串不为空
  17.    {
  18.        if(s[n]=='(')            //遇到左括号，则其前面的结点成为父结点
  19.        {
  20.            n++;
  21.            parent=child;
  22.            stack[top++]=parent; //将父结点进栈
  23.        }
  24.        else if(s[n]==')')       //遇到右括号，父结点出栈
  25.        {
  26.            n++;
  27.            parent=stack[--top];
  28.            if(top==0)           //若栈顶无元素，则结束
  29.             done=1;
  30.            else
  31.             parent=stack[top-1];//换下一个父结点收集子结点
  32.        }
  33.        else if(s[n]==',')
  34.         n++;
  35.        else
  36.        {
  37.            child=(tree)malloc(sizeof(node));
  38.            child->data=s[n];
  39.            for(i=0;i<m;i++)
  40.             child->child[i]=NULL;
  41.            if(parent!=NULL)      //若父结点不为空，则将其挂到父结点上
  42.            {
  43.                for(i=0;i<m;i++)
  44.                 if(parent->child[i]==NULL)
  45.                 {
  46.                     parent->child[i]=child;
  47.                     break;
  48.                 }
  49.            }
  50.            n++;
  51.        }
  52.    }
  53.    return parent;
  54. }
  57. int main ()
  58. {
  59.     char s[MAXLEN];
  60.     tree root = NULL;
  61.     printf ("请用树的括号表示法输入一棵树:\n");
  62.     scanf ("%s",s);
  63.     root = Ct(s);
  64.     preorder(root);  /*前序遍历树*/
  65.     return 0;
  66. }

本文地址：http://liuyanzhao.com/3586.html

转载请注明
历史上的今天
十二月
05日
  • 微信
  • 交流学习，资料分享
  • weinxin
  • 个人淘宝
  • 店铺名：言曌博客咨询部

  • (部分商品未及时上架淘宝)
avatar

发表评论

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

  

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