遍历二叉树

一下是递归遍历二叉树的先序、中序和非递归遍历二叉树的六种算法：


#include
#include
#define MAXSIZE 50
 
typedef struct Node
{
    char data;
    struct Node *LChild;
    struct Node *RChild;
}BiTNode,*BiTree;
 
void CreateBiTree(BiTree *bt)
{
    char ch;
    ch = getchar();
    if(ch == ' ')  *bt = NULL;
    else 
    {
        *bt=(BiTree)malloc(sizeof(BiTNode));
        (*bt) -> data = ch;
        CreateBiTree(&((*bt)->LChild));
        CreateBiTree(&((*bt)->RChild));
    }
}
 
void PreOrder(BiTree root)
{
    /*先序递归遍历二叉树*/
    if(root != NULL)
    {
        printf("%c ",root -> data);                   
        PreOrder(root -> LChild);                     
        PreOrder(root -> RChild);                       
    }
}
 
void InOrder(BiTree root)
{
    /* 中序递归遍历二叉树*/
    if(root != NULL)
    {
        InOrder(root -> LChild);                   
        printf("%c ",root -> data);                    
        InOrder(root -> RChild);                         
    }
}
 
void PostOrder(BiTree root)
{
    /*后序递归遍历二叉树*/
    if(root != NULL)
    {
        PostOrder(root -> LChild);                    
        PostOrder(root -> RChild);                      
        printf("%c ",root -> data);
    }
}
 
void PPreOrder(BiTree root)
{
    /*先序非递归遍历二叉树*/
    int top;
    BiTree s[MAXSIZE],p,q;                 
    p = root;
    top = 0;
    q = NULL;
    
    while(p != NULL || top != 0)
    {
        while(p != NULL)
        {
            printf("%c ",p -> data);                 /*访问当前节点*/
                top = top + 1;
            if(top > MAXSIZE) 
                return;
            s[top] = p;                              /*入栈*/ 
            p = p -> LChild;                         /*进入到左子树*/
        }
        if(top > 0)
        {
            p = s[top];                              /*出栈ˆ*/ 
            top--;
            p = p -> RChild;                         /*进入到右子树*/
        }
    }
}
 
void InnOrder(BiTree root)
{
    /*中序非递归遍历二叉树*/
    BiTree p,s[MAXSIZE];
    int top = 0;
    p = root;
    do
    {
      while(p!=NULL)
      {
        if(top > MAXSIZE) return;
        top = top + 1;
        s[top] = p;
        p = p ->LChild;
      }                                                /*进入到左子树*/            
      if(top!=0)
      {
 
        p = s[top];
        top = top - 1;
        printf("%c ",p -> data);                       /*访问当前节点*/
        p = p -> RChild;                               /*进入到右子树*/        
      }
    }while(p!=NULL || top != 0);
}
 
void PPostOrder(BiTree root)
{   /*后序非递归访问二叉树*/
    BiTree p,q,s[MAXSIZE];
    int top = 0;
    q = NULL;
    p = root;
    while(p != NULL || top != 0)
    {
        while(p!=NULL)
        {
        top++;
        if(top > MAXSIZE) return;
        s[top] = p;
        p = p->LChild ;
        }
    if(top > 0)
    {
        p = s[top];
        if((p -> RChild == NULL) || (p -> RChild == q))
        {
           printf("%c ",p->data);
           q = p;
           top --;
           p = NULL;
        }
        else 
             p = p -> RChild;
    }
}
}
int main()
{
 
        BiTree root;
    
    printf("创建二叉树:\n");
    CreateBiTree(&root);                            
        
    printf("先序递归遍历:    ");
    PreOrder(root);
    printf("\n");
 
    printf("中序递归遍历:    ");
    InOrder(root);
    printf("\n");
 
    printf("后序递归遍历");
    PostOrder(root);
    printf("\n");
 
    printf("先序非递归遍历:  ");
    PPreOrder(root);
    printf("\n");
 
    printf("中序非递归遍历:  ");
    InnOrder(root);
    printf("\n");
 
    printf("后序非递归遍历:  ");
    PPostOrder(root);
    printf("\n");
 
    return 0;
}