【摘要】二叉树，根据先序、中序序列，求后续遍历结果
输入：
第一行为二叉树先序遍历结果。
第二行为二叉树中序遍历结果。
12
输出：
二叉树后续遍历结果
1
样例输入：
426315
623415
12
样例输出：
632514
1
完整代码：
#include<bits/stdc++.h>
using namespace std;

char pre[10…

二叉树，根据先序、中序序列，求后续遍历结果

输入：

第一行为二叉树先序遍历结果。
第二行为二叉树中序遍历结果。

  
 
  1
  2

输出：

二叉树后续遍历结果

  
 
  1

样例输入：

样例输出：

完整代码：

#include<bits/stdc++.h>
using namespace std;

char pre[100];
char hou[100];
//定义结构体
typedef struct node{
	char data;
	struct node *lc,*rc;
} *BTree; 
//根据先序、中序建树
BTree build(int l1, int r1, int l2, int r2){
	BTree T = new node;
	T->data = pre[l1];
	T->lc=NULL;
	T->rc=NULL;
	int pos = l2;
	while(hou[pos]!=pre[l1]){
		pos++;
	}
	int cnum = pos-l2;
	if(pos>l2){
		T->lc = build(l1+1, l1+cnum, l2, pos-1);
	}
	if(pos<r2){
		T->rc = build(l1+cnum+1, r1, pos+1, r2);
	}
	return T;
}
//后续输出遍历结果
void Hou(BTree T){
	if(T!=NULL){
		Hou(T->lc);
		Hou(T->rc);
		cout<<T->data;
	} 
}
//主函数
int main(){
	cin>>pre;
	cin>>hou;
	BTree T = build(0, strlen(pre)-1, 0, strlen(hou)-1);
	Hou(T);
} 

  
 
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36
  37
  38
  39
  40
  41
  42
  43
  44