已知树的两种遍历求第三种一、已知先序遍历和中序遍历，求后序遍历二、已知中序遍历和后序遍历，求先序遍历三、已知先序遍历和后序遍历，求中序遍历

110 阅读 0 评论 73 点赞

我是靠谱客的博主笑点低枕头，这篇文章主要介绍已知树的两种遍历求第三种一、已知先序遍历和中序遍历，求后序遍历二、已知中序遍历和后序遍历，求先序遍历三、已知先序遍历和后序遍历，求中序遍历，现在分享给大家，希望可以做个参考。

一、已知先序遍历和中序遍历，求后序遍历

复制代码

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
#include<bits/stdc++.h>

using namespace std;

typedef struct TreeNode{
	struct TreeNode* left;
	struct TreeNode* right;
	char elem;
}TreeNode;

TreeNode* BinaryTreeFromOrderings(char* preorder, char* inorder, int length)
{
	TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
	node->elem = *preorder;
	
	if(length == 0) return NULL;
	
	int rootIndex = 0;
	for(; rootIndex < length; rootIndex++)
	{
		if(inorder[rootIndex] == *preorder)
			break;
	}
	node->left = BinaryTreeFromOrderings(preorder + 1, inorder, rootIndex);
	node->right = BinaryTreeFromOrderings(preorder+rootIndex+1, inorder+rootIndex+1, length-rootIndex-1); 
	cout << node->elem <<' '; //注意位置 
}

int main()
{
	char* pre = "GDAFEMHZ";
	char* in = "ADEFGHMZ";
	BinaryTreeFromOrderings(pre, in, 8);
	return 0;
}

//out:A E F D H Z M G

二、已知中序遍历和后序遍历，求先序遍历

复制代码

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
#include<bits/stdc++.h>

using namespace std;

typedef struct TreeNode{
	struct TreeNode* left;
	struct TreeNode* right;
	char elem;
}TreeNode;

TreeNode* BinaryTreeFromOrderings(char* postorder, char* inorder, int length)
{
	TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
	node->elem = *(postorder+length-1);
	
	if(length == 0) return NULL;
	
	int rootIndex = 0;
	for(; rootIndex < length; rootIndex++)
	{
		if(inorder[rootIndex] == *(postorder+length-1))
			break;
	}
	cout << node->elem <<' '; //注意位置 
	node->left = BinaryTreeFromOrderings(postorder, inorder, rootIndex);
	node->right = BinaryTreeFromOrderings(postorder+rootIndex, inorder+rootIndex+1, length-rootIndex-1); 
}

int main()
{
	char* post = "AEFDHZMG";
	char* in = "ADEFGHMZ";
	BinaryTreeFromOrderings(post, in, 8);
	return 0;
}