二叉树遍历之已知中序和按层遍历求先序遍历(flist)

2021年6月19日 1点热度 0条评论 来源: 寒冰雪松

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

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

【输入】
两行,每行是由字母组成的字符串(一行的每个字符都是唯一的),分别表示二叉树的中序遍历和按层遍历的序列。

【输出】
一行,表示二叉树的先序序列。

【输入样例】
DBEAC
ABCDE
【输出样例】
ABDEC
【算法分析】:树本身可以看做是递归定义的,求先序遍历只要找出树的根,递归找到左子树的根,右子树的根,输出根即可。本题中各结点都不相同,而同一层中左子树的树根一定先于右子树遍历到,

因此,可以据分层遍历找到根结点,由根结点和中序遍历把原树分成左右子树,设置左右子树范围,再用分层遍历结果找子树的根。特点说明,由于树各结点都不同,所以分层遍历的结果可以不用修改

直接与子树对比查找子树的根。

代码:

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
using namespace std;
string s1,s2;
void houx(int,int,int,int); 
int main()
{
	cin>>s1>>s2;
	houx(0,s1.length()-1,0,s2.length()-1);
	cout<<endl;
	return 0;
}
void houx(int l1,int r1,int l2,int r2)//子树中序开始位置l1结果位置r1;分层遍历开始l2,结果r2 
{
	int i,j,b;
	for(i=l2;i<=r2;i++)//分层遍历边界不用修改,直接使用,因为与子树中序遍历结果对比找根时,
                        //已经输出的树是绝对找不到的。 
	{					//而且每个子树的根用分层遍历时是最选找到的结点。 
		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)houx(l1,j-1,l2,r2);//调整子树中序边界,递归,左子树 
	if(j<r1)houx(j+1,r1,l2,r2);	//调整子树中序边界,递归,右子树 
}

 

    原文作者:寒冰雪松
    原文地址: https://blog.csdn.net/HanJsong2018/article/details/116163188
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。