二叉树各种操作的C语言实现（二）（递归，非递归..

时间：2010-07-31 来源：frankzfz

这一篇主要是二叉树中各种遍历的非递归和递归算法的实现：

void PreOrderTraverse(BiTree *T,Status(*Visit)(TElemType))
{// 先序递归遍历T，对每个节点调用函数visit一次且仅一次

  if(T)
  {
    Visit(T->data);
    PreOrderTraverse(T->lchild,Visit);
    PreOrderTraverse(T->rchild,Visit);
  }
}

void InOrderTraverse(BiTree *T,Status(*Visit)(TElemType))
{//中序递归遍历T，对每个节点调用函数visit一次

  if(T)
  {
    InOrderTraverse(T->lchild,Visit);
    Visit(T->data);
    InOrderTraverse(T->rchild,Visit);
  }
}

typedef BiTree_1 SElemType;
#include "Stack.h"
#include "Stack.c"
Status InOrderTraverse1(BiTree *T,Status(*Visit)(TElemType))
{//中序遍历二叉树T的非递归算法（利用栈），对每个数据元素调用函数visit

  SqStack S;
  BiTree *p;

  InitStack(&S);
  while(T||!StackEmpty(S))
  {
    if(T)
    {
      Push(&S,T);
      T=T->lchild;
    }
    else
    {
      Pop(&S,&T);
      if(!Visit(T->data))
         return ERROR;

         T = T->rchild;
    }
  }
    printf("\n");
    return OK;
  }

Status InOrderTraverse2(BiTree *T,Status(*Visit)(TElemType))
{//中序遍历二叉树T的非递归算法（利用栈），对每个数据元素调用函数visit，

  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);
      if(!Visit(p->data))
        return ERROR;
      Push(&S,p->rchild);
    }
  }
  printf("\n");

  return OK;
}

void PostOrderTraverse(BiTree *T,Status(*Visit)(TElemType))
{//后序递归遍历T,对每个节点调用函数Visit一次

  if(T)
  {
    PostOrderTraverse(T->lchild,Visit);
    PostOrderTraverse(T->rchild,Visit);
    Visit(T->data);
  }
}

void LevelOrderTraverse(BiTree *T,Status (*Visit)(TElemType))
{//层序递归遍历T，利用队列，对每个节点调用函数Visit一次

  LinkQueue *q;
  QElemType a;
  q = (LinkQueue *)malloc(sizeof(struct QNode));


  if(T)
  {
    InitQueue(&q);
    EnQueue(q,T);
    while(!QueueEmpty(q))
    {
      DeQueue(q,&a);
      Visit(a->data);
      if(a->lchild!=NULL)
        EnQueue(q,a->lchild);
      if(a->rchild!=NULL)
        EnQueue(q,a->rchild);
    }
    printf("\n");
  }
  free(q);


}

Status PreOrderN(BiTree *T,Status (*Visit)(TElemType))
{//先序遍历二叉树T非递归算法

  SqStack s;
  BiTree *p;
  InitStack(&s);
  Push(&s,T);//根指针入栈

  while(!StackEmpty(s))
  {
    while(GetTop(s,&p) && p)
    {
      if(!Visit(p->data))
        return ERROR;
      Push(&s,p->lchild);//向左走到尽头

    }
    Pop(&s,&p);//空指针出栈

    if(!StackEmpty(s))
    {
      Pop(&s,&p);
      Push(&s,p->rchild);
    }
  }
}

void PreOrder(BiTree *T,Status(*Visit)(TElemType))
{//先序遍历的递归算法

  if(T)
  {
    Visit(T->data);
    PreOrder(T->lchild,Visit);
    PreOrder(T->rchild,Visit);
  }
}

Status PostOrderN(BiTree *T,Status (*Visit)(TElemType))
{//后序遍历的非递归算法
  SqStack s;
  BiTree *p;
  BiTree *r;
  p = T;
  InitStack(&s);
  Push(&s,T);
  while(!StackEmpty(s))
  {
    while(GetTop(s,&p) && p)
      Push(&s,p->lchild);
    Pop(&s,&p);
    if(!StackEmpty(s))
    {
      GetTop(s,&p);
    if(p->rchild && p->rchild!=r)
    {
      p=p->rchild;
      Push(&s,p);
      p=p->lchild;

    }
    else
    {
      Pop(&s,&p);
      if(!Visit(p->data))
         return ERROR;
      r = p;
      p=NULL;
      Push(&s,p);
    }
    }
  }
}