蔡子经数据结构5.6

#define MAXN 100

typedef struct  ;
struct 
{
    int val;
    node *lchild,*rchild;
};

node* createNode()
{
    node *ret = (node*)malloc(sizeof(node));
    ret->lchild = ret->rchild = NULL;
    ret->val = 0;
    return ret;
}
            //   0 1 2 3 4 5 6
int pre[MAXN] = {4,2,1,3,6,5,7};
int in[MAXN] = {1,2,3,4,5,6,7};
            //  0 1 2 3 4 5 6

node* createTree(int fst, int l, int r)
{
    if(l > r) return NULL;
    node* rt = createNode();
    int axi = 0;
    for(int i = l; i <= r; ++i)
    {
        if(in[i] == pre[fst])
        {
            axi = i;
            break;
        }
    }
    rt->val = pre[fst];
    rt->lchild = createTree(fst+1, l, axi-1);
    rt->rchild = createTree(fst+axi-l+1, axi+1, r);
    return rt;
}

void InOrder(node *rt)
{
    if(rt == NULL) return;
    InOrder(rt->lchild);
    printf("%d ",rt->val);
    InOrder(rt->rchild);
}

int main()
{
    node *root = createTree(0, 0, 6);
    InOrder(root);
    return 0;
}