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

忘是亡心i 2021-12-14 09:17 213阅读 0赞

###  ###

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

Time Limit: 1000 ms Memory Limit: 65536 KiB

#### Problem Description ####

已知一棵二叉树的前序遍历和中序遍历，求二叉树的后序遍历和层序遍历。

#### Input ####

输入数据有多组，第一行是一个整数t (t<1000)，代表有t组测试数据。每组包括两个长度小于50 的字符串，第一个字符串表示二叉树的先序遍历序列，第二个字符串表示二叉树的中序遍历序列。

#### Output ####

每组第一行输出二叉树的后序遍历序列，第二行输出二叉树的层次遍历序列。

#### Sample Input ####

2
    abdegcf
    dbgeafc
    xnliu
    lnixu

#### Sample Output ####

dgebfca
    abcdefg
    linux
    xnuli
    
    提示：本题用到了还原二叉树的知识点，即通过前序+中序来还原二叉树，从而输出它的后序遍历和层序遍历。
    
    代码实现如下（g++）：

#include <bits/stdc++.h>
    
    using namespace std;
    
    typedef struct node
    {
        char data;
        struct node *left;
        struct node *right;
    } node;//typedef定义struct node结构体
    
    node *create(int n,char *a,char *b)
    {
        node *root;
        char *p;//定义一个指针，用来查找b数组
        if(n==0)
            return NULL;//如果n==0，即长度为空，不存在
        root=(node *)malloc(sizeof(node));//申请空间
        root->data=a[0];//注意a数组是前序遍历，所以它的第一个元素必定是该树的根节点
        for(p=b; p!='\0'; p++)
        {
            if(*p==a[0])//一步步找b数组中a[0]的位置，找到位置记下来
                break;
        }
        int t=p-b;//左子树长度为p-b
        root->left=create(t,a+1,b);//三个变量分别为左子树长度，指向a的下一位，指向b
        root->right=create(n-t-1,a+t+1,p+1);//三个变量分别为右子树长度，指向a+左子树长度+根节点长度，指向p的下一位
        return root;
    }
    
    void housort(node *root)//后序遍历
    {
        if(root)
        {
        housort(root->left);//遍历左儿子
        housort(root->right);//遍历右儿子
        cout<<root->data;//遍历根节点，输出根节点
        }
    }
    
    void cengci(node *root)//层序遍历，需要用到队列
    {
        queue<node *>t;
        t.push(root);
        while(!t.empty())
        {
            root=t.front();
            t.pop();
            if(root)
            {
                cout<<root->data;
                t.push(root->left);
                t.push(root->right);//将左右节点依次进队，先进先出，很好理解
            }
        }
    }
    
    int main()
    {
        char a[55],b[55];
        int n;
        while(~scanf("%d",&n))
        {
            node *root;
            scanf("%s",a);
            scanf("%s",b);
            n=strlen(a);
            root=create(n,a,b);
            housort(root);
            printf("\n");
            cengci(root);
            printf("\n");
        }
        return 0;
    }
    
    
    /***************************************************
    Result: Accepted
    Take time: 0ms
    Take Memory: 200KB
    ****************************************************/

转载于:https://www.cnblogs.com/jkxsz2333/p/9498627.html