鏈接：登錄—專業(yè)IT筆試面試備考平臺_?？途W(wǎng)
來源：?？途W(wǎng) ?
題目描述
給出一棵二叉樹的中序與后序排列。求出它的先序排列。（約定樹結(jié)點用不同的大寫字母表示，長度 ≤ 8）。
輸入描述:
2行，均為大寫字母組成的字符串，表示一棵二叉樹的中序與后序排列。
輸出描述:
1行，表示一棵二叉樹的先序。
示例1
輸入
復(fù)制BADC BDCA
BADC BDCA
輸出
復(fù)制ABCD
ABCD
思路和題解
二叉樹的定義是遞歸定義，很多二叉樹題目的解決方法也可以是遞歸。二叉樹的中序遍歷是左->根->右，后序遍歷是左->右->根，先序遍歷是根->左->右。我們可以按照下面的步驟來解決問題。
1、如果一個樹是空樹，則退出。
2、輸出二叉樹的根，在中序排列中找到二叉樹根的位置pos，即后序排列的最后一個字符在中序排列里的位置。在中序排列中pos的左邊（假設(shè)字符個數(shù)為x）為左子樹的中序排列，pos右邊（假設(shè)字符個數(shù)為y）為右子樹的中序排列。在后續(xù)排列中前x個字符組成的子串為左子樹的后序排列，緊接著后面的y個字符組成的子串為右子樹的后序排列。
3、對左子樹的中序排列后續(xù)排列做步驟2文章來源：http://www.zghlxwxcb.cn/news/detail-743146.html
4、對右子樹的中序排列和后續(xù)排列做步驟2文章來源地址http://www.zghlxwxcb.cn/news/detail-743146.html
代碼：
#include<iostream>
#include<cstring>
using namespace std;
string zhong,hou;
void f(int l1,int r1,int l2,int r2)
{
int pos=-1;
if(l1>r1) return ;
//找根節(jié)點在中序序列中的位置
for(int i=l1;i<=r1;i++)
if(zhong[i]==hou[r2])
{pos=i;break;}
cout<<hou[r2];
f(l1,pos-1,l2,l2+(pos-1-l1));
f(pos+1,r1,l2+(pos-1-l1)+1,r2-1);
}
int main()
{
cin>>zhong>>hou;
int len=zhong.length();
f(0,len-1,0,len-1);
}到了這里，關(guān)于求先序排列的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
