(1) 根据输入的(先序+中序)建立二叉树
(2) 要能直观显示一颗二叉树。

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

#define MAX    20//树的可能最大结点数
#define INIT_SIZE   10
#define ADD     5

int left[MAX];
int right[MAX];
char pre[MAX];
char ord[MAX];

typedef struct Node
{
    char data;
    struct Node *lchild;
    struct Node *rchild;
}*BiTree;

typedef struct
{
    char *base;
    char *top;
    int stack_size;
}Sq_Stack;

typedef struct
{
    char *base;
    int front, rear;
    int queue_size;
}Sq_Queue;

/////栈的基本实现函数/////
void Init_Stack( Sq_Stack &S )
{
    S.base = (char*) malloc (INIT_SIZE*sizeof(char));
    if( !S.base )
        exit(0);
    S.top = S.base;
    S.stack_size = INIT_SIZE;
}

void Push( Sq_Stack &S, char e )
{
    if( S.top - S.base >= S.stack_size )
    {
        S.base = (char*) realloc (S.base, (S.stack_size+ADD)*sizeof(char));
        if( !S.base )
            exit(0);
        S.top = S.base + S.stack_size;
        S.stack_size += ADD;
    }
    *S.top++ = e;
}

char Pop( Sq_Stack &S )
{
    if( S.top == S.base )
        return ' ';
    return *--S.top;
}

char Getop( Sq_Stack S )
{
    if( S.top == S.base )
        return '\0';
    return *(S.top-1);
}

int Empty_Stack( Sq_Stack S )
{
    if( S.top == S.base )
        return 1;
    return 0;
}
///////////////

/////////队的基本操作//////
void Init_Queue( Sq_Queue &Q )
{
    Q.base = (char*) malloc (INIT_SIZE*sizeof(char));
    if( !Q.base )
        exit(0);
    Q.front = Q.rear = 0;
    Q.queue_size = INIT_SIZE;
}

void Enter_Queue( Sq_Queue &Q, char e)
{
    if( Q.rear >= Q.queue_size-1 )
    {
        Q.base = (char*) realloc (Q.base, (Q.queue_size+ADD)*sizeof(char));
        if( !Q.base )
            exit(0);
        Q.queue_size += ADD;
    }
    Q.base[Q.rear++] = e;
}

void Delete_Queue( Sq_Queue &Q, char &e )
{
    if( Q.rear == Q.front )
        return;
    e = Q.base[Q.front++];
}
/////////////////////////////////

void Init_Date( Sq_Stack &S, Sq_Queue &Q )
{
    int i, j;

    printf("输入先序:");
    scanf("%s", pre);
    printf("输入中序(加上#作标志):");
    scanf("%s", ord);

    for( i=0; i<strlen(pre); ++i )
        for( j=0; j<strlen(ord); ++j )
            if( pre[i] == ord[j] )
            {
                ord[j] = '#';
                if( ord[j+1] == '#' )
                    right[i] = 0;
                else
                    right[i] = 1;
                if( ord[j-1] == '#' )
                    left[i] = 0;
                else
                    left[i] = 1;
                break;
            }
/*    for( i=0; i<strlen(pre); ++i )
        printf("%d ", left[i]);
    printf("\n");
    for( i=0; i<strlen(pre); ++i )
        printf("%d ", right[i]);
    printf("\n");*/
    for( i=0; i<strlen(pre); ++i )
    {
        if( left[i] )
        {
            Push( S, pre[i] );
            Enter_Queue( Q, pre[i] );
        }
        else
        {
            Enter_Queue( Q, pre[i] );
            Enter_Queue( Q, '#' );
            if( !right[i] )
                Enter_Queue( Q, '#');
        }
    }

    while( !Empty_Stack( S ) )
    {
        for( i=0; i<strlen(pre); ++i )
            if( Getop(S) == pre[i] )
            {   
                Pop(S);
                if( !right[i] )
                    Enter_Queue( Q, '#');
                break;
            }
    }
}

void Create_BiTree( BiTree &T, Sq_Queue &Q )
{
    if( Q.front != Q.rear )
    {
        char c;
        Delete_Queue( Q, c );
        if( c == '#' )
            T = NULL;
        else
        {
            T = (BiTree) malloc (sizeof(BiTree));
            T->data = c;
            Create_BiTree( T->lchild, Q );
            Create_BiTree( T->rchild, Q );
        }
    }
}

void Print_BiTree( BiTree T, int i )
{
    if(T)
    {
        int j;
        for( j=0; j<i; ++j )
            printf("--");
        printf("%c\n", T->data);
        Print_BiTree( T->lchild, i+1 );
        Print_BiTree( T->rchild, i+1 );

    }
}

int main()
{
    BiTree T = NULL;
    Sq_Stack S;
    Sq_Queue Q;

    Init_Stack( S );
    Init_Queue( Q );
    Init_Date( S, Q );
/*    char c;
    while( Q.front != Q.rear )
    {
        Delete_Queue( Q, c );
        printf("%c ", c);
    }
    printf("\n");*/
    Create_BiTree( T, Q );
    Print_BiTree( T, 1 );
    return 0;
}