【C语言】数据结构C语言版实验6 树

Love The Way You Lie 2022-12-27 09:14 134阅读 0赞

/*
    编写算法函数void levelorder(tree t)实现树的层次遍历。
    */
    #include "tree.h"
    void levelorder(tree t)    /* t为指向树根结点的指针*/
    {
        tree queue[100];
        int f,r,i; //f,r分别为队头和队尾指针
        tree p;
        f=0; r=1; queue[0]=t;
        while(f<r)
        {
            p=queue[f] ;f++;printf("%c",p->data);  //访问队头元素
            for(i=0;i<m;i++) //将刚被访问的元素的所有子女结点依次进队 
            {
                if(p->child[i])
                {
                    queue[r]=p->child[i];
                    r++;
                }
            }
        }
    }
     int main()
     {
       tree t;
       printf("please input the preorder sequence of the tree:\n");
       t=createtree();
       printf("\nthe levelorder is:");
       levelorder(t);
       return 0;
     }

/*
    假设树采用指针方式的孩子表示法表示，试编写一个非递归函数void PreOrder1(tree root)，实现树的前序遍历算法。
    */
    #include "tree.h"
    void  PreOrder1(tree root)
    {
        tree stack[MAXLEN];
        int top=-1,i;
        while(top!=-1||root)
        {
            if(root)                        //子树不为空
            {
                printf("%c",root->data);
                for(i=m-1;i>0;i--)
                {
                    if(root->child[i]!=NULL)    //将不为空的子结点进栈
                        stack[++top]=root->child[i];
                }
                root=root->child[0];        //从第一个子结点开始遍历
            }
            else                            //子树为空，出栈
            {
                root=stack[top--];
            }
        }
    }
    int main ()
    {
            tree root;
            printf("please input the preorder sequence of the tree:\n");
            root =createtree();
            printf("前序序列是：\n");
            PreOrder1(root);
            return 0;
    }

/*
       假设树采用指针方式的孩子表示法表示，试编写一个非递归函数void PostOrder1(tree t)，实现树的后序遍历算法。
    */
    #include "tree.h"
    int PostOrder1(tree root)
    {
        tree treeStack[MAXLEN];     //待处理结点
        tree overStack[MAXLEN];     //已处理完的结点
        int top=-1,top1=-1,i;
        if(root)
            treeStack[++top]=root; //根结点进栈
        while(top!=-1)
        {
            root=treeStack[top--];  //取一个待处理结点
            for(i=0;i<m;i++)        //将root的所有子结点进栈
            {
                if(root->child[i])
                    treeStack[++top]=root->child[i];
            }
            overStack[++top1]=root; //处理完root，将root入overStack
        }
        while(top1!=-1)             //输出
            printf("%c",overStack[top1--]->data);
    }
    int main ()
    {
        tree root;
        printf("please input the preorder sequence of the tree:\n");
        root =createtree();
        printf("后序序列是：\n");
        PostOrder1(root);
        return 0;
    }

/*
    假设树采用指针方式的孩子表示法表示，试编写一个函数int equal(tree t1, tree t2)，
    判断两棵给定的树是否等价(两棵树等价当且仅当其根结点的值相等且其对应的子树均相互等价)。
    */
    #include "tree.h"
    #define TRUE  1
    #define FALSE 0
    int equal(tree t1,tree t2)
    {
        int flag=TRUE,i;
        if(!t1&&!t2)                //若两树为空，则相等
            return TRUE;
        else if(!t1&&t2||t1&&!t2)   //若有一树为空，则不相等
            return FALSE;
        else if(t1->data!=t2->data)
            return FALSE;
        else
        {
            for(i=0;i<m;i++)
            {
                if(t1->child[i]==t2->child[i])
                    flag=flag&&equal(t1->child[i],t2->child[i]);
            }
            return flag;
        }
    }
    int main ()
    {
        tree t1,t2;
        printf("please input the preorder sequence of the tree:\n");
        t1=createtree();
        getchar();
        printf("please input the preorder sequence of the tree:\n");
        t2=createtree();
        if ( equal(t1,t2) == TRUE)
        {
            printf ("两树相等\n");
        }
        else
        {
            printf ("两树不相等\n");
        }
        return 0;
    }

/*
    假设树采用指针方式的孩子表示法存储结构，试编写一个函数tree Ct(char s[])，
    根据输入的树的括号表示字符串s，生成树的存储结构。例如，若要建立教材图6.4所示的树，
    应输入A(B(E，F),C,D(G(I，J，K),H))。(说明，tree.h中定义的常量m表示树的最
    大度，请根据建树的需要自行修改m的值)
     
    */
    #include "tree.h"
    /*请将本函数补充完整，并进行测试*/
    tree Ct(char s[MAXLEN])
    {
       tree stack[MAXLEN],parent=NULL,child=NULL;
       int n=0,top=0,done=0,i;
       while(done==0&&s[n]!='\0')   //未完成并且字符串不为空
       {
           if(s[n]=='(')            //遇到左括号，则其前面的结点成为父结点
           {
               n++;
               parent=child;
               stack[top++]=parent; //将父结点进栈
           }
           else if(s[n]==')')       //遇到右括号，父结点出栈
           {
               n++;
               parent=stack[--top];
               if(top==0)           //若栈顶无元素，则结束
                done=1;
               else
                parent=stack[top-1];//换下一个父结点收集子结点
           }
           else if(s[n]==',')
            n++;
           else
           {
               child=(tree)malloc(sizeof(node));
               child->data=s[n];
               for(i=0;i<m;i++)
                child->child[i]=NULL;
               if(parent!=NULL)      //若父结点不为空，则将其挂到父结点上
               {
                   for(i=0;i<m;i++)
                    if(parent->child[i]==NULL)
                    {
                        parent->child[i]=child;
                        break;
                    }
               }
               n++;
           }
       }
       return parent;
    }
    int main ()
    {
        char s[MAXLEN];
        tree root = NULL;
        printf ("请用树的括号表示法输入一棵树:\n");
        scanf ("%s",s);
        root = Ct(s);
        preorder(root);  /*前序遍历树*/
        return 0;
    }