stepvisit.cpp

数据结构试验中一个有关于非递归算法的源程序

#include <iostream.h>
#include <malloc.h>			
#include <stdio.h>			
#include <stdlib.h>
#define N 50
#define OVERFLOW 0
#define NULL 0

typedef struct BiTNode            //定义线性链表
{
	char data;
	struct BiTNode *lchild;
	struct BiTNode *rchild;		
}*BiTree;		

typedef struct queue            //定义队列结构体
{
	BiTree elem;
	int front;
	int tail;
}queue;

void CreateBiTree(BiTree &T)	//先序扩展序列建立二叉树的递归算法 
{  
	char ch;
	scanf("%c",&ch);
	if (ch=='!') 
	{
		T = NULL;		
	}
	else 
	{ 
		if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))
		{
			exit(OVERFLOW);
		}
		T->data=ch;
		CreateBiTree(T->lchild); 
		CreateBiTree(T->rchild); 
	}  
} 


queue* CreateQueue () 
 {							// 构造一个空队列Q
	queue *q;
	q=(queue *) malloc(sizeof (queue));
	if (!q) exit (OVERFLOW);	
    q->elem = (BiTree) malloc(N*sizeof (struct BiTNode));
    if (!q->elem) exit (OVERFLOW);		              
    q->front = q->tail = 0;
     return q;
 }


BiTree SubQueue(queue *q)
{
	BiTree p;
	p=&(q->elem[q->front]);
	(q->front)++;
	return p;
}


void AddQueue(queue *q,BiTree T)
{
	q->elem[q->tail]=*T;
	q->tail++;
	return;
}


void main()	//层次遍历二叉树的非递归算法的主程序
{
	printf("本程序为层次遍历二叉树的非递归算法的实现程序，请按先序扩展序列输入二叉树，空用@表示：\n");
	queue *q;
    BiTree p;
    BiTree b;		
	CreateBiTree(b);
    printf("\n层次遍历二叉树的结果为：\n");	
	q=CreateQueue();				
	AddQueue(q,b);					
	while(q->front!=q->tail)		
		{
			p=SubQueue(q);
			printf("%c",p->data);
			if(p->lchild) AddQueue(q,p->lchild);
			if(p->rchild) AddQueue(q,p->rchild);
		}
	
	printf("\n");
}