2137 数据结构实验之求二叉树后序遍历和层次遍历

以你之姓@ 2022-07-14 21:08 134阅读 0赞

[数据结构实验之求二叉树后序遍历和层次遍历][Link 1]

/*#include<cstdio>
    #include<cstring>
    #include<cstdlib>
    #include<iostream>*/
    #include <bits/stdc++.h>
    using namespace std;
    
    int n;
     struct node
    {
        char data;
        struct node *lchild,*rchild;
    }tree;
    /*中序遍历中根节点的左边全都是左子树的中序，
    右边全是右子树中序。然而每个子树的先序序
    列的第一个节点是子树的根，而且向后移动中
    序查找得到的左子树节点数便可分开得到左右子树。
    因此可以用递归分而治之*/
    
    struct node *creat(char *a1,char*a2,int n)
    {
        struct node*root;
        if(n<=0)
            return NULL;
        else
        {
            root = (struct node*)malloc(sizeof(struct node));
            root->data=*a1;//先序的第一个节点指定是当前子树的根
            char *a;
            for(a=a2;a!=NULL;a++)
            {
                if(*a==*a1)
                break;
            }
            int lchildroot=a-a2;/*左子树节点个数*/
            root->lchild=creat(a1+1,a2,lchildroot);//分而治之创建左子树
            root->rchild=creat(a1+1+lchildroot,a+1,n-lchildroot-1);//分而治之创建右子树
        }
           return root;
    };
    void houxu(struct node *root)
    {
        if(root)
        {
            houxu(root->lchild);
            houxu(root->rchild);
            printf("%c",root->data);
        }
    }
    void sequence(struct node *root)
    {
        int out=0,in=0,f;
        struct node *q[100];
        q[in++]=root;
        while(in>out)
        {
            if(q[out])
            {
    
                printf("%c",q[out]->data);
                q[in++]=q[out]->lchild;
                q[in++]=q[out]->rchild;
            }
            out++;
        }
    }
    /*void cengci(tree *root)
    {
        tree *p[51];//用指针来控制。
        p[0] = root;
        int f = 0,r = 1;
        while(f < r)//每一个p[f]都是子树树根
        {
            if(p[f])//因为为二叉树所以最多有2个子树，且只有当二叉树不为空时才可能有数据，为空时即可跳过，不打印
            {
                printf("%c",p[f]->data);
                p[r++] = p[f]->l;
                p[r++] = p[f]->r;//
            }
            f++;
        }
    }
    
    void sequence(BiTree T)//bfs算法完成层次遍历，使用队列存储数据。
    {
        BiTree p=T;
        queue<BiTree>queue;
        queue.push(p);
        while(!queue.empty())
        {
            p=queue.front();
            cout<<p->data;
            queue.pop();
            if(p->lchild!=NULL)
            {
                queue.push(p->lchild);
            }
            if(p->rchild!=NULL)
            {
                queue.push(p->rchild);
            }
        }
    }
    */
    
    int main()
    {
        char a1[1006],a2[1006];
        int t,i;
        scanf("%d%*c",&t);
        while(t--)
            {
                char *s1,*s2;
               gets(a1);
            gets(a2);
                s1=a1;s2=a2;
                n=strlen(a1);
            struct node *root;
           root=creat(s1,s2,n);
            houxu(root);
            printf("\n");
            sequence(root);
               printf("\n");
            }
        return 0;
    }

[Link 1]: http://www.sdutacm.org/onlinejudge2/index.php/Home/Index/problemdetail/pid/2137.html