给定先序和中序序列,求后序序列

发表于 | 分类于
字数统计: 512 word | 阅读时长 ≈ 2 min
要求：

输入二叉树的先序遍历序列和中序遍历序列，输出该二叉树的后序遍历序列。

代码：
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
 #include<iostream>
 #include<string>
using namespace std;
int i;
char s1[100],s2[100];
typedef struct Node{
	char value;
	Node *lchild;
	Node *rchild;
}*Tree;
//由先序序列s1[0···n-1]和中序序列s2[0···n-1]建立二叉链存储结构的二叉树
//s1:先序遍历字符串  s2:中序遍历字符串   n:结点个数
Tree creattree(char s1[],char s2[],int n){
	int k;
	if (n <= 0){
		return NULL;
	}
	char root = s1[0];       //根节点的值
	Tree bt = (Tree)malloc(sizeof(Node));
	bt->value = root;
	for (k = 0; k < n; k++){  
		if (s2[k] == root){    //在s2中查找 根节点
			break;
		}
	}
	bt->lchild = creattree(s1 + 1, s2, k);		//递归创建左子树
	bt->rchild = creattree(s1 + k + 1, s2 + k + 1, n - k - 1); //递归创建右子树
	return bt;
}
//后序遍历
void traveltree2(Tree t){
	if (t != NULL){
		traveltree2(t->lchild);
		traveltree2(t->rchild);
		cout << t->value;
	}	
}
int main(){
	Tree t = NULL;
	cin >> s1>>s2;
	string s = s1;
	t = creattree(s1, s2, s.size());
	traveltree2(t);
	return 0;
}

输入：
ABDCEF

BDAECF

输出：

DBEFCA
附：已知中序后序求先序
代码：
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
 #include<iostream>
 #include<string>
using namespace std;
int i;
char s1[100],s2[100];
typedef struct Node{
	char value;
	Node *lchild;
	Node *rchild;
}*Tree;
Tree creattree(char s1[],char s2[],int n){
	int k;
	if (n <= 0){
		return NULL;
	}
	char root = s2[n-1];       //这里和上面的不一样 后序遍历的最后一个元素才是 根节点
	Tree bt = (Tree)malloc(sizeof(Node));
	bt->value = root;
	for (k = 0; k < n; k++){  
		if (s1[k] == root){		//在中序序列中查找根节点
			break;
		}
	}
	bt->lchild = creattree(s1, s2, k);		
	bt->rchild = creattree(s1 + k + 1, s2 + k, n - k - 1);  //注意这里的范围 s2+k  画一画就明白了
	return bt;
}
//先序遍历
void traveltree2(Tree t){
	if (t != NULL){
		cout << t->value;
		traveltree2(t->lchild);
		traveltree2(t->rchild);		
	}	
}
int main(){
	Tree t = NULL;
	cin >> s1>>s2;
	string s = s1;
	t = creattree(s1, s2, s.size());
	traveltree2(t);
	return 0;
}

输入：

dbgeafc

dgebfca

输出：

abdegcf
0%