二叉树非递归遍历

/* ******************************************************************************
/* <PRE>
/* 版权所有    : -
/* 模块名      : 树
/* 文件名      : bitree.cpp
/* 功能描述    : 二叉树的非递归遍历
/* 作者        : <xxx>
/* 版本        : 1.0
/* -----------------------------------------------------------------------------
/* 备注        : 输入示例与输出结果
/* 
/* e.g. input  : ABD###CE#F###
/* bi-tree     :
/*                 A
/*                / \
/*               B   C
/*              /   /
/*             D   E
/*                  \
/*                   F
/* 
/* pre-order traverse: A B D C E F
/* in-order traverse: D B A E F C
/* post-order traverse: D B F E C A
/* -----------------------------------------------------------------------------
/* 修改记录    :
/* 日 期        版本     修改人        修改内容
/* 2011/01/01   1.0      <xxx>         创建
/* </PRE>
****************************************************************************** */
#include  < stdio.h >
#include  < stdlib.h >
#include  " common.h "

/* *****************************************************************************
/* 函数原型声明
/***************************************************************************** */
Status Visit(TElemType e);
Status PreOrderTraverse(BiTree T, Status ( * Visit)(TElemType));
Status InOrderTraverse(BiTree T, Status ( * Visit)(TElemType));
Status PostOrderTraverse(BiTree T, Status ( * Visit)(TElemType));


/* ******************************************************************************
/* <FUNC>
/* 函数名   : Visit
/* 功能     : 打印节点数据
/* 参数     : -
/* 返回值   : -
/* 备注     : -
/* 作者     : <xxx>
/* </FUNC>
****************************************************************************** */
Status Visit(TElemType e)
{
    printf( " %c " , e);
     return  OK;
}

/* ******************************************************************************
/* <FUNC>
/* 函数名   : PreOrderTraverse
/* 功能     : 前序遍历二叉树
/* 参数     : -
/* 返回值   : -
/* 备注     : 非递归法
/* 作者     : <xxx>
/* </FUNC>
****************************************************************************** */
Status PreOrderTraverse(BiTree T, Status ( * Visit)(TElemType))
{
    LinkStack S;  BiTNode  * p  =  NULL;
    InitStack(S); p  =  T;
     while  (p  ||   ! StackEmpty(S)) {
         if  (p) {  // 访问根结点, 遍历左子树
             if  ( ! Visit(p -> data))  return  ERROR;
            Push(S, p); p  =  p -> lchild; 
        }
         else  {  // 根指针出栈, 遍历右子树
            Pop(S, p); 
            p  =  p -> rchild;
        } // else
    }
     return  OK;
}

/* ******************************************************************************
/* <FUNC>
/* 函数名   : InOrderTraverse
/* 功能     : 中序遍历二叉树
/* 参数     : -
/* 返回值   : -
/* 备注     : 采用二叉链表存储结构, Visit是对数据元素操作的应用函数, 
/*            中序遍历二叉树T的非递归算法, 对每个数据元素调用函数Visit
/* 作者     : <xxx>
/* </FUNC>
****************************************************************************** */
Status InOrderTraverse(BiTree T, Status ( * Visit)(TElemType e))
{
    LinkStack S;  BiTNode  * p  =  NULL;
    InitStack(S); p  =  T;
     while  (p  ||   ! StackEmpty(S)) {
         if  (p) { Push(S, p); p  =  p -> lchild; }  // 根指针进栈, 遍历左子树
         else  {  // 根指针退栈, 访问根结点, 遍历右子树
            Pop(S, p);  if  ( ! Visit(p -> data))  return  ERROR;
            p  =  p -> rchild;
        } // else
    }
     return  OK;
}

/* ******************************************************************************
/* <FUNC>
/* 函数名   : PostOrderTraverse
/* 功能     : 后序遍历二叉树
/* 参数     : -
/* 返回值   : -
/* 备注     : 非递归法
/* 作者     : <xxx>
/* </FUNC>
****************************************************************************** */
Status PostOrderTraverse(BiTree T, Status ( * Visit)(TElemType))
{
    LinkStack S;  BiTNode  * p  =  NULL; 
    BiTNode  * top  =  NULL;   BiTNode  * pre  =  NULL;
    InitStack(S); p  =  T;
     while  (p  ||   ! StackEmpty(S)) {
         if  (p) {  // 遍历左子树
            Push(S, p); p  =  p -> lchild; 
        }
         else  {  // 根据栈顶元素的右孩子属性及与前驱节点的关系访问根结点或遍历右子树
                // 遍历结束条件: 栈为空且p为NULL
            GetTop(S, top);
             while  ( ! StackEmpty(S)  &&  ( ! top -> rchild  ||  top -> rchild  ==  pre)) {
                Pop(S, top);  pre  =  top; 
                 if  ( ! Visit(top -> data))  return  ERROR;
                GetTop(S, top);
            }
            p  =  StackEmpty(S)  ?  NULL : top -> rchild;
        } // else
    }
     return  OK;
}

/* ******************************************************************************
/* <FUNC>
/* 函数名   : CreateBiTree
/* 功能     : 创建二叉树
/* 参数     : -
/* 返回值   : -
/* 备注     : 前序方式创建
/* 作者     : <xxx>
/* </FUNC>
****************************************************************************** */
Status CreateBiTree(BiTree  & T)
{
     char  ch  =  getchar();
     if ( ' # '   ==  ch) T  =  NULL;
     else  {
         if ( ! (T  =  (BiTNode  * )malloc( sizeof (BiTNode)))) exit(OVERFLOW);
        T -> data  =  ch;              // 生成根结点
        CreateBiTree(T -> lchild);   // 构造左子树
        CreateBiTree(T -> rchild);   // 构造右子树
    }
     return  OK;
}

