二叉树遍历（已知中序和按层遍历求先序递归）

爱被打了一巴掌 2022-06-09 10:38 68阅读 0赞

### 二叉树遍历(flist) ###

时间限制: 1000 ms 内存限制: 65536 KB  
提交数: 8 通过数: 6

### 【题目描述】 ###

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

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

### 【输入】 ###

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

### 【输出】 ###

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

### 【输入样例】 ###

DBEAC
    ABCDE

### 【输出样例】 ###

ABDEC

### 【来源】 ###

[No][]

[提交 ][Link 1][统计信息][Link 2]

#include<iostream>
    #include<cstring>
    using namespace std;
    string s1,s2;
    void calc(int l1,int r1,int l2,int r2)
    {
    	int i,j;
    	for(i=l2;i<=r2;i++)//找层次遍历中优先输出根节点的位置 
    	{
    		int b=0;
    		for(j=l1;j<=r1;j++)
    		{
    			if(s2[i]==s1[j]) 
    			{
    				cout<<s1[j];//输出根节点 
    				b=1;
    				break;
    			}
    		}
    		if(b) break;
    	}
    	if(j>l1) calc(l1,j-1,0,r2);//遍历左子树 
    	if(j<r1) calc(j+1,r1,0,r2);//遍历右子树 
    }
    int main()
    {
    	cin>>s1>>s2;
    	calc(0,s1.length()-1,0,s2.length()-1);
    	cout<<endl;
    	return 0;
    }

这种题一般都要先确定好根节点的位置。然后才根据先序、中序、后序的规则进行递归。

[No]: http://ybt.ssoier.cn:8088/problem_search.php?searchsource=No
[Link 1]: http://ybt.ssoier.cn:8088/submit.php?pid=1364
[Link 2]: http://ybt.ssoier.cn:8088/problem_stat.php?pid=1364