二叉树层序遍历

上一篇文章讲了二叉树的递归先序中序后序遍历方式，现在讲讲更加简单的层序遍历

 首先，我们先要知道按层遍历是什么意思，如图，一个这样的二叉树，我们遍历打印应该得出什么结果？显然顾名思义，按层遍历，自然是先A B F C G D E H

 也没有递归那么抽象了，我们讲讲这是怎么做到的。

 1、我们依靠队列来完成这种行为，我们先把树的结构贴出来，和实现代码

typedef struct BINARYNODE {
	char ch;
	struct BINARYNODE* lchild;
	struct BINARYNODE* rchild;
}BinaryNode;

void LevelOrderTraversal(BinaryNode* BT) {
	if (!BT)return;
	queueQ;
	Q.push(BT);				//根结点入栈
	while (Q.empty() == false) {//队列不为空
		BinaryNode* node = Q.front();
		cout << node->ch;
		if (node->lchild != NULL)
			Q.push(node->lchild);
		if (node->rchild != NULL)
			Q.push(node->rchild);
		Q.pop();
	}
}

虽然没有递归那么简洁不过要好理解多了。

首先函数需要接收一个首结点，判断结点是否为空，不为空就继续

创建一个队列，队列的数据类型为结点指针，表示存储结点地址

队列先让首结点入队，也就是A。然后进入循环，循环的条件为列表不为空

循环内创建一个树的结点指针，被赋值为列表的第一个元素，也就是node现在为列表首结点

打印node即A的根，也就是打印A

如果结点的左结点不为空，那么入队，右结点同理，A恰好满足，所以此时Q队列为A B F

pop()移除第列表第一个元素，即Q只剩下B F，进入下一轮循环

队列不为空，node被赋值为B的地址，打印B的根，即打印B

B的左结点为空，所以不入队，又结点入队，即C入队。pop()移除列表第一个元素，Q只剩下F C

队列不为空，继续循环node为队列的第一个元素，即F的地址

打印F的根，即打印F

至此打印了两层，也就是A B F，这个要比递归好理解多了，剩下的就自己想想吧。

 我们把代码发出来，以供运行

#include
#include
using namespace std;

typedef struct BINARYNODE {
	char ch;
	struct BINARYNODE* lchild;
	struct BINARYNODE* rchild;
}BinaryNode;

void LevelOrderTraversal(BinaryNode* BT) {
	if (!BT)return;
	queueQ;
	Q.push(BT);				//根结点入栈
	while (Q.empty() == false) {//队列不为空
		BinaryNode* node = Q.front();
		cout << node->ch;
		if (node->lchild != NULL)
			Q.push(node->lchild);
		if (node->rchild != NULL)
			Q.push(node->rchild);
		Q.pop();
	}
}
void CresteBinaryTree() {
	//创建结点
	BinaryNode node1 = { 'A',NULL,NULL };
	BinaryNode node2 = { 'B',NULL,NULL };
	BinaryNode node3 = { 'C',NULL,NULL };
	BinaryNode node4 = { 'D',NULL,NULL };
	BinaryNode node5 = { 'E',NULL,NULL };
	BinaryNode node6 = { 'F',NULL,NULL };
	BinaryNode node7 = { 'G',NULL,NULL };
	BinaryNode node8 = { 'H',NULL,NULL };

	//建立结点关系
	node1.lchild = &node2;
	node1.rchild = &node6;
	node2.rchild = &node3;
	node3.lchild = &node4;
	node3.rchild = &node5;
	node6.rchild = &node7;
	node7.lchild = &node8;
	LevelOrderTraversal(&node1);
	printf("n");
}

int main() {
	CresteBinaryTree();
}

不能再简单了