欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

由中序与后序遍历得到二叉树

程序员文章站 2022-05-20 13:51:44
...
例子
3 2 1 4 5 7 6 (中序遍历) 
3 1 2 5 6 7 4 (后序遍历)
思路
整体来说就是一个递归分治的思想
重点在后序遍历上,由后序遍历的定义知,后序遍历的最后一项肯定为根结点,然后在中序遍历中找到这一项(假设无重复项)
如:由 3 1 2 5 6 7 4 (后序遍历)知该二叉树的根结点为4,因此将3 2 1 4 5 7 6 (中序遍历) 分割为3 2 1||4||5 7 6,
又由中序遍历的定义知,4左边的为左子树,右边的为右子树。在将每颗子树看为一颗树
------左:3 2 1(中序遍历) 3 1 2(后序遍历)--------右:5 7 6 (中序遍历)  5 6 7(后序遍历)-------

以此类推。。。。直到不可分割出现递归出口。


vector<int>inorder;
vector<int>postorder;
struct my_Node
{
	int data;
	struct my_Node *left_p;
	struct my_Node *right_p;
};

struct my_Node* create_tree(int start_inorder, int end_inorder, int start_postorder, int end_postorder)
//传入的四个参数为,中序遍历的开始与结束位,后序遍历的开始与结束位
{
	my_Node* root = (my_Node*)malloc(sizeof(my_Node));
	root->data = postorder[end_postorder];
	if (end_inorder - start_inorder < 2)//递归出口,子树为空
	{
		root->left_p = NULL;
		root->right_p = NULL;
		return root;
	}

	//找出中序遍历中的根结点
	int p_temp = start_inorder;
	while ((p_temp<=end_inorder)&&(inorder[p_temp]!=postorder[end_postorder]))
	{
		p_temp++;
	}

	//左子树
	int num_left_tree = p_temp - start_inorder;//左子树大小
	if (num_left_tree!=0)
	{
		root->left_p = create_tree(start_inorder, p_temp-1, start_postorder, start_postorder + (num_left_tree)-1);
	}
	else
	{
		root->left_p = NULL;
	}
	//右子树
	int num_right_tree = end_inorder - p_temp;
	if (num_right_tree!=0)
	{
		root->right_p = create_tree(p_temp + 1, end_inorder, end_postorder - num_right_tree, end_postorder - 1);
	}
	else
	{
		root->right_p = NULL;
	}
	return root;
}