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

灰太狼 2022-04-24 08:06 216阅读 0赞

## 构建二叉树 ##

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTAzMzE1_size_16_color_FFFFFF_t_70]

*  具体代码实现如下

//二叉树节点定义
    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**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTAzMzE1_size_16_color_FFFFFF_t_70]: /images/20220217/8bf6b8be6ba24d4797faea5c99ac6071.png