二叉树的各种遍历操作(非)递归.c

数据结构的基本应用

/*二叉树的各种遍历操作*/
//#include<alloc.h> 
#include<stdio.h>
#include<malloc.h>
#include<conio.h>

/*函数结果状态代码*/
#define   True        1
#define   False       0
#define   Ok          1
#define   Error       0
#define   Infeasible  -1
#define   Overflow    -2
#define   Null        0
#define STACK_INIT_SIZE 100
#define Stackincrement 10
 
typedef int Status ;
typedef char TElemType;/* 抽象元素类型为char类型 */
typedef struct BiTNode {
    TElemType data;
    struct BiTNode *lchild,*rchild;/*左右孩子指针*/
}BiTNode;
typedef struct BiTNode *BiTree;
typedef struct BiTNode SElemType;

struct STACK
{
  SElemType *base;
  SElemType *top;
  int stacksize;
};

typedef struct STACK SqStack;

int InitStack(SqStack *S)
   /*构造一个空栈*/
{
  S->base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));
  if(!S->base)
    exit(Overflow);/*存储分配失败*/
  S->top=S->base;
  S->stacksize=STACK_INIT_SIZE;
  return Ok;
}/*InitStack()*/



Status StackEmpty(SqStack *S)
  /*判断栈S是否为空*/
{
  if(S->top==S->base) return True;
  else
    return False;
}/*StackEmpty()*/




int StackLength(SqStack *S)
  /*求栈S中的数据个数*/
{
  int i;
  SElemType *p;
  i=0;
  p=S->top;
  while(p!=S->base)
    {
      p--;
      i++;
    }/*while*/
  return i;
}/*StackLength()*/





int GetTop(SqStack *S,SElemType **e)
  /*若栈不空，则用e返回S的栈顶元素，并返回Ok，否则返回Error*/
{
  if(S->top==S->base)
    return Error;
  else 
    {
      *e=S->top-1;
      return Ok;
    }/*else*/
}/*GetTop()*/



int Push(SqStack *S,SElemType *e)
  /*插入元素e为新的栈顶元素*/
{
  if(S->top-S->base>=S->stacksize)/*栈满，追加存储空间*/
    {
      S->base=(SElemType*)realloc(S->base,(S->stacksize+Stackincrement)*sizeof(SElemType));
      if(!S->base)exit(Overflow);
      S->top=S->base+S->stacksize;
      S->stacksize+=Stackincrement;
    }/*if*/
  S->top->data=e->data;
  S->top->rchild=e->rchild;
  S->top->lchild=e->lchild;
  ++S->top;
}/*Push()*/




int Pop(SqStack *S,SElemType **e)
  /*若栈不空，则删除S的栈顶元素，用e返回其值，并返回Ok；否则返回Error*/
{
  if(S->top==S->base)
    return Error;
  else
    {
      (*e)->data=(S->top-1)->data;
      (*e)->rchild=(S->top-1)->rchild;
      (*e)->lchild=(S->top-1)->lchild;
      --S->top;
    }/*else*/
  return Ok;
}/*Pop()*/



int CreateBiTree(BiTNode **T)
  /*  按先序次次序输入二叉树终结点的值（一个字符），空格字符表示空树，构造二叉链表表示的二叉树T  */
{
  TElemType ch;
  scanf("%c",&ch);
  if(ch=='#')
    (*T)=Null;
  else
    {
      (*T)=(BiTNode*)malloc(sizeof(BiTNode));
      if(!(*T))
        exit(Overflow);
      (*T)->data=ch;  /*  生成根节点  */
      CreateBiTree(&(*T)->lchild);  /*  构造左子树  */
      CreateBiTree(&(*T)->rchild);  /*  构造右子树  */
    }/*else*/
  return Ok;
}  /*  CreateBiTree()  */



int PreOrderTraverse(BiTree T,int (*Visit)(TElemType))
  /*采用二叉链表存储结构，Visit是对数据元素操作的应用函数      */
  /*先序遍历二叉树T的递归算法，对每个数据元素调用函数Visit     */
  /*最简单的Visit函数是：                                      */
  /*                        int PrintElememt(TElemType e)      */
  /*                          输出元素e的值                    */
  /*                        {                                  */
  /*                          printf(e);  实用时，加上格式串   */ 
  /*                          return Ok;                       */
  /*                        }                                  */
  /*调用实例：PreOrderTraverse(T,PrintElement)                 */
{
  if(T)
    {
      if(Visit(T->data))
        if(PreOrderTraverse(T->lchild,Visit))
          if(PreOrderTraverse(T->rchild,Visit))
            return Ok;
      return Error;
    }
  else
    return Ok;
}/*PreOrderTraverse()*/
  


