层次非递归遍历.cpp

来自「数据结构中的常见算法」· C++ 代码 · 共 33 行

//层次的非递归算法
#include <stdio.h>
#include <stdlib.h>
#include"建立树.h"
#define MAX 20
void LevleOrder(BiTree T)/*层次遍历二叉树T，从第一层开始，每层从左到右*/
{
	BiTree Queue[MAX],b; /*用一维数组表示队列，front和rear分别表示队首和队尾指针*/
	int front,rear;
	front=rear=0;
	if (T) /*若树非空*/
	{
		Queue[rear++]=T;           /*根结点入队列*/
		while (front!=rear)//当队列非空，
		{  
			b=Queue[front++];       //队首元素出队列，并访问这个结点
			printf("%c",b->data);
			if (b->lchild!=NULL) Queue[rear++]=b->lchild; /*左子树非空，则入队列*/
			if (b->rchild!=NULL) Queue[rear++]=b->rchild; /*右子树非空，则入队列*/
		}
	}
}//LevelOrder

void main()
{
  BiTree T;
  printf("请输入建树字符序列,以“.”表示NULL:\n");
  CreateBiTree(T);  /*建立一棵二叉树T*/
  printf("\n层次遍历二叉树的结果:\n");
  LevleOrder(T);     /*层次遍历二叉树*/
}