数据结构 - 二叉树的广度优先遍历算法（C++）

#include <iostream>

#define _OK 1
#define _ERROR 0

using namespace std;

// Define node element type in binary tree.
typedef char Element;

// Binary tree.
typedef struct BTNode
{
	Element data;
	BTNode *lChild,*rChild; // Define left,right subtree.
} BTNode, *BTree;

// Define node element type in queue. (The node element type in queue is the pointer to binary tree node)
typedef BTNode *QElementType;
typedef int status;

// --------------------------------------------------------------------
// We need use queue to perform level traverse. So, define queue first.
typedef struct QNode
{
	QElementType data;
	QNode *next;
} QNode, *QueuePtr;

// Definition of queue.
typedef struct
{
	QueuePtr front;
	QueuePtr rear;
} LinkQueue;

status InitQueue(LinkQueue &Q)
{
	Q.front = NULL;
	Q.rear = NULL;
	return _OK;
}

bool IsEmpty(LinkQueue Q)
{
	return Q.front == NULL;
}

status EnQueue(LinkQueue &Q, QElementType e)
{
	// Construct queue node.
	QNode *ptrNode = (QNode*) malloc(sizeof(QNode));
	if(!ptrNode)
	{
		return _ERROR;
	}

	ptrNode->data=e;
	ptrNode->next=NULL;
	if(IsEmpty(Q))
	{
		Q.front=Q.rear=ptrNode;
		return _OK;
	}

	Q.rear->next=ptrNode;
	Q.rear = ptrNode;
	return _OK;
}

status DeQueue(LinkQueue &Q, QElementType &e)
{
	if(IsEmpty(Q))
	{
		return _ERROR;
	}

	QNode *tempPtr = Q.front;
	e = tempPtr->data;
	Q.front = tempPtr->next;
	free(tempPtr);
	return _OK;
}

// ------------------------------------------
int CreateBTree(BTree &T)
{
	char ch;
	cout << "Please input a character:" << endl;
	cin >> ch;
	if(ch=='#')
	{
		T = NULL;
	}
	else
	{
		// Allocate memory for new node.
		if(!(T = (BTNode*)malloc(sizeof(BTNode))))
		{
			return 0; // Allocation fails.
		}

		T->data = ch;

		// Create left subtree.
		CreateBTree(T->lChild);

		// Create right subtree.
		CreateBTree(T->rChild);
	}

	return 1;
}

void VisitBTNode(BTNode *BT)
{
	cout << BT->data << endl;
}

void VisitQNode(QNode *Q)
{
	VisitBTNode(Q->data);
}

void LevelTraverse(BTree T)
{
	QElementType e;
	LinkQueue Q;
	InitQueue(Q);
	EnQueue(Q,T);
	while (!IsEmpty(Q))
	{
		VisitQNode(Q.front);
		if(Q.front->data->lChild!=NULL)
		{
			EnQueue(Q,Q.front->data->lChild);
		}
		if(Q.front->data->rChild!=NULL)
		{
			EnQueue(Q,Q.front->data->rChild);
		}
		DeQueue(Q,e);
	}
}

// ------------------------------------------
void main()
{
	BTree T;
	CreateBTree(T);
	LevelTraverse(T);
}

// Output:
/*
Please input a character:
6
Please input a character:
g
Please input a character:
#
Please input a character:
7
Please input a character:
f
Please input a character:
g
Please input a character:
8
Please input a character:
9
Please input a character:
#
Please input a character:
$
Please input a character:
#
Please input a character:
#
Please input a character:
#
Please input a character:
#
Please input a character:
c
Please input a character:
#
Please input a character:
#
Please input a character:
#
Please input a character:
#
6
g
7
f
g
c
8
9
$
*/