9.cpp

层次的非递归算法

#include"stdio.h"
#include"malloc.h"

#define TRUE    1
#define FALSE	0

typedef struct tag_BiTNode
{
	char ch;
	struct tag_BiTNode *pLeftChild, *pRightChild;

}BiTNode_S, *BiTree;

typedef struct QNode{
	BiTree  data;
	struct QNode *next;
}QNode,*QueuePtr;

typedef struct {
	QueuePtr front;//队头指针
	QueuePtr rear;//队尾指针
}LinkQueue;

int InitQueue(LinkQueue  &Q);
int EnQueue(LinkQueue  &Q,BiTree e);
BiTree  DeQueue(LinkQueue  &Q,BiTree &e);
int QueueEmpty(LinkQueue  Q);

int PreOrderCreateBiTree( BiTree *pBiTree );
int LevelTraverse( BiTree T );
void main()
{
	BiTree pBiTree;

	printf( "\n pls input the tree: " );
	PreOrderCreateBiTree( &pBiTree );

	printf( "\n The result : ");
	LevelTraverse(pBiTree);


}
int InitQueue(LinkQueue  &Q)
{
  Q.front=Q.rear=(QueuePtr) malloc(sizeof(QNode));
  if(!Q.front)
	  return  0;
  Q.front->next=NULL;
  return 1;
}
int EnQueue(LinkQueue  &Q,BiTree e)
{
  QueuePtr  p;
  p=(QueuePtr) malloc(sizeof(QNode));
  if(!p)
     return 0;
  p->data=e; p->next=NULL;
  Q.rear->next=p;
  Q.rear=p;
  return 1;
}
BiTree DeQueue(LinkQueue  &Q,BiTree &e)
{
  QueuePtr  p;
  //if(Q.front==Q.rear)
	 
  p=Q.front->next;
  e=p->data;
  Q.front->next=p->next;
  if(Q.rear==p)
	  Q.rear=Q.front;
  free(p);
  return e;
}
int QueueEmpty(LinkQueue  Q)
{
  if(Q.front==Q.rear)
	  return 1;
  else
	  return 0;
}
int PreOrderCreateBiTree( BiTree *pBiTree )
{
	char t;

	scanf( "%c", &t);
	if( t == '*' )
	{
		*pBiTree = NULL;
		return TRUE;
	}
	else
	{
		*pBiTree = ( BiTree )malloc( sizeof( BiTNode_S ));
		if( !(*pBiTree) )
		{
			return FALSE;
		}

		(*pBiTree)->ch = t;
        
		if( PreOrderCreateBiTree( &((*pBiTree)->pLeftChild )) == TRUE )
		{
			if( PreOrderCreateBiTree( &((*pBiTree)->pRightChild)) == TRUE )
			{
				return TRUE;
			}
		}
		return FALSE;
	}
}
int LevelTraverse( BiTree T )
{
	LinkQueue  Q;
	BiTree p;
    InitQueue( Q );		// 初始化一个队列
	if( T )
	{
		EnQueue(Q, T );		// 入队列
	}
	while( !QueueEmpty(Q))
	{
		p = DeQueue(Q, T );	// 出队列
	    
		printf(" %c ",p->ch);	// 访问
	
        if( p->pLeftChild )
		{	
			EnQueue( Q,p->pLeftChild );	//左孩子入队列	
		}
		if( p->pRightChild )
		{
			EnQueue( Q,p->pRightChild );	// 右孩子入队列
		}
	}
	return 1;
}