143-6

二叉树的结点值各不相同，先序序列和中序序列分别存储在数组A和B中，设计算法构建二叉树

使用递归方法。

1、使用指针传入数组，方便进行根节点操作。

TreeNode* BuildTree(int *A,int Alen,int *B,int Blen)
T->lchild=BuildTree(A+1,index,B,index);        
T->rchild=BuildTree(A+index+1,Alen-index-1,B+index+1,Blen-index-1);

重点：A+1——>A[1]变成了A[0]，以此类推。

2、需要使用一个变量在B中分出左子树结点和右子树结点

int index=0;
for(;index<Blen;index++)
    if(B[index]==T->data)
　　 　　break;

3、完成代码

#include <stdio.h>
#include <stdlib.h>

typedef struct node{
    int data;
    struct node *lchild,*rchild;
}TreeNode,*Tree;

void CreateTree(Tree &T)
{
    int x;
    scanf("%d",&x);
    if(x==-1)
    {
        T=NULL;
        return;    
    }
    else
    {
        T=(TreeNode*)malloc(sizeof(TreeNode));
        T->data=x;
        printf("输入%d的左结点:",x);
        CreateTree(T->lchild);
        printf("输入%d的右结点:",x);
        CreateTree(T->rchild);
    }
}

void PreOrder(Tree T)        //先序遍历 
{
    if(T!=NULL)
    {
        printf("%d  ",T->data);
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}

void MidOrder(Tree T)        //中序遍历 
{
    if(T!=NULL)
    {
        MidOrder(T->lchild);
        printf("%d  ",T->data);
        MidOrder(T->rchild);
    }
}

TreeNode* BuildTree(int *A,int Alen,int *B,int Blen)    //传入的数组是指针形式的！！！ 
{
    if(Alen==0)
        return NULL;
        
    Tree T=(Tree)malloc(sizeof(TreeNode));
    T->data=A[0];
    T->lchild=NULL;
    T->rchild=NULL;
    
    int index=0;
    for(;index<Blen;index++)
        if(B[index]==T->data)
            break;
    
    T->lchild=BuildTree(A+1,index,B,index);        //指针形式的数组方便进行变换 
    T->rchild=BuildTree(A+index+1,Alen-index-1,B+index+1,Blen-index-1);
    
    return T;
}

int main()
{
    /*
    Tree T;
    CreateTree(T);
    PreOrder(T);
    printf("\n");
    MidOrder(T);
    */
    int A[]={1,2,4,6,3,5};
    int B[]={2,6,4,1,3,5};
    int Alen=sizeof(A)/sizeof(A[0]);
    int Blen=sizeof(B)/sizeof(B[0]);
    MidOrder(BuildTree(A,Alen,B,Blen));     //中序遍历验证 
    
    return 0;
}