ACM 重构二叉树 C++实现

朱雀 2022-05-15 13:15 133阅读 0赞

重构二叉树

Description  
根据输入的二叉树前序和中序遍历序列重构二叉树，输出对应节点的左右子节点。

输入：  
第一行是一个整数N（1<=N<=20），表示有多少个测试例子。以下每个测试例子的第一行是本测试例子的二叉树的前序遍历，第二行是中序遍历，第三行首先是一个整数M，表示要求输出结果的数目，以后有M个节点，每个中间由一个空格隔开。  
  
输出：  
每行输出一个例子的所有结果，如果其子节点为空则输出字符\#，同一例子的不同节点的输出结果之间用一个空格隔开  
  
Sample Input  
1  
ABCDEF  
CBEDFA  
3 A B C  
  
Sample Output  
B\# CD \#\#

//C++实现

\#include<iostream>  
using namespace std;

char str1\[100\],str2\[100\],s\[100\];  
int c\[100\],d\[100\];

typedef struct trees  
\{  
int value;  
int k;  
\};  
trees tree\[100\];

void insert(int cc,int i)  
\{  
if(c\[cc\]<tree\[i\].k)  
\{  
if(tree\[2\*i\].value=='\#')  
\{  
tree\[2\*i\].value=cc;  
tree\[2\*i\].k=c\[cc\];  
d\[cc\]=2\*i;  
\}  
else insert(cc,2\*i);  
\}  
else  
\{  
if(tree\[2\*i+1\].value=='\#')  
\{  
tree\[2\*i+1\].value=cc;  
tree\[2\*i+1\].k=c\[cc\];  
d\[cc\]=2\*i+1;  
\}  
else insert(cc,2\*i+1);  
\}  
\}

int main()  
\{  
int cases;  
cin>>cases;  
  
int lena,lenb;  
while(cases--)  
\{  
int n;  
scanf("%s %s",str1,str2);  
scanf("%d",&n);  
lena=strlen(str1);  
lenb=strlen(str2);  
int i;  
for(i=0;i<100;i++)  
tree\[i\].value='\#';  
for(i=0;i<n;i++)  
\{  
scanf(" %c",&s\[i\]);  
\}  
for(i=0;i<lenb;i++)  
\{  
c\[str2\[i\]\]=i+1;  
\}  
tree\[1\].value=str1\[0\];  
tree\[1\].k=c\[str1\[0\]\]; //用来比较的,str2中的位置  
d\[str1\[0\]\]=1; //每个字符的存储位置  
for(i=1;i<lena;i++)  
insert(str1\[i\],1);  
int k;  
for(i=0;i<n;i++)  
\{  
k=d\[s\[i\]\];  
printf("%c%c ",tree\[2\*k\].value,tree\[2\*k+1\].value);  
\}  
cout<<endl;  
\}  
return 0;  
\}