leveltraverse.c

LevelTraverse.c 上次写的“cengxubianlierchashu.rar（二叉树层序遍历程序）”遍历不能将二叉树的所有结点都遍历

/* LevelTraverse.c
说明:本程序用于层序遍历二叉树.程序开始时先由用户先根序输入二叉树各结点值,对于空结点输入宏ENDTAG所对的值(暂定为整数0).
建立好二叉树后即可自动进行遍历依次层序输出各结点的值.
*/

#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<alloc.h>

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

/*-----------------------------------------------------------------------------------*/
/*              								
在此可改变二叉树结点的数据类型,暂定为int,用户可将int改为其他类型,则同时须改%d及0.   	
这几个宏用在visit函数和PreCreateBT函数中.       					
*/
typedef int ElemType;   
#define OUTFORMAT       "%d  ",Node->data   					
#define INFORMAT        "%d",&e     						
#define ENDTAG      	0	
#define PROMPT          "\tNULL:\t%d\n\n",ENDTAG					
/*-----------------------------------------------------------------------------------*/

typedef struct BTNode
{
  ElemType data;
  struct BTNode *lchild,*rchild;
}BTNode;

typedef struct BT
{
  BTNode *root;/*指向根结点*/
  int nNOde;/*二叉树的结点数*/
}BTree;


typedef struct QNode
{
  BTNode data;/*存放二叉数结点*/
  struct QNode *next;
}QNode;

typedef struct
{
  QNode *front,*rear;
}LinkQ;


int EmptyQueue(LinkQ Q)
{
  if(Q.front==Q.rear)
    return TRUE;/*同指向对头结点则表明队列为空*/
  else
    return FALSE;
}

int InitQueue(LinkQ *Q)
{/*首尾指针分配同一块空间，该结点不用*/
  Q->front=Q->rear=(QNode *)malloc(sizeof(QNode));
  if(Q->front==NULL)
    exit(OVERFLOW);
  Q->rear->next=NULL;
  return OK;
}

int EnQueue(LinkQ *Q,BTNode e)
{
  QNode *p;
  p=(QNode *)malloc(sizeof(QNode));
  if(p==NULL)
    exit(OVERFLOW);

  p->data=e;
  Q->rear->next=p;
  Q->rear=p;
  Q->rear->next=NULL;

  return OK;
}

int DeQueue(LinkQ *Q,BTNode *e)
{/*从队列中去掉一个二叉数结点，并用e返回*/
  QNode *p;
  if(EmptyQueue(*Q))
    exit(ERROR);

  p=Q->front->next;
  Q->front->next=p->next;
/*--------------------------------*/
  if(Q->front->next==NULL)
    Q->rear=Q->front;
/*如果出队后，队列为空，则使头尾指针同指向头结点，从而使判空函数才能得出正确判断*/
/*--------------------------------*/
  *e=p->data;
  free(p);

  return OK;
}


int LevelTraverse(BTree BT,void(*visit)(BTNode *Node))
{
  BTNode *p;
  LinkQ Q;

  if(!BT.root)/*空树则退出*/
    exit(ERROR);

  InitQueue(&Q);
  p=BT.root;
  (*visit)(p);
  EnQueue(&Q,*p);
  while(!EmptyQueue(Q))
  {
    DeQueue(&Q,p);
    if(p->lchild)
    {
      visit(p->lchild);
      EnQueue(&Q,*p->lchild);
    }
    if(p->rchild)
    {
      visit(p->rchild);
      EnQueue(&Q,*p->rchild);
    }
  }
  return OK;
}

void visit(BTNode *Node)
{/* 以宏定义中的格式输出结点中Node->data的值 */
  printf(OUTFORMAT);
}

int PreCreateBT(BTNode **Node)
{
  ElemType e;

  scanf(INFORMAT);/* 以宏定义中的格式输入结点的值给e */
  if(e==ENDTAG)
  {
    *Node=NULL;
    return OK;
  }

  *Node=(BTNode *)malloc(sizeof(BTNode));
  if((*Node)==NULL)
    exit(OVERFLOW);

  (*Node)->data=e;
  PreCreateBT(&(*Node)->lchild);
  PreCreateBT(&(*Node)->rchild);

  return OK;
}




void main()
{
  BTree BT;
  clrscr();
  printf(PROMPT);
  printf("PreCreate BTree:\n");
  PreCreateBT(&BT.root);
  printf("LevelTraverse:\n");
  LevelTraverse(BT,visit);
  getch();
}