int InOrderTraverse(BiTree T,int (*Visit)(TElemType))
  /*中序遍历二叉树T的递归算法*/
{
  if(T)
    {       
      if(InOrderTraverse(T->lchild,Visit))
        if(Visit(T->data))
          if(InOrderTraverse(T->rchild,Visit))
            return Ok;
      return Error;
    }
  else
    return Ok;
}/*InOrderTraverse()*/





int PostOrderTraverse(BiTree T,int (*Visit)(TElemType))
  /*后序遍历二叉树T的递归算法*/
{
  if(T)
    {       
      if(PostOrderTraverse(T->lchild,Visit))
        if(PostOrderTraverse(T->rchild,Visit))
	  if(Visit(T->data))
            return Ok;
      return Error;
    }
  else
    return Ok;
}/*PostOrderTraverse()*/

 


int InOrderTraverse1(BiTree T,int(*Visit)(TElemType))
  /*采用二叉链表存储结构，Visit是对数据元素操作的应用函数。*/
  /*中序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit*/
{
  SqStack *S;
  SElemType *p;

  S=(SqStack*)malloc(sizeof(SqStack));
  p=(SElemType*)malloc(sizeof(SElemType));
  
  InitStack(S);
  Push(S,T);  /*根指针进栈*/
  while(!StackEmpty(S))
    {
      while(GetTop(S,&p)&&p->data>='a'&&p->data<='z')
        {Push(S,p->lchild);}  /*向左走到尽头*/
      Pop(S,&p);  /*空指针退栈*/
      if(!StackEmpty(S))  /*访问结点，向右一步*/
        {
          Pop(S,&p);
          if(!Visit(p->data))
            return Error;
          Push(S,p->rchild);
        }/*if*/
    }/*while*/                                                                     
  return Ok;
}/*InOrderTraverse1()*/



int PreOrderTraverse1(BiTree T,int(*Visit)(TElemType))
  /*采用二叉链表存储结构，Visit是对数据元素操作的应用函数。*/
  /*先序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit*/
{
  SqStack *S;
  SElemType *p;

  S=(SqStack*)malloc(sizeof(SqStack));
  p=(SElemType*)malloc(sizeof(SElemType));
  
  InitStack(S);
  Push(S,T);/*根指针进栈*/
  while(!StackEmpty(S))
    {
      while(GetTop(S,&p)&&p->data>='a'&&p->data<='z')  /*先遍历左子树*/
        {
          if(!Visit(p->data))
            return Error;
          p=p->lchild;
          Push(S,p);
        }/*while*/
      Pop(S,&p);  /*空指针退栈*/
      if(!StackEmpty(S))  /*通过下一次循环中的内嵌while实现右子树遍历*/
        {
          Pop(S,&p);
          p=p->rchild;
          Push(S,p);       
        }/*if*/
    }/*while*/                                                                     
  return Ok;
}/*PreOrderTraverse1()*/



int PostOrderTraverse1(BiTree T,int(*Visit)(TElemType))
  /*采用二叉链表存储结构，Visit是对数据元素操作的应用函数。*/
  /*后序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit*/
{
  SqStack *S;
  SElemType *p,*t;
  int tag[100];

  S=(SqStack*)malloc(sizeof(SqStack));
  p=(SElemType*)malloc(sizeof(SElemType));
  t=(SElemType*)malloc(sizeof(SElemType));
  
  InitStack(S);
  p=T;/*Push(S,T);*/
  do
    {
      while(p->data>='a'&&p->data<='z')
        {
          Push(S,p);          
          tag[StackLength(S)]=0;
          p=p->lchild;
        }  /*向左走到尽头*/
      if(!StackEmpty(S))  /*访问结点，向右一步*/
        {
          if(GetTop(S,&t)&&tag[StackLength(S)]==1)
            {
              Pop(S,&t);
              if(!Visit(t->data))
                return Error;
            }/*if*/
          else
            {
              GetTop(S,&p);
              if(!StackEmpty(S))
                {
                  p=p->rchild;  /*扫描右子树*/
                  tag[StackLength(S)]=1;
                }
            }
        }/*while*/
    }while(p->data>='a'&&p->data<='z'||!StackEmpty(S)); 
  return Ok;
}/*PostOrderTraverse1()*/



int PrintTree(TElemType e)
  /*输出二叉树中的每一个结点*/
{
  printf("%c  ",e);
  return Ok;
}



main()
{
  BiTree T;
  CreateBiTree(&T);
  printf("preOrder:");
  PreOrderTraverse(T,PrintTree);
  printf("\n");
  printf("InOrder:");
  InOrderTraverse(T,PrintTree);
  printf("\n");
  printf("postOrder:");
  PostOrderTraverse(T,PrintTree);
  printf("\n");
  printf("not recursion InOrder:");
  InOrderTraverse1(T,PrintTree);
  printf("\n");
  printf("not recursion PreOrder:");
  PreOrderTraverse1(T,PrintTree);
  printf("\n");
  printf("not recursion PostOrder:");
  PostOrderTraverse1(T,PrintTree);
  printf("\n");
}