二叉树的层序遍历

• 一、树的层序遍历
• • 1.结构体
  • 2.初始化队列
  • 3.入队
  • 4.出队
  • 5.判空
  • 6.建立结点
  • 7.结点上树
  • 8.层序遍历
  • 9.完整代码
  • 10.运行结果
• 三、总结

typedef struct BTNode 
{
	char element;
	BTNode* left;
	BTNode* right;
}BTNode, * BTNodePtr;


typedef struct BTNodePtrQueue 
{
	BTNodePtr* nodePtrs;
	int front;
	int rear;
}BTNodePtrQueue, * QueuePtr;

树的层序遍历需要借助队列，因此我们这里需要定义一个队列结构体。

QueuePtr initQueue()
{
	QueuePtr resultQueuePtr = new struct BTNodePtrQueue;

	resultQueuePtr->nodePtrs = new BTNodePtr[QUEUE_SIZE];

	resultQueuePtr->front = 0;
	resultQueuePtr->rear = 1;

	return resultQueuePtr;
}

void enqueue(QueuePtr paraQueuePtr, BTNodePtr paraBTNodePtr) 
{
	

	if ((paraQueuePtr->rear + 1) % QUEUE_SIZE == paraQueuePtr->front % QUEUE_SIZE) 
	{
		printf("Error, trying to enqueue %c. queue full.n", paraBTNodePtr->element);
		return;
	}
	paraQueuePtr->nodePtrs[paraQueuePtr->rear] = paraBTNodePtr;
	paraQueuePtr->rear = (paraQueuePtr->rear + 1) % QUEUE_SIZE;

	
}

BTNodePtr dequeue(QueuePtr paraQueuePtr) 
{
	if (isQueueEmpty(paraQueuePtr)) 
	{
		cout << "Error, empty queue" << endl;
		return NULL;
	}

	paraQueuePtr->front = (paraQueuePtr->front + 1) % QUEUE_SIZE;

	//printf("dequeue %c ends.rn", paraQueuePtr->nodePtrs[paraQueuePtr->front]->element);

	return paraQueuePtr->nodePtrs[paraQueuePtr->front];
}

bool isQueueEmpty(QueuePtr paraQueuePtr) 
{
	if ((paraQueuePtr->front + 1) % QUEUE_SIZE == paraQueuePtr->rear) 
		return true;

	return false;
}

BTNodePtr constructBTNode(char paraChar) 
{
	BTNodePtr resultPtr = new BTNode;
	resultPtr->element = paraChar;
	resultPtr->left = NULL;
	resultPtr->right = NULL;
	return resultPtr;
}

BTNodePtr stringToBTree(char* paraString)
{
	int i = 0;
	char ch;

	//用队列去管理指针
	QueuePtr tempQueuePtr = initQueue();

	BTNodePtr resultHeader;
	BTNodePtr tempParent, tempLeftChild, tempRightChild;

	//先入队一个
	ch = paraString[i];

	resultHeader = constructBTNode(ch);

	enqueue(tempQueuePtr, resultHeader);

	//对后续结点入队
	while (!isQueueEmpty(tempQueuePtr))
	{
		tempParent = dequeue(tempQueuePtr);

		//先处理左子结点
		i++;
		ch = paraString[i];

		if (ch == '#')
		{
			tempParent->left = NULL;
		}else{

			tempLeftChild = constructBTNode(ch);
			enqueue(tempQueuePtr, tempLeftChild);
			tempParent->left = tempLeftChild;
		}


		//再处理右子结点
		i++;
		ch = paraString[i];
		if (ch == '#')
		{
			tempParent->right = NULL;
		}
		else {

			tempLeftChild = constructBTNode(ch);
			enqueue(tempQueuePtr, tempLeftChild);
			tempParent->right = tempLeftChild;
		}
	}

	return resultHeader;
}

这里的‘#’表示为空。后面给出“acde#bf######”测试样例，构造出的树如下

//层次遍历
void levelwise(BTNodePtr paraTreePtr)
{
	char tempString[100];
	int i = 0;

	QueuePtr tempQueuePtr = initQueue();

	BTNodePtr tempNodePtr;
	
	//根结点先入队
	enqueue(tempQueuePtr, paraTreePtr);
	
	//对后续结点进行处理
	while (!isQueueEmpty(tempQueuePtr))
	{
		tempNodePtr = dequeue(tempQueuePtr);

		//准备输出,取出父结点
		tempString[i] = tempNodePtr->element;
		i++;
		
		//孩子结点入队
		if (tempNodePtr->left != NULL)
			enqueue(tempQueuePtr, tempNodePtr->left);
		if(tempNodePtr->right != NULL)
			enqueue(tempQueuePtr, tempNodePtr->right);
	}

	tempString[i] = '';
	
	printf("层次遍历结果: %sn", tempString);
}

先让根结点入队

如果后续还有结点，那么父结点出队，其子结点 如果不为空那么都入队。

把出队的元素放入一个字符串里面存储起来；继续遍历出队，遵循“父结点出队，其子节点入队”的规律。最后输出字符串，也就是层序遍历的结果。

