最近学到二叉树，在递归创建二叉树时遇到了点问题，记录一下

二叉树的存储结构：

/****** 二叉树 ********/
typedef struct BiTree{
    char data;       //数据段
    struct BiTree * lchild;	
    struct BiTree * rchild;
}BiTree;

书上面是每次递归调用的时候读取一个字符作为输入，我改了一下，通过一个字符串去创建。

第一个版本：

void ProOrderInputTree(char * input, BiTree * T)
{
    if(*input == 0)
        return;
    if(*input == '#')
    {
        T = NULL;//扩展标志
    }
    else
    {
        T = (BiTree*)malloc(sizeof(BiTree));
        T->data = *input;
        ProOrderInputTree(input + 1, T->lchild);  
        ProOrderInputTree(input + 2, T->rchild);   
    }
}

思路很简单，把字符串第一个字符作为根的数据，第二个作为左孩子的数据，第三个作为右孩子的数据。
但想一想之后发现不行，创建左子树返回后，input是从栈拿出来的，指向的位置不会变。而左子树的子孙个数是不一定的。

于是我想到设置一个全局变量，指向当前结点的数据，它不是函数内的局部变量，不会进栈：

char* c;
void ProOrderInputTree(char * input, BiTree * T)
{
	c = input;
    if(*c== 0)
        return;
    if(*c== '#')
    {
    	c++;
        T = NULL;
    }
    else
    {
        T = (BiTree*)malloc(sizeof(BiTree));
        T->data = *c;
        c++;
        ProOrderInputTree(c, T->lchild);  
        ProOrderInputTree(c, T->rchild);   
    }
}

修改后发现还是不行，调试的时候发现，每次递归完后，T的左右孩子指向了无法访问的内存，这就很疑惑，每次传入的都是指针，为什么还是无法改变呢？

在网上找了一圈，终于理解了，简单来说，当使用malloc创建内存时，函数参数T的值改变了，导致它的双亲无法找到它了。（经典的值传递无法改变变量的问题，只不过这次的‘值’是地址而已）

知道原因就简单了，通过二级指针传递：

char * c;
void ProOrderInputTree(char * input, BiTree ** T)
{
    c = input;
    if(*c == 0)
        return;
    if(*c == '#')
    {
        c++;
        *T = NULL;
    }
    else
    {
        (*T) = (BiTree*)malloc(sizeof(BiTree));
        (*T)->data = *c;
        c++;
        ProOrderInputTree(c, &(*T)->lchild); 
        ProOrderInputTree(c, &(*T)->rchild); 
    }
}

这样就可以实现了

#include<stdio.h>
#include<stdlib.h>
struct TreeNode{
    char data;
    struct TreeNode *left;
    struct TreeNode *right;
};
struct TreeNode *create_by_pre(struct TreeNode *T){/*利用前序遍历构建二叉树*/
    char ch;
    printf("ch=");
    scanf("%c",&ch);
    getchar();
    if(ch=='#'){
        T=NULL;
    }else{
        T=(struct TreeNode *)malloc(sizeof(struct TreeNode));
        T->data=ch;
        T->left=create_by_pre(T->left);
        T->right=create_by_pre(T->right);
    }
    return T;
}
void preOrder(struct TreeNode *T){
    if(T!=NULL){
        printf("\t%c",T->data);
        preOrder(T->left);
        preOrder(T->right);
    }
}
void inOrder(struct TreeNode *T){
    if(T!=NULL){
        inOrder(T->left);
        printf("\t%c",T->data);
        inOrder(T->right);
    }
}
void postOrder(struct TreeNode *T){
    if(T!=NULL){
        postOrder(T->left);
        postOrder(T->right);
        printf("\t%c",T->data);
    }
}
int main(){
    struct TreeNode *T;
    T=NULL;
    T=create_by_pre(T);
    printf("前序遍历:");
    preOrder(T);
    printf("\n中序遍历:");
    inOrder(T);
    printf("\n后序遍历:");
    postOrder(T);
    return 0;
}

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

题目要求如下：
给定某一个二叉树的前序遍历和中序遍历，要求据此创建一颗符合这样遍历顺序的二叉树。

前序遍历和中序遍历的概念以及特性：

• 前序遍历：先遍历节点本身，再遍历其左孩子，最后遍历其右孩子。
• 中序遍历：先遍历其左孩子，再遍历节点本身，最后遍历其右孩子。
  我们根据这样的概念可以得出其特性：
• 一棵树的前序遍历的第一个节点一定是这棵树的根节点
• 一棵树的中序遍历中，在根节点前面遍历的节点构成根节点的左子树；在根节点后面遍历的节点构成根节点的右子树。

由这样的两个特性，我们可以先由一棵树的前序遍历来获得这棵树的根节点，然后通过根节点与其中序遍历来分别得到其左右子树的节点数目。
然后再根据左右子树的节点数目信息，我们可以从原先的根节点的前序遍历和中序遍历中截取出左右子树的前序遍历和中序遍历，之后这显然可以构成一个递归拆分问题，我们再将问题拆分成求解左右子树的根节点，将左右子树的根节点创建到根节点的左右孩子上，然后以此类推递归求解，最终可以构建出整颗二叉树。
c语言的代码实现：

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 10000
  struct TreeNode {
      int val;
      struct TreeNode *left;
      struct TreeNode *right;
  };
struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize){
 if(preorderSize==0||inorderSize==0) return NULL;
 if(preorder==NULL||inorder==NULL) return NULL;
 struct TreeNode *t=(struct TreeNode*)calloc(1,sizeof(struct TreeNode));
 //memset(t,0,sizeof(struct TreeNode));
 int root=preorder[0];
 int left_num=0,right_num=0,i=0,j=0,k=0;
 while(inorder[i]!=root)
 {
 	left_num++;
 	i++;
  } 
  right_num=preorderSize-1-left_num;
  t->val=root;
  t->left=buildTree(preorder+1,left_num,inorder,left_num);
  t->right=buildTree(preorder+1+left_num,right_num,inorder+1+left_num,right_num);
  return t;

}
LevelOrder(struct TreeNode *t)
{
	if(t==NULL) return 0;
	struct TreeNode *queue[MAXSIZE];
	struct TreeNode *temp=NULL;
	int rear=0,front=0;
	queue[rear++]=t;
	while(rear!=front)
	{
		temp=queue[front];
		printf("%d ",temp->val);
		if(temp->left!=NULL)
		{
			queue[rear++]=temp->left;
		}
		if(temp->right!=NULL)
		{
			queue[rear++]=temp->right;
		}
		front++;
	}
}
main()
{
	int size=5;
	int preorder[5]={3,9,20,15,7};
	int inorder[5]={9,3,15,20,7};
	struct TreeNode *t=buildTree(preorder,size,inorder,size);

	LevelOrder(t);
}