JakeLin

首先我们知道，前序第一个和后序最后一个就是树的根节点，拿到前序中的A，并在中序中找到它：
preorder：**A**BCDEFG
inorder：DCB**A**EFG
##### 此时中序被分割为【DCB】A【EFG】，我们即可知道：
- A的左子树元素有【DCB】，右子树元素有【EFG】，左子树3个元素，右子树也3个元素
- 对应到前序中，我们知道A后面三个元素即是左子树，剩下的即是右子树，即：A【BCD】【EFG】

------------

##### 通过这个原理，迭代可构建二叉树，看看代码：
```cpp
BiNode* build(int L1,int R1,int L2,int R2){ //返回树的根节点，L1-R1是先序遍历序列，L2-R2是后序遍历序列
	if(L1>R1) return NULL;
	BiNode* root = new BiNode();
	root->data = pre[L1];   //每次树的根节点都是先序遍历中的第一个元素
	int p=0;
	while(in[p]!=root->data) p++;  //找到根在中序中的位置
	int llen = p-L2;
	//pre:L1[L1+1,L1+llen][L1+llen+1,R1]   in:[L2,p-1]p[p+1,R2] 
	root->lchild = build(L1+1,L1+llen,L2,p-1);  //将其切割为左子树和右子树
	root->rchild = build(L1+llen+1,R1,p+1,R2);
	return root;
}
```

------------

#####  第二步：后序遍历二叉树
后序遍历的算法比较简单，按照**左->右->根**的顺序：
    
	void postOrder(BiNode* root){
    	if(root!=NULL){
    		postOrder(root->lchild);
    		postOrder(root->rchild);
    		cout<<root->data;
    	}
    }

------------

完整代码：
```cpp
#include<stdio.h>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
using namespace std;
const int maxn = 26 + 10;
char pre[maxn];
char in[maxn];
int len;
struct BiNode{
	char data;
	BiNode* lchild;
	BiNode* rchild;
}; 
BiNode* build(int L1,int R1,int L2,int R2){
	if(L1>R1) return NULL;
	BiNode* root = new BiNode();
	root->data = pre[L1]; 
	int p=0;
	while(in[p]!=root->data) p++;
	int llen = p-L2;
	root->lchild = build(L1+1,L1+llen,L2,p-1);
	root->rchild = build(L1+llen+1,R1,p+1,R2);
	return root;
}
void postOrder(BiNode* root){
	if(root!=NULL){
		postOrder(root->lchild);
		postOrder(root->rchild);
		cout<<root->data;
	}
} 
int main(){
	while(gets(pre)!=NULL){
		len=strlen(pre);
		gets(in);
		BiNode* root = build(0,len-1,0,len-1);
		postOrder(root);
		cout<<endl;
	}
    return 0;
}

```

0.0分

17 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

JakeLin

TA的其他文章

你可能喜欢

1010101001000：C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

C语言程序设计教程（第三版）课后习题10.4 （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

整除问题（C语言代码）

二叉树遍历-题解(C/C++) 详细解释，值得一看

评论区

精彩推荐

C二级辅导-温度转换（C语言代码）

C语言程序设计教程（第三版）课后习题10.1 （C语言代码）

C语言训练-求矩阵的两对角线上的元素之和（C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

字符串输入输出函数（C++代码）（都当成字符串吧hhhhhhhh）

C语言训练-求具有abcd=(ab+cd)2性质的四位数（C语言代码）

C语言训练-角谷猜想（C语言代码）

不会做的

程序员的表白（C语言代码）

蛇行矩阵（C语言代码）

JakeLin

TA的其他文章

你可能喜欢

1010101001000：C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

C语言程序设计教程（第三版）课后习题10.4 （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

整除问题 （C语言代码）

二叉树遍历-题解(C/C++) 详细解释，值得一看

评论区

精彩推荐

C二级辅导-温度转换 （C语言代码）

C语言程序设计教程（第三版）课后习题10.1 （C语言代码）

C语言训练-求矩阵的两对角线上的元素之和 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

字符串输入输出函数 （C++代码）（都当成字符串吧hhhhhhhh）

C语言训练-求具有abcd=(ab+cd)2性质的四位数 （C语言代码）

C语言训练-角谷猜想 （C语言代码）

不会做的

程序员的表白 （C语言代码）

蛇行矩阵 （C语言代码）

整除问题（C语言代码）

　　评论区

C二级辅导-温度转换（C语言代码）

C语言训练-求矩阵的两对角线上的元素之和（C语言代码）

字符串输入输出函数（C++代码）（都当成字符串吧hhhhhhhh）

C语言训练-求具有abcd=(ab+cd)2性质的四位数（C语言代码）

C语言训练-角谷猜想（C语言代码）

程序员的表白（C语言代码）

蛇行矩阵（C语言代码）