/* ******************************************************************************
/* <FUNC>
/* 函数名   : main
/* 功能     : 测试函数
/* 参数     : -
/* 返回值   : -
/* 备注     : -
/* 作者     : <xxx>
/* </FUNC>
****************************************************************************** */
void  main()
{
    BiTree T;
    CreateBiTree(T);

    printf( " Pre Order Traverse:  " );
    PreOrderTraverse(T, Visit);         // 前序方式遍历二叉树

    printf( " \nIn Order Traverse:  " );
    InOrderTraverse(T, Visit);          // 中序方式遍历二叉树

    printf( " \nPost Order Traverse:  " );
    PostOrderTraverse(T, Visit);        // 后序方式遍历二叉树
    printf( " \n " );
}

/* ******************************************************************************
/* <PRE>
/* 版权所有    : -
/* 模块名      : 树
/* 文件名      : common.h
/* 功能描述    : 栈和树的结构与函数原型 
/* 作者        : <xxx>
/* 版本        : 1.0
/* -----------------------------------------------------------------------------
/* 备注        : -
/* -----------------------------------------------------------------------------
/* 修改记录    :
/* 日 期        版本     修改人        修改内容
/* 2011/01/01   1.0      <xxx>         创建
/* </PRE>
****************************************************************************** */
#ifndef __COMMON_H__
#define  __COMMON_H__

#include  " stdio.h "  

/* *****************************************************************************
/* 数据类型和常量定义
/***************************************************************************** */
typedef  int           Status;
typedef  int           TElemType;

#define  TRUE         1
#define  FALSE        0
#define  OK           1
#define  ERROR        0
#define  OVERFLOW    -2

/* *****************************************************************************
/* 数据结构声明
/***************************************************************************** */

/*  二叉树的链式存储结构  */
typedef  struct  BiTNode {
    TElemType data;
     struct  BiTNode  * lchild,  * rchild;
} BiTNode,  * BiTree,  * SElemType;


/*  存储树的节点指针的栈结构  */
typedef  struct  SNode {
    SElemType data;
     struct  SNode  * next;
}SNode;

typedef  struct  LinkStack {
    SNode  * base ;
    SNode  * top;
}LinkStack;


/* *****************************************************************************
/* 函数原型声明
/***************************************************************************** */

/* 栈的基本操作 */
Status InitStack(LinkStack  & S);
Status StackEmpty(LinkStack S);
Status GetTop(LinkStack  & S, SElemType  & e);
Status Push(LinkStack  & S, SElemType e);
Status Pop(LinkStack  & S, SElemType  & e);

#endif

/* ******************************************************************************
/* <PRE>
/* 版权所有    : -
/* 模块名      : 树
/* 文件名      : stack.cpp
/* 功能描述    : 栈实现 
/* 作者        : <xxx>
/* 版本        : 1.0
/* -----------------------------------------------------------------------------
/* 备注        : -
/* -----------------------------------------------------------------------------
/* 修改记录    :
/* 日 期        版本     修改人        修改内容
/* 2011/01/01   1.0      <xxx>         创建
/* </PRE>
****************************************************************************** */
#include  < stdio.h >
#include  < stdlib.h >
#include  " common.h "

/* ******************************************************************************
/* <FUNC>
/* 函数名   : InitStack
/* 功能     : 构造空栈
/* 参数     : -
/* 返回值   : -
/* 备注     : -
/* 作者     : <xxx>
/* </FUNC>
****************************************************************************** */
Status InitStack(LinkStack  & S) {
    S.top  =  S. base   =  NULL;
     return  OK;
}

/* ******************************************************************************
/* <FUNC>
/* 函数名   : GetTop
/* 功能     : 获取栈顶元素
/* 参数     : -
/* 返回值   : -
/* 备注     : -
/* 作者     : <xxx>
/* </FUNC>
****************************************************************************** */
Status GetTop(LinkStack  & S, SElemType  & e)
{
     if  (S.top  ==  NULL)  return  ERROR;
     else  e  =  S.top -> data;
     return  OK;
}

/* ******************************************************************************
/* <FUNC>
/* 函数名   : Push
/* 功能     : 入栈
/* 参数     : -
/* 返回值   : -
/* 备注     : 插入元素e为新的栈顶元素
/* 作者     : <xxx>
/* </FUNC>
****************************************************************************** */
Status Push(LinkStack  & S, SElemType e) {
    SNode  * p  =  (SNode  * )malloc( sizeof (SNode));
     if  ( ! p) exit(OVERFLOW);
    p -> data  =  e;
    p -> next  =  S.top;
    S.top  =  p;
     return  OK;
}

/* ******************************************************************************
/* <FUNC>
/* 函数名   : Push
/* 功能     : 出栈
/* 参数     : -
/* 返回值   : -
/* 备注     : 若栈不空, 则删除S的栈顶元素, 用e返回其值, 并返回OK; 否则返回ERROR
/* 作者     : <xxx>
/* </FUNC>
****************************************************************************** */
Status Pop(LinkStack  & S, SElemType  & e) {
     if  (S.top  ==  S. base )
         return  ERROR;
    SNode  * p  =  S.top;
    S.top  =  S.top -> next;
    e  =  p -> data;
    free(p);
     return  OK;
}

/* ******************************************************************************
/* <FUNC>
/* 函数名   : StackEmpty
/* 功能     : 判断栈是否为空
/* 参数     : -
/* 返回值   : -
/* 备注     : 若栈空则返回TRUE; 否则返回FALSE
/* 作者     : <xxx>
/* </FUNC>
****************************************************************************** */
Status StackEmpty(LinkStack S)
{
     if  (S. base   ==  S.top)  return  TRUE;
     else   return  FALSE;
}