学步园

#include <stdio.h>      
#include <stdlib.h>      
#define INIT_STACK_SIZE 100      
#define STACKINCREMENT 10      
      
//*****二叉树的二叉链表存储结构*****//  
typedef struct BiNode      
{      
    char data;      
    struct BiNode *lchild, *rchild;     
    int visitcount;                 //访问次数(后序遍历会用到)  
}BiNode, *BiTree;      
      
typedef struct      
{      
    BiNode **base;      
    BiNode **top;      
    int stacksize;      
}SqStack;      
  
//*****初始化栈*****//     
void InitStack(SqStack &S)                   
{      
    if (!(S.base = (BiNode **)malloc(sizeof(BiTree) * INIT_STACK_SIZE)))      
    {      
        return;      
    }      
    S.top = S.base;      
    S.stacksize = INIT_STACK_SIZE;      
      
    return;      
}      
      
//*****元素进栈*****//  
void Push(SqStack &S, BiNode *e)             
{      
    if (S.top - S.base >= S.stacksize)      
    {      
        if (!(S.base = (BiNode **)realloc(S.base, sizeof(BiTree) * (STACKINCREMENT + S.stacksize))))    
        {      
            return;      
        }      
        S.stacksize += STACKINCREMENT;      
    }      
    *S.top++ = e;      
      
    return;      
}      
      
//*****元素出栈*****//  
void Pop(SqStack &S, BiNode **e)             
{      
    if (S.base == S.top)      
    {      
        return;      
    }      
    *e = *--S.top;      
      
    return;      
}      
  
//*****取栈顶元素*****//      
int GetTop(SqStack S, BiNode **e)      
{      
    if (S.base == S.top)      
    {      
        return 0;      
    }      
    *e = *(S.top - 1);      
          
    return 1;      
}      
      
//*****判断栈是否为空*****//    
int StackEmpty(SqStack S)           
{      
    if (S.top == S.base)      
        return 1;      
    else      
        return 0;      
}      
  
//*****按先序次序输入二叉树中结点的值(一个字符)，空格字符表示空树构造二叉链表表示的二叉树T*****//      
void CreateBiTree(BiTree &T)              
{                                         
    char ch;        
    scanf("%c", &ch);        
    if(ch == ' ')        
    {        
        T = NULL;        
    }        
    else        
    {        
        if(!(T = (BiNode *)malloc(sizeof(BiNode))))         
        {        
            return;        
        }        
        T->data = ch;                    //生成根结点        
        CreateBiTree(T->lchild);     //构造左子树        
        CreateBiTree(T->rchild);     //构造右子树        
    }        
          
    return;        
}        
  
//*****先序遍历二叉树方法1*****//   
void PreorderTraverse_1(BiTree T)                         
{    
    BiTree p;    
    SqStack S;    
    InitStack(S);    
    Push(S, T);                                         //根指针进栈    
    while(!StackEmpty(S))    
    {    
        while(GetTop(S, &p) && p)     
        {                                                   
            printf("%c ", p->data);                          
            Push(S, p->lchild);     
        }    
        Pop(S, &p);                                     //空指针退栈      
        if(!StackEmpty(S))    
        {    
            Pop(S, &p);                                 //根结点出栈    
            Push(S,p->rchild);                           //右孩子进栈    
        }    
    }    
      
    return;    
}    
  
//*****先序遍历二叉树方法2*****//   
void PreorderTraverse_2(BiTree T)                           
{      
    BiTree p = T;      
    SqStack S;      
    InitStack(S);      
      
    while (p || !StackEmpty(S))      
    {      
        if (p)      
        {      
            printf("%c ", p->data);    
            Push(S,p);      
            p = p->lchild;      
        }      
        else      
        {      
            Pop(S, &p);      
            p = p->rchild;      
        }      
    }      
}   
  
//*****中序遍历二叉树方法1*****//   
void InOrderTraverse_1(BiTree T)                          
{    
    SqStack S;    
    BiTree p;    
    InitStack(S);    
    Push(S,T);       
    while (!StackEmpty(S))    
    {    
        while (GetTop(S,&p) && p)      
        {    
            Push(S,p->lchild);                           //向左走到尽头    
        }    
        Pop(S,&p);                                      //空指针退栈      
        if (!StackEmpty(S))    
        {      
            Pop(S,&p);      
            printf("%c ", p->data);    
            Push(S,p->rchild);    
        }    
    }    
      
    return;    
}    
  
//*****中序遍历二叉树方法2*****//   
void InOrderTraverse_2(BiTree T)                           
{      
    BiTree p = T;      
    SqStack S;      
    InitStack(S);      
      
    while (p || !StackEmpty(S))      
    {      
        if (p)      
        {      
            Push(S,p);      
            p = p->lchild;      
        }      
        else      
        {      
            Pop(S, &p);      
            printf("%c ", p->data);      
            p = p->rchild;      
        }      
    }     
      
    return;    
}           
  
//*****后序遍历二叉树*****//   
void PostOrderTraverse(BiTree T)    
{    
    SqStack S;    
    BiTree p = T;    
    InitStack(S);    
        
    while (p || !StackEmpty(S))    
    {    
        if(p)    
        {    
            if (p->visitcount != 2)    
            {    
                p->visitcount = 1;    
                Push(S, p);    
            }    
            p = p->lchild;    
        }    
        else     
        {               
            Pop(S, &p);      
            if(p->visitcount == 2)    
            {    
                printf("%c ", p->data);      
            }    
            else     
            {     
                p->visitcount++;     
                Push(S, p);    
            }    
            p = p->rchild;    
        }    
    }    
        
    return;    
}    
    
int main(void)      
{      
    BiTree T;      
    printf("请按先序次序输入二叉树中结点的值(字符)，空格字符表示空树:\n");  
    CreateBiTree(T);      
      
    printf("先序遍历方法1结果为:");  
    PreorderTraverse_1(T);  
    printf("\n\n");   
  
    printf("先序遍历方法2结果为:");  
    PreorderTraverse_2(T);  
    printf("\n\n");   
  
    printf("中序遍历方法1结果为:");  
    InOrderTraverse_1(T);  
    printf("\n\n");   
      
    printf("中序遍历方法2结果为:");  
    InOrderTraverse_2(T);  
    printf("\n\n");   
  
    printf("后序遍历结果为:");  
    PostOrderTraverse(T);      
    printf("\n\n");      
      
    return 0;      
}      

以如下二叉树为例，给出按先序次序输入二叉树中结点的值（字符），从而按照本文给出的算法构造二叉树。

输入字符的顺序是：-+a空格空格*b空格空格-c空格空格d空格空格/e空格空格f空格空格，即可验证本文给出的遍历算法。