1020. Tree Traversals (25)

最新推荐文章于 2023-08-19 19:24:19 发布

puppet_pyt

最新推荐文章于 2023-08-19 19:24:19 发布

阅读量200

点赞数

分类专栏： pat甲级

本文链接：https://blog.csdn.net/puppet_pyt/article/details/70174921

版权

pat甲级专栏收录该内容

55 篇文章

订阅专栏

Suppose that all the keys in a binary tree are distinct positive integers. Given the postorder and inorder traversal sequences, you are supposed to output the level order traversal sequence of the corresponding binary tree.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (<=30), the total number of nodes in the binary tree. The second line gives the postorder sequence and the third line gives the inorder sequence. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print in one line the level order traversal sequence of the corresponding binary tree. All the numbers in a line must be separated by exactly one space, and there must be no extra space at the end of the line.

Sample Input:

7
2 3 1 5 7 6 4
1 2 3 4 5 6 7

Sample Output:

4 1 6 3 5 7 2

已知中序后序求层序，方法是根据后序找到根，再根据中序中根的位置找到右子树和左子树，题目中的树大概是下面这个样子

首先找到后序遍历中root肯定是最后一个元素4然后找到4在中序的位置，那么4右边的都为他的右子树4左边的都为他的左子树，然后下一个后序根为6，即右子树的根为6，6左边的为他左子树，右边的为他的右子树，依次递归。至于为什么是这样，因为后序遍历根始终是在其子树遍历完才会遍历到，而中序遍历则根在他左子树遍历好后经过根再遍历右子树。

前序遍历：根->左子树->右子树

中序遍历: 左子树->根->右子树

后序遍历: 左子树->右子树->根

/***已知后序中序求二叉树***/
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

typedef struct Tree{
    int data;
    Tree *left;
    Tree *right;
}Tree;

Tree *root = NULL;
vector<int> post;
vector<int> in;
int postindex;

Tree *create(int left, int right)
{
    if(left > right)
    {
        return NULL;
    }
    vector<int>::size_type i;
    int rootdata = post[postindex];//取后序遍历的最后一个数据为根
    postindex--;
    Tree *p = new Tree();
    p->data = rootdata;
    for(i=0; i<in.size(); i++)//找到根在中序的位置
    {
        if(in[i] == rootdata)
            break;
    }
    p->right = create(i+1, right);//中序根右边的数据为根的右子树，左边的为根的左子树，
    p->left = create(left, i-1);
    return p;
}

void levelorder()//层序遍历
{
    bool flag = true;
    queue<Tree*> myque;
    Tree *p;
    p = root;
    myque.push(p);
    while(!myque.empty())
    {
        Tree *cur = myque.front();
        myque.pop();
        if(cur->left)
            myque.push(cur->left);
        if(cur->right)
            myque.push(cur->right);
        if(flag)
        {
            cout << cur->data;
            flag = false;
        }
        else{
            cout << " " << cur->data;
        }
    }
}
int main()
{
    int n, temp;
    cin >> n;
    for(int i=0; i<n; i++)
    {
        cin >> temp;
        post.push_back(temp);
    }
    for(int i=0; i<n; i++)
    {
        cin >> temp;
        in.push_back(temp);
    }
    postindex = post.size()-1;
    root = create(0, n-1);
    levelorder();
    return 0;
}