#include 
#include 

#define QUEUE_SIZE 5

using namespace std;


typedef struct BTNode 
{
	char element;
	BTNode* left;
	BTNode* right;
}BTNode, * BTNodePtr;


typedef struct BTNodePtrQueue 
{
	BTNodePtr* nodePtrs;
	int front;
	int rear;
}BTNodePtrQueue, * QueuePtr;


QueuePtr initQueue()
{
	QueuePtr resultQueuePtr = new struct BTNodePtrQueue;

	resultQueuePtr->nodePtrs = new BTNodePtr[QUEUE_SIZE];

	resultQueuePtr->front = 0;
	resultQueuePtr->rear = 1;

	return resultQueuePtr;
}


void enqueue(QueuePtr paraQueuePtr, BTNodePtr paraBTNodePtr) 
{
	

	if ((paraQueuePtr->rear + 1) % QUEUE_SIZE == paraQueuePtr->front % QUEUE_SIZE) 
	{
		printf("Error, trying to enqueue %c. queue full.n", paraBTNodePtr->element);
		return;
	}
	paraQueuePtr->nodePtrs[paraQueuePtr->rear] = paraBTNodePtr;
	paraQueuePtr->rear = (paraQueuePtr->rear + 1) % QUEUE_SIZE;

	
}


bool isQueueEmpty(QueuePtr paraQueuePtr) 
{
	if ((paraQueuePtr->front + 1) % QUEUE_SIZE == paraQueuePtr->rear) 
		return true;

	return false;
}


BTNodePtr dequeue(QueuePtr paraQueuePtr) 
{
	if (isQueueEmpty(paraQueuePtr)) 
	{
		cout << "Error, empty queue" << endl;
		return NULL;
	}

	paraQueuePtr->front = (paraQueuePtr->front + 1) % QUEUE_SIZE;

	//printf("dequeue %c ends.rn", paraQueuePtr->nodePtrs[paraQueuePtr->front]->element);

	return paraQueuePtr->nodePtrs[paraQueuePtr->front];
}


BTNodePtr constructBTNode(char paraChar) 
{
	BTNodePtr resultPtr = new BTNode;
	resultPtr->element = paraChar;
	resultPtr->left = NULL;
	resultPtr->right = NULL;
	return resultPtr;
}

BTNodePtr stringToBTree(char* paraString)
{
	int i = 0;
	char ch;

	//用队列去管理指针
	QueuePtr tempQueuePtr = initQueue();

	BTNodePtr resultHeader;
	BTNodePtr tempParent, tempLeftChild, tempRightChild;

	//先入队一个
	ch = paraString[i];

	resultHeader = constructBTNode(ch);

	enqueue(tempQueuePtr, resultHeader);

	//对后续结点入队
	while (!isQueueEmpty(tempQueuePtr))
	{
		tempParent = dequeue(tempQueuePtr);

		//先处理左子结点
		i++;
		ch = paraString[i];

		if (ch == '#')
		{
			tempParent->left = NULL;
		}else{

			tempLeftChild = constructBTNode(ch);
			enqueue(tempQueuePtr, tempLeftChild);
			tempParent->left = tempLeftChild;
		}

		//再处理右子结点
		i++;
		ch = paraString[i];
		if (ch == '#')
		{
			tempParent->right = NULL;
		}
		else {

			tempLeftChild = constructBTNode(ch);
			enqueue(tempQueuePtr, tempLeftChild);
			tempParent->right = tempLeftChild;
		}
	}

	return resultHeader;
}

//层次遍历
void levelwise(BTNodePtr paraTreePtr)
{
	char tempString[100];
	int i = 0;

	QueuePtr tempQueuePtr = initQueue();

	BTNodePtr tempNodePtr;

	enqueue(tempQueuePtr, paraTreePtr);

	while (!isQueueEmpty(tempQueuePtr))
	{
		tempNodePtr = dequeue(tempQueuePtr);

		//准备输出,取出父结点
		tempString[i] = tempNodePtr->element;
		i++;
		
		//孩子结点入队
		if (tempNodePtr->left != NULL)
			enqueue(tempQueuePtr, tempNodePtr->left);
		if(tempNodePtr->right != NULL)
			enqueue(tempQueuePtr, tempNodePtr->right);
	}

	tempString[i] = '';
	
	printf("层次遍历结果: %sn", tempString);
}


int main() 
{
	BTNodePtr tempHeader;
	tempHeader = constructBTNode('c');
	printf("There is only one node. Preorder visit: ");
	char tempString[15] = "acde#bf######";

	tempHeader = stringToBTree(tempString);
	printf("层次遍历的结果: ");
	levelwise(tempHeader);
	printf("rn");

	system("pause");
	return 0;
}

二叉树借助队列进行一个层次遍历是一个很好玩的应用，这表明单一的数据结构要和其他结构结合起来才能实现更多有趣的功能。这里的队列长度应该开大一点的，避免溢出。我这里的开得小，是为了能看到报错信息，不信开长度为4的试试。