信息学奥赛一本通数据结构 1364：二叉树遍历(flist) 第三章树

长春高老师编程

488人浏览 · 2024-03-26 15:58:23

长春高老师编程 · 2024-03-26 15:58:23 发布

1364：二叉树遍历(flist)

时间限制: 1000 ms 内存限制: 65536 KB

【题目描述】

树和二叉树基本上都有先序、中序、后序、按层遍历等遍历顺序，给定中序和其它一种遍历的序列就可以确定一棵二叉树的结构。

假定一棵二叉树一个结点用一个字符描述，现在给出中序和按层遍历的字符串，求该树的先序遍历字符串。

【输入】

两行，每行是由字母组成的字符串（一行的每个字符都是唯一的），分别表示二叉树的中序遍历和按层遍历的序列。

【输出】

一行，表示二叉树的先序序列。

【输入样例】

DBEAC
ABCDE

【输出样例】

ABDEC

解析：详见代码：

#include<bits/stdc++.h>
using namespace std;
int len;
string a, b;
void preorder(int left, int right) {
    int i, j;
    bool flag = false;
    //枚举层序遍历，最先在中序遍历中出现的节点为根
    for(i = 0; i < len; i++) {
        for(j = left; j <= right; j++) {
            if(b[i] == a[j]) {
                cout << a[j];
                flag = 1;
                break;
            }
        }
        if(flag)
            break;
    }
    if(left < j)//递归左子树
        preorder(left, j - 1);
    if(j < right)//递归右子树
        preorder(j + 1, right);
}
int main() {
    cin >> a >> b;
    len = a.length();
    preorder(0, len - 1);
    return 0;
}