根据前序遍历和中序遍历构建二叉树

根据前序遍历和中序遍历构建二叉树

通过前序遍历和中序遍历 可以确定二叉树 （中+后也可以 ，但前+后不行）从而构建二叉树

通过前序遍历和中序遍历确定二叉树

Tip：以1为结点的前序遍历是 1 2 4 5 3 6 7 8 中序：4 2 5 1 6 3 8 7 以2为结点的前序： 2 4 5 中序 ：4 2 5 以3为结点的前序： 3 6 7 8 中序： 6 3 8 7 以上图为例子： 由前序遍历可知：1为根结点 在中序遍历中找到1 说明 425 为左子树 6387为右子树 先来确定左子树 由前序可知 2为左子树的根节点 结合中序的4 2 5可知 4为2结点的左孩子 5为2 的右孩子 即可得到左子树如下图 再来看右子树： 3为右子树的根结点 6为3的左孩子 7 为3的右孩子8为7的左孩子

如何用代码来实现构建二叉树

函数传参内容包括：1.前序遍历结果 2.后序遍历结果 3.结点个数 实现步骤：1.建立根结点 2.建立左子树 3.建立右子树 终止条件：结点个数为0 如何找根结点？ 传入根结点的 前序遍历和中序遍历 前序遍历第一个结点为根节点

Node* BuildTree(int Preorder[], int Inorder[], int size)//根据前序遍历和中序遍历构建二叉树
{
          
   
	if (size == 0)
		return NULL;
	int rootvalue = Preorder[0];
	int r = -1;
	for (int i = 0; i < size; i++)
	{
          
   
		if (Inorder[i] = Preorder[0])
		{
          
   
			r = i;//找根结点在中序遍历中的位置
			break;
		}
	}
	assert(r != -1);
	Node*root = (Node*)malloc(sizeof(Node));
	root->value = rootvalue;
	root->left = BuildTree(Preorder + 1, Inorder, r);
	//上一步中 Preorder + 1表示左子树的前序遍历  Inorder表示右子树的中序遍历  r表示结点个数
	root->right = BuildTree(Preorder + 1 + r, Inorder + r + 1, size - 1 - r);
	//上一步中 Preorder + 1表示右子树的前序遍历  Inorder表示右子树的中序遍历  r表示结点个数
	return root;
}