学步园

1、中序遍历的投影法

2、先序遍历的填空法（后序遍历也可用此法）

 
 如果给定一棵二叉树的图形形态，可在图形基础上，采用填空法迅速写出该二叉树的先序遍历序列。具体做法是：我们知道，对于每个结点都由三个要素组成，即根结点，左子树、右子树；又已知先序遍历顺序是先访问根结点、然后访问左子树、访问右子树。那么，我们按层分别展开，逐层填空即可得到该二叉树的先序遍历序列。

(1)根结点 左子树 右子树
     A      ( )    ( )

(2) A (根结点(左子树)(右子树))  (根结点(左子树)(右子树))
     A  (B       (        ) (        ))  ( C      (         )(        ))  

     A  (B      (根结点(左)(右))(根结点(左)(右)))  ( C (……)(……))

    ...
     A   B       D         无       G          E     H       无          C    F     无

(3)A B D G J E H C F I 此即为该二叉树的先序遍历序列。

3、代码实现

#include <stdio.h>
#include <malloc.h>

typedef char t_elemtype; 
typedef struct bitree_node* s_elemtype; 

typedef int status;

#define OK 1 
#define ERROR 0 

#define STACK_INIT_SIZE 128

int g_print_stack = 1;

struct bitree_node 
{
    t_elemtype data;
    struct bitree_node *lchild;
    struct bitree_node *rchild;
};

struct stack
{
    s_elemtype *base;
    s_elemtype *top;
    int stack_size;
};

status init_stack(struct stack *S)
{
     (*S).base = (s_elemtype*)malloc(sizeof(s_elemtype) * STACK_INIT_SIZE);
     if (!(*S).base)
     {
         printf("%s: malloc failed\n", __FUNCTION__);
         return ERROR;
     }

     (*S).top = (*S).base;
     (*S).stack_size = STACK_INIT_SIZE;

     return OK;
}

status get_top_of_stack(struct stack S, s_elemtype *e)
{
    if (S.base == S.top)
    {
        return ERROR;
    }
    else
    {
        (*e) = *(S.top - 1);
    }

    return OK;
}

status stack_empty(struct stack S)
{
    return (S.base == S.top? 1 : 0);
}

void push_stack(struct stack *S, s_elemtype e)
{
    *((*S).top++) = e;
    
    if (1 == g_print_stack)
    {
        if (e == NULL)
        {
            printf("push #\n");
        }
        else
        {
            printf("push %c\n", e->data);
        }
    }
}

void pop_stack(struct stack *S, s_elemtype *e)
{
    (*e) = *(--(*S).top);

    if (1 == g_print_stack)
    {
        if (*e == NULL)
        {
            printf("pop  #\n");
        }
        else
        {
            printf("pop  %c\n", (*e)->data);
        }
    }
}

void visit(t_elemtype data)
{
    printf("%c ", data);
}

status create_bitree(struct bitree_node **T)
{
    t_elemtype ch;

   scanf("%c", &ch);

   if (ch == '#')
   {
       (*T) = NULL;
   }
   else
   {
       (*T) = (struct bitree_node *)malloc (sizeof(struct bitree_node));  
       if(!(*T))
       {
           printf("%s: malloc failed\n", __FUNCTION__);
           return ERROR;
       }

       (*T)->data = ch;
       create_bitree(&((*T)->lchild));
       create_bitree(&((*T)->rchild));
   }

   return OK;
}

void inorder_traverse(struct bitree_node *T)
{
    if (T)
    {
        inorder_traverse(T->lchild);
        visit(T->data);
        inorder_traverse(T->rchild);
    }
}

void preorder_traverse(struct bitree_node *T)
{
    if (T)
    {
        visit(T->data);
        preorder_traverse(T->lchild);
        preorder_traverse(T->rchild);
    }
}


void inorder_traverse_stack(struct bitree_node *T)
{
    struct stack S;
    struct bitree_node *e;

    init_stack(&S);
    push_stack(&S, T);

    while (!stack_empty(S))
    {
        while (get_top_of_stack(S, &e) && e)
        {
            push_stack(&S, e->lchild);
        }

        pop_stack(&S, &e);

        if (!stack_empty(S))
        {
            pop_stack(&S, &e);

            if (0 == g_print_stack)
            {
                visit(e->data);
            }
            
            push_stack(&S, e->rchild);
        }
    
    }

}


int main(void)
{
    struct bitree_node *T; 

    printf("plese input the preorder tree. if empty, input '#'\n");
    create_bitree(&T);

    printf("\npreorder traverse:\n");
    preorder_traverse(T);

    printf("\ninorder traverse:\n");
    inorder_traverse(T);

    printf("\nprint stack in/out info of inorder traverse by the tree with stack:\n");
    inorder_traverse_stack(T);

    printf("\ninorder traverse the bitree with stack:\n");
    g_print_stack = 0;
    inorder_traverse_stack(T);

    return 0;
}