C语言——二叉树的生成与遍历

  输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果都不含重复数字。例如，输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建如图2.6所示的二叉树并输出它的头结点。二叉树节点的定义如下：

typedef struct
{
	int m_value;
	struct BinaryTreeNode* m_pLeft;
	struct BinaryTreeNode* m_pRight;
}BinaryTreeNode;

  前序遍历、中序遍历、后序遍历中的“前中后”分别指根节点的位置，因此我们现在来根据题目所给的例子，来分析如何重建该二叉树。
1.从前序遍历中找到第一个值1，由前序遍历概念可以知道，他是作为二叉树的根节点
2.接着从中序遍历中找到这个根节点的值，由中序遍历这个值的左边的数{4,7,2}为左子树节点，右边的{5,3,8,6}为右子树节点
3.重新开始，前序遍历的第一个值为2，由以上分析可以知道，这个值是左子树的根节点
4.目光转移到中序遍历，刚刚得出中序遍历的左子树节点为{4,7,2},找到左子树的根节点2，进一步得出{4,7}为该子树的左子树，且该子树没有右子树
5.依次重复，直到遍历的数组结束。

BinaryTreeNode* Construct(int* preorder, int* inorder, int length)
{
	if (preorder == NULL || inorder == NULL || length < 0)
		return NULL;

	return ConstructCore(preorder, preorder + length - 1, inorder, inorder + length - 1);
}

BinaryTreeNode* ConstructCore(int* startPreorder, int* endPreorder, int* startInorder, int* endInorder)
{
	int rootVaule = startPreorder[0];	//获取根节点的值
	BinaryTreeNode* root = (BinaryTreeNode*)malloc(sizeof(BinaryTreeNode));
	root->m_value = rootVaule;
	root->m_pRight = root->m_pLeft = NULL;

	if (startPreorder == endPreorder)  //传递进来的两个数组只有一个元素的情况
	{
		if (endInorder == startInorder && *startInorder == *startPreorder)
			return root;
		else
			printf("输入错误n");
	}
	//在中序遍历中找到根节点的值:
	int* rootInorder = startInorder;
	while (rootInorder <= endInorder && *rootInorder != rootVaule)
	{
		rootInorder++;
		if (rootInorder == endInorder && *rootInorder != rootVaule)
			printf("输入错误n");		
	}

	int leftLength = rootInorder - startInorder;
	int* leftPreorderEnd = startPreorder + leftLength;
	if (leftLength > 0)
	{
		root->m_pLeft = ConstructCore(startPreorder + 1, leftPreorderEnd, startInorder, rootInorder - 1);
	}
	if (endPreorder - startPreorder - leftLength > 0)
	{
		root->m_pRight = ConstructCore(leftPreorderEnd + 1, endPreorder, rootInorder + 1, endInorder);
	}
	return root;
}

分析：与以往判断数组是否结束使用的下标+长度方法不同，这次使用的地址来判断数组是否结束。

void PreOrder(BinaryTreeNode* node)
{
	if (node == NULL)
	{
		printf("节点错误");
	}
	printf("%d ", node->m_value);
	if (node->m_pLeft != NULL)
	{
		PreOrder(node->m_pLeft);
	}
	if (node->m_pRight != NULL)
	{
		PreOrder(node->m_pRight);
	}
	return;
}

void InOrder(BinaryTreeNode* node)
{
	if (node == NULL)
	{
		printf("节点错误");
	}
	
	if (node->m_pLeft != NULL)
	{
		InOrder(node->m_pLeft);
	}
	printf("%d ", node->m_value);
	if (node->m_pRight != NULL)
	{
		InOrder(node->m_pRight);
	}
	return;
}

void PostOrder(BinaryTreeNode* node)
{
	if (node == NULL)
	{
		printf("节点错误");
	}

	if (node->m_pLeft != NULL)
	{
		PostOrder(node->m_pLeft);
	}
	if (node->m_pRight != NULL)
	{
		PostOrder(node->m_pRight);
	}
	printf("%d ", node->m_value);
	return;
}

注意：前序遍历、中序遍历、后序遍历的代码实现差别只在什么时候输入根节点的值。前序在开始，中序在中间，后序在最后。

int main()
{
	int preorder[8] = {1,2,4,7,3,5,6,8};
	int inorder[8] = {4,7,2,1,5,3,8,6};
	int length = 8;
	BinaryTreeNode* root = NULL;
	root = Construct(preorder, inorder, length);
	printf("前序遍历:");
	PreOrder(root);
	printf("n中序遍历:");
	InOrder(root);
	printf("n后序遍历:");
	PostOrder(root);
	return 0;
}