/* *  名 称: 建立二叉树(非递归) *  作 者: Brooke gao *  时 间: 2013/8/21 *  */    #include<stdio.h>#include<stdlib.h>#include<malloc.h>#define STACKSIZE 50#define bitree_size(tree)  ((tree)->size)   #define bitree_root(tree)  ((tree)->root)#define bitree_left(node)  ((node)->left)#define bitree_right(node) ((node)->right)/* *  定义二叉树结点以及二叉树的结构 **/typedef struct BiTreeNode_{    char data;    struct BiTreeNode_ *left;    struct BiTreeNode_ *right;}BiTreeNode;typedef struct BiTree_{    int size;    BiTreeNode *root;}BiTree;/* *  定义栈的结构 **/typedef struct Stack_{    BiTreeNode * base[STACKSIZE];    int top;    int stacksize;}Stack;void stack_init(Stack *stack){    stack->top = -1;    stack->stacksize = 0;}void push(Stack *stack, BiTreeNode *node){    if(stack->stacksize == STACKSIZE)        exit(-1);    stack->base[++stack->top] = node;    stack->stacksize++;}int stack_empty(Stack *stack){    if((-1 == stack->top) && (0 == stack->stacksize))        return 1;    else        return 0;}BiTreeNode* pop(Stack *stack){    if(stack->top < 0)        exit(-1);    else    {        stack->stacksize--;        return stack->base[stack->top--];    }}BiTreeNode* get_stack_top(Stack *stack){    if(stack->top < 0)        exit(-1);    return stack->base[stack->top];}void bitree_init(BiTree *tree){    tree->size = 0;    tree->root = NULL;}//给树tree的某个结点node插入数据域为data的左子树int bitree_ins_left(BiTree *tree, BiTreeNode *node, const char data){    BiTreeNode *new_node, **position;    if(NULL == node)    {        if(bitree_size(tree) > 0)            return -1;        position = &tree->root;    }    else    {        if(bitree_left(node) != NULL)            return -1;        position = &node->left;    }    if( NULL == (new_node = (BiTreeNode *)malloc(sizeof(BiTreeNode))) )        return -1;    new_node->data =http://www.mamicode.com/ data;    new_node->left = NULL;    new_node->right = NULL;    *position = new_node;    tree->size++;            return 0;}//给树tree的某个结点node插入数据域为data的右子树int bitree_ins_right(BiTree *tree, BiTreeNode *node, const char data){    BiTreeNode *new_node, **position;    if(NULL == node)    {        if(bitree_size(tree) > 0)            return -1;        position = &tree->root;    }    else    {        if(bitree_right(node) != NULL)            return -1;        position = &node->right;    }    if( NULL == (new_node = (BiTreeNode *)malloc(sizeof(BiTreeNode))) )        return -1;    new_node->data =http://www.mamicode.com/ data;    new_node->left = NULL;    new_node->right = NULL;    *position = new_node;    tree->size++;    return 0;}// 先序遍历函数void pre_order(const BiTreeNode *node){    if(node)    {        printf("%c",node->data);        pre_order(node->left);        pre_order(node->right);    }}// 中序遍历函数void in_order(const BiTreeNode *node){    if(node)    {        in_order(node->left);        printf("%c",node->data);        in_order(node->right);    }}// 后序遍历函数void end_order(const BiTreeNode *node){    if(node)    {        end_order(node->left);        end_order(node->right);        printf("%c",node->data);    }}int main(){    char data;    Stack stack;    BiTree tree;    BiTreeNode *node;        stack_init(&stack);    bitree_init(&tree);    printf("请以先序顺序输入结点值: \n");    data = getchar();        if( 0 == bitree_size(&tree) )    {        if( ‘ ‘ == data )            return -1;        bitree_ins_left(&tree,NULL,data);        push(&stack,tree.root);    }    while(!stack_empty(&stack))    {        data = getchar();        if( ‘ ‘ == data )        {            node = pop(&stack);                        if(NULL == node->left)            {                data = getchar();                if( ‘ ‘ != data )                {                    bitree_ins_right(&tree,node,data);                    push(&stack,node->right);                }            }        }        else        {            node = get_stack_top(&stack);            if( NULL == node->left )            {                bitree_ins_left(&tree,node,data);                push(&stack,node->left);            }            else            {                node = pop(&stack);                bitree_ins_right(&tree,node,data);                push(&stack,node->right);            }        }    }    printf("-----先序遍历二叉树-----\n");    pre_order(tree.root);    putchar(‘\n‘);        printf("-----中序遍历二叉树-----\n");    in_order(tree.root);    putchar(‘\n‘);    printf("-----后序遍历二叉树-----\n");    end_order(tree.root);    putchar(‘\n‘);    return 0;}