Thinking in Data Structure -- Binary Tree

二叉树是树结构中比较容易实现的一种，有关它的操作也有很多，在接下来的几天，我将陆续更新，先写个目录吧：

1. 已知二叉树的前序和中序，要求重新构造出该二叉树

我们知道，前序遍历是所谓的 “根左右”，中序遍历是所谓的 “左根右”。注意，重点来了，中序遍历的根节点将整棵二叉树分成了左子树和右子树，而前序遍历因为总是先访问根节点，所以可以在前序遍历的第一个节点肯定是根节点，然后在根据这个根节点找到中序遍历的两棵子树，然后以此类推。即可以使用递归。

说到递归，确实是一个神奇的东西，它极大地降低了编码的难度，同时也增大了阅读的难度。不过要写出一个好的递归算法还是需要一定的技巧的，一般我是这么考虑递归的：

1. 考虑递归是否需要返回值
2. 考虑递归结束的条件，这一个非常的重要
3. 考虑子问题，这里要注意的是如果是有返回值的递归要对每一种情况都进行返回的

这样说比较虚，我们具体来看这道题：

既然是要重新构造二叉树，说明是从无到有的，所以要么在递归函数的参数中加入一个节点参数，要么选择有返回值的递归函数，我倾向于第二种，因为如果是引入节点参数的话，必须使用二级指针，（关于二级指针的内容我接下来将会写一篇使用底层汇编来解释二级指针的文章，尽请期待），比较麻烦，而且多加一个参数的话如果递归深度过高将会大大增加暴栈的可能性。

递归结束条件，很明显，如果根节点没有左子树和右子树，那么就可以将该节点直接返回。

子问题，我们可以将树的左子树和右子树看成一棵新的树，然后新的树也将有根节点，左子树和右子树，于是树的长度变小，直至为 1

好了，其实这个问题真的不难，说了这么多只是想把自己的思考过程写出来而已，下面看代码，自己感觉写的还是挺优美的～

#include "binary_tree.h"
#include <stdlib.h>
#include <string.h>
#define N 100

b_tree recover(char *preorder, char *inorder, int len)
{
	b_tree node = (b_tree)malloc(sizeof(bin_tree));
	int i;
	int root_pos;

	node->data = preorder[0];
	node->lchild = node->rchild = NULL;

	if (len == 1) {
		return node;
	}

	for (i = 0; i < len; i++) {
		if (inorder[i] == preorder[0]) {
			root_pos = i;
			break;
		}
	}

	if (root_pos == 0) {
		node->rchild = recover(preorder+1, inorder+1, len-1);
	} else if (root_pos == len-1) {
		node->lchild = recover(preorder+1, inorder, len-1);
	} else {
		node->lchild = recover(preorder+1, inorder, root_pos);
		node->rchild = recover(preorder+root_pos+1, inorder+root_pos+1, len-root_pos-1);
	}

	return node;
}

int main(void)
{
	b_tree root;
	char preorder[N] = {0};
	char inorder[N] = {0};
	int len;
	
	printf("Please enter the preorder: ");
	scanf("%s", preorder);
	printf("Please enter the inorder: ");
	scanf("%s", inorder);
	
	len = strlen(preorder);
	root = recover(preorder, inorder, len);

	preorder_recur(root);
	putchar(10);
	inorder_recur(root);
	putchar(10);

	return 0;
}