根据二叉树的前序中序构建二叉树

构建二叉树

  • 构建二叉树,这是个比较繁琐的问题,假如我们知道二叉树的先序及中序遍历我们能不能构建二叉树呢?答案肯定是能得,这不废话么,不能得话我就得换我的标题了。
  • 为什么能根据先序以及中序构建一棵二叉树呢?
    答案显而易见,开始我也不知道,哈哈,但是我根据先序以及中序遍历将二叉树画出来了,那就说明当然可以,后来我又仔细观察了二叉树的先序以及中序序列,我们会发现先序序列中根很容易找到,因为第一个元素就是根节点,我们从先序序列中找到根节点之后,然后在中序序列中就很容易找到根节点,那么在根节点左边的就是左子树,右边的就是右子树了。按照这种思路,很容易我们就还原了二叉树。。同理,根据后序以及中序序列我们也能轻松还原二叉树,但是根据先序以及后序我们无法还原二叉树,因为在先序以及后序序列中,我们只能找到根节点,却无法根据根节点区分左右子树

《根据二叉树的前序中序构建二叉树》

  • 具体代码实现如下
//二叉树节点定义
typedef struct Node {
	struct Node *left;
	struct Node *right;
	char value;
}	Node;

//查找
int find(char array[], int size, char v) {
	for (int i = 0; i < size; i++) {
		if (array[i] == v) {
			return i;
		}
	}

	return -1;
}

// size 树的结点个数
Node * buildTree(char preorder[], char inorder[], int size) {
	if (size == 0) {
		return NULL;
	}

	char rootValue = preorder[0];
	//计算左子树的节点个数
	int leftSize = find(inorder, size, rootValue);

	// 根
	Node *root = (Node *)malloc(sizeof(Node));
	root->value = rootValue;
	// 左子树
	root->left = buildTree(
		preorder + 1,// 左子树前序
		inorder,// 左子树中序
		leftSize// 左子树结点个数
		);
	// 右子树
	root->right = buildTree(
		preorder + 1 + leftSize,// 右子树前序
		inorder + leftSize + 1,// 右子树中序
		size - 1 - leftSize// 右子树结点个数
		);

	return root;
}

这就是我们利用二叉树的先序以及中序序列构建二叉树的方法,主要还是我强调的那个思路,采用子问题的方法解决问题,即先处理根,再处理左子树,再处理右子树。 在代码中我就是采用了这种方法,即先构建根节点,再构建左子树,再构建右子树的方式构建二叉树。
想法往往比实现过程重要很多。。。。。。。。。。。。。。。。。

ALL OVER

    原文作者:blog_zhangxu
    原文地址: https://blog.csdn.net/qq_43503315/article/details/89418810
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