由后序遍历序列和中序遍历序列，构建二叉树【C++版】_中序后序确定二叉树c++

1.需求

根据后序遍历序列和中序遍历序列，构建二叉树。本代码使用C++实现。

2.分析

我们知道，可以用后序遍历序列和中序遍历序列，或者先序序列和中学序列完全确定一棵二叉树。但是理论上的都好理解，但是如何用代码实现了。记住一句话：抽象！
我们需要把理论的部分完全抽象出来，然后用代码实现即可。主要步骤如下：

• step 1：后序遍历中，根节点在最后输出，所以对于一个后序遍历序列post[]，其最后一个值必是该树的根节点，我们记该值为root。
• step 2： 在中序遍历序列in[]中找到一个节点的值与root相同，记其下标为i，这样就可以将该树分成左右两部分了，在i左侧的都是root的左子树，在i右侧的都是右子树。
• step 3:我们用一个变量 numLeft标记左子树的个数，很显然，左子树中节点的个数是i-inL
• step 4：在对当前的节点建树完成之后，就要开始建左子树和右子树了。这里采用递归的方式，只不过是传递的参数不同罢了；对于左子树，传递的参数则是：(postL,postL+numLeft-1,inL,k-1)，而对于右子树传递的参数则是：(postL+numLeft,postR-1,k+1,inR)。
  可以看到上面这个区间实际上是连续的，postL -> postL+numLeft-1 ->postL+numLeft -> PostR -1。intL ->k-1 -> k+1 -> inR。这里的postR-1，而不是postR，是因为最后一个节点是根节点，我们已经创建过了（后序遍历序列）；同理，下标为k的那个节点也是根节点（中序遍历序列）。

3.代码

针对以上的分析，得到如下的代码：

#include<cstdio>
#include<iostream>
#define maxn 100
using namespace std;
struct node{
	int data;//值 
	int height;//高度 
	node* left;//左子树 
	node* right; //右子树 
}; 

int in[maxn];
int post[maxn];
int N;

node* create(int postL,int postR,int inL,int inR){
	if(postL > postR){//说明到头了 
		return NULL; 
	}
	//下面这个就是建树的步骤 
	node* root = new node;
	root->data = post[postR];//新节点的数据域为根节点的值 
	int i;
	for(i = inL; i <= inR;i++ ){
		if(in[i] == post[postR]){//说明找到了相同值 
			break;
		}
	}
	int numLeft ;//表示的是这个根节点左侧的节点数
	numLeft = i - inL;
	root->left = create(postL,postL+numLeft-1,inL,i-1); //建左子树 
	root->right = create(postL+numLeft,postR-1,i+1,inR);//建右子树 
	return root; 
} 

//输出先序遍历 
void preOrder(node* root){
	cout << root->data <<" ";
	if(root->left!=NULL) preOrder(root->left);//输出左子树 
	if(root->right!=NULL) preOrder(root->right);//输出右子树 
}


int main(){
	cin >> N;
	int i;
	for(i = 0;i< N;i++){
		cin >> in[i];
	}
	for(i = 0;i< N;i++){
		cin >> post[i];
	}
	node* root = create(0,N-1,0,N-1);
	preOrder(root); 
}
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
45
46
47
48
49
50
51
52
53
54
55

4.测试用例

8
12 11 20 17 1 15 8 5
12 20 17 11 15 8 5 1

4
1 15 8 5
15 8 5 1
1
2
3
4
5
6
7