还原二叉树

1. 二叉树的遍历方式
二叉树有三种遍历方式：先序遍历、中序遍历、后序遍历。
先序遍历： a、访问根节点；b、前序遍历左子树；c、前序遍历右子树。
中序遍历： a、中序遍历左子树；b、访问根节点；c、中序遍历右子树。
后序遍历：a、后序遍历左子树；b、后续遍历右子树；c、访问根节点。

2. 根据遍历结果还原二叉树
已知先序遍历和中序遍历，可以还原二叉树；
已知中序遍历和后序遍历，可以还原二叉树；
已知先序遍历和后序遍历，不可以还原二叉树。
2.1 已知先序遍历和中序遍历还原二叉树
思路：
1）、根据先序遍历结果确定根节点。
先序遍历的第一个节点为根节点。
2）、在中序遍历结果中找到根节点，根节点左侧的部分为左子树节点，根节点右侧的部分为右子树节点。
3）、将中序遍历的结果按根节点分为两部分，迭代的执行第一步和第二步，直到还原整个二叉树。

例如：已知先序遍历的结果为：ABDHIEJKCFLMGNO，中序遍历的结果为：HDIBJEKALFMCNGO。则二叉树为以下结构：

其后序遍历结果为：HIDJKEBLMFNOGCA
7-23 还原二叉树 (25 分)
给定一棵二叉树的先序遍历序列和中序遍历序列，要求计算该二叉树的高度。

输入格式:
输入首先给出正整数N（≤50），为树中结点总数。下面两行先后给出先序和中序遍历序列，均是长度为N的不包含重复英文字母（区别大小写）的字符串。

输出格式:
输出为一个整数，即该二叉树的高度。

输入样例:
9
ABDFGHIEC
FDHGIBEAC
输出样例:
5
1
2
3
4
5
6

#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std; 
int n;
char pre[60],in[60];
struct TNode{
	int Data;
	struct TNode* Left;
	struct TNode* Right;
};
typedef struct TNode* Tree;
//子问题，假如只有一个节点a的树，n1和n2都会等于0，他的左右子树经过递归都为空 ，最后返回T，也就是根节点。
//最小的子问题是空树，也就是递归出口 
Tree restoreTree(char pre[],char in[],int n){
	int i;
	char lpre[60],rpre[60];
	char lin[60],rin[60];
	int n1 = 0,n2 = 0;//n1记录中序左子树 n2记录中序右子树
	int m1 = 0,m2 = 0;//m1记录前序左子树 m2记录前序右子树
	if(n==0){
		return NULL;
	}
	Tree T = (Tree)malloc(sizeof(struct TNode));
	if(T==NULL){
		return NULL;//若内存满了（T无法再被分配节点），返回NULL； 
	}
	T->Data = pre[0];//根节点 
	//依次确定根节点，递归实现
	//分中序遍历序列 
	for(i = 0; i < n; i++){
		if(i<=n1&&in[i]!=pre[0]){//中序遍历被根节点分开的左子树的点 
			lin[n1] = in[i];
			n1++;
		}
		else if(in[i]!=pre[0]){//跳过了根节点，把中序遍历的节点依次放入rin中 
			rin[n2] = in[i];
			n2++;
		}
	}
	//分前序遍历序列,注意这里从1开始循环，因为0号元素作为根 
	for(i = 1; i < n; i++){
		if(i<(n1+1)){
			lpre[m1] = pre[i];
			m1++;
		}
		else{
			rpre[m2] = pre[i];
			m2++;
		}
	}
	T->Left = restoreTree(lpre,lin,n1);//又是一颗新的数 
	T->Right = restoreTree(rpre,rin,n2);//又是一颗新的数 
	return T;//最后一定要return这颗树，才能计算高度 
}
int getHight(Tree BST){//树高为max（左树高，右树高）+1； 
	int lh,rh;
	if(BST==NULL){
		return 0;
	}
	else {
		lh = getHight(BST->Left);
		rh = getHight(BST->Right);
	    return (lh>rh?lh:rh)+1;
	} 
	
}
int main(){
	scanf("%d",&n);
	scanf("%s",pre);
	scanf("%s",in);
	Tree BST = NULL;
	BST = restoreTree(pre,in,n);
	int hight;
	hight = getHight(BST);
	printf("%d\n",hight);
	return 0;
}
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

2.2 已知后序遍历和中序遍历还原二叉树
思路：
1）、根据后序遍历结果确定根节点。
后序遍历的最后一个节点为根节点。
2）、在中序遍历结果中找到根节点，根节点左侧的部分为左子树节点，根节点右侧的部分为右子树节点。
3）、将中序遍历的结果按根节点分为两部分，迭代的执行第一步和第二步，直到还原整个二叉树。
例如：已知后序遍历的结果为：HIDJKEBLMFNOGCA，中序遍历的结果为：HDIBJEKALFMCNGO。则二叉树为以下结构：

其先序遍历结果为：ABDHIEJKCFLMGNO

已知前序和中序，后序和中序遍历序列之后，可以唯一确定一棵二叉树。但是，只知道前序和后序遍历序列，是无法知道哪个结点是左子树还算右子树。

如还是上面题目：如：已知一棵二叉树的后序遍历序列和中序遍历序列分别是gdbehfca、dgbaechf，求二叉树

后序：gdbehfca—->gdb ehfc a

中序：dgbaechf—–>dgb a echf
得出结论：a是树根，a有左子树和右子树，左子树有bdg结点，右子树有cefh结点。
后序：gdb—->gd b

中序：dgb—–>dg b

得出结论：b是a左子树的根节点，无右子树，有左子树dg。

后序：gd—->g d

中序：dg—–>d g

得出结论：d是b的左子树根节点，g是d的右子树。

然后对于a 的右子树类似可以推出。然后还原。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

以下代码未测试

#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std; 
int n;
char post[60],in[60];
struct TNode{
	int Data;
	struct TNode* Left;
	struct TNode* Right;
};
typedef struct TNode* Tree;
Tree restoreTree(char post[],char in[],int n){
	int i;
	char lpost[60],rpost[60];
	char lin[60],rin[60];
	int n1 = 0,n2 = 0;
	int m1 = 0,m2 = 0;
	if(n==0){
		return NULL;
	}
	Tree T = (Tree)malloc(sizeof(struct TNode));
	if(T==NULL){
		return NULL;
	}
	T->Data =post[n-1];
	for(i = 0; i < n; i++){
		if(i<=n1&&in[i]!=post[n-1]){
			lin[n1] = in[i];
			n1++;
		}
		else if(in[i]!=post[n-1]){
			rin[n2] = in[i];
			n2++;
		}
	}
	for(i = 0; i < n-1; i++){
		if(i<(n1+1)){
			lpost[m1] = post[i];
			m1++;
		}
		else{
			rpost[m2] = post[i];
			m2++;
		}
	}
	T->Left = restoreTree(lpost,lin,n1);
	T->Right = restoreTree(rpost,rin,n2);
	return T;
}
int getHight(Tree BST){
	int lh,rh;
	if(BST==NULL){
		return 0;
	}
	else {
		lh = getHight(BST->Left);
		rh = getHight(BST->Right);
	    return (lh>rh?lh:rh)+1;
	} 
	
}
int main(){
	scanf("%d",&n);
	scanf("%s",post);
	scanf("%s",in);
	Tree BST = NULL;
	BST = restoreTree(post,in,n);
	int hight;
	hight = getHight(BST);
	printf("%d\n",hight);
	return 0;
}
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73