数据结构 ——— 层序遍历链式二叉树

链式二叉树示意图编辑

何为层序遍历

手搓一个链式二叉树

实现层序遍历链式二叉树

链式二叉树示意图

何为层序遍历

和前中后序遍历不同，前中后序遍历链式二叉树需要利用递归才能遍历
而层序遍历是非递归的形式，如上图：层序遍历的结果：1，2，4，3，5，6

手搓一个链式二叉树

代码演示（以上图为例）：

// 数据类型
typedef int BTDataType;
 
// 二叉树节点的结构
typedef struct BinaryTreeNode
{
    BTDataType data; //每个节点的数据
 
    struct BinaryTreeNode* left; //指向左子树的指针
 
    struct BinaryTreeNode* right; //指向右子树的指针
}BTNode;
 
// 申请新节点
BTNode* BuyNode(BTDataType x)
{
    BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
 
    // 判断是否申请成功
    if (newnode == NULL)
    {
        perror("malloc fail");
        return NULL;
    }
 
    // 初始化
    newnode->data = x;
    newnode->left = NULL;
    newnode->right = NULL;
 
    return newnode;
}
 
BTNode* CreatBinaryTree()
{
    BTNode* n1 = BuyNode(1);
    assert(n1);
    BTNode* n2 = BuyNode(2);
    assert(n2);
    BTNode* n3 = BuyNode(3);
    assert(n3);
    BTNode* n4 = BuyNode(4);
    assert(n4);
    BTNode* n5 = BuyNode(5);
    assert(n5);
    BTNode* n6 = BuyNode(6);
    assert(n6);
 
    n1->left = n2;
    n1->right = n4;
    n2->left = n3;
    n4->left = n5;
    n4->right = n6;
 
    return n1;
}

实现层序遍历链式二叉树

实现思路：

利用队列的先进先出的性质，实现层序遍历链式二叉树
如上图所示：先将 1 节点入队列，再将 1 节点出队列，在 1 节点出队列的时候，把 2、4 节点带入队列，2 节点再出队列，2 节点出队列的时候，把 3 节点带入队列，然后就是 4 节点出队列，同样出队列的时候，将 5、6 节点带入队列，最后再依次出队列，所有数据出完队列后，根据出队列的顺序，就是层序遍历的顺序

实现前要先构建一个简易队列以及队列的基本函数：

// 数据类型
typedef BTNode* QDataType;

// 链式队列每个节点的结构
typedef struct QueueNode
{
	struct QueueNode* next; //指向下一个节点的指针

	QDataType data; //当前节点的数据
}QNode;

// 链式队列的结构
typedef struct Queue
{
	QNode* phead; //指向队头节点的指针

	QNode* ptail; //指向队尾节点的指针

	int size; //队列的总数据个数
}Queue;

// 初始化队列
void QueueInit(Queue* pq)
{
	assert(pq);

	pq->phead = NULL;
	pq->ptail = NULL;
	pq->size = 0;
}

// 数据入队列
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);

	// 申请新节点
	QNode* newnode = (QNode*)malloc(sizeof(QNode));

	// 判断是否申请成功
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}

	// 初始化新节点
	newnode->data = x;
	newnode->next = NULL;

	if (pq->phead == NULL) //当队列中没有数据的情况
	{
		// 双重判断，更加保险
		assert(pq->ptail == NULL);

		// 头尾都指向新节点即可
		pq->phead = newnode;
		pq->ptail = newnode;
	}
	else //当队列已有数据的情况
	{
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}

	pq->size++;
}

// 数据出队列
void QueuePop(Queue* pq)
{
	assert(pq);

	// 当队列中没有数据的情况
	if (pq->phead == NULL)
	{
		perror(pq->phead);
		return;
	}

	if (pq->phead->next == NULL) //当队列中只有一个数据的情况
	{
		free(pq->phead);
		
		pq->phead = NULL;
		pq->ptail = NULL;
	}
	else //当队列中有多个数据的情况
	{
		QNode* next = pq->phead->next;
		free(pq->phead);
		pq->phead = next;
	}

	pq->size--;
}

// 访问队头数据
QDataType QueueFront(Queue* pq)
{
	assert(pq);

	// 当队列中没有数据的情况
	if (pq->phead == NULL)
	{
		perror(pq->phead);
		return -1;
	}

	return pq->phead->data;
}

// 判断队列是否为空
bool QueueEmpty(Queue* pq)
{
	assert(pq);

	return (pq->phead == NULL) && (pq->ptail == NULL);
}

// 释放队列
void QueueDestroy(Queue* pq)
{
	assert(pq);

	QNode* cur = pq->phead;

	while (cur != NULL)
	{
		QNode* next = cur->next;

		free(cur);

		cur = next;
	}

	pq->phead = NULL;
	pq->ptail = NULL;
	pq->size = 0;
}

在定义队列数据时，需要定义链式二叉树节点的指针，这样才能找到二叉树节点的左右子树

代码实现：

void LevelOrder(BTNode* root)
{
	// 定义队列
	Queue q;
	// 初始化队列
	QueueInit(&q);

	// 先将二叉树的根节点的指针入队列
	if (root != NULL)
		QueuePush(&q, root);

	while (!QueueEmpty(&q))
	{
		// 访问队头数据
		BTNode* front = QueueFront(&q);
		printf("%d ", front->data);

		// 队头数据出队列
		QueuePop(&q);

		if (front->left)
			QueuePush(&q, front->left);

		if (front->right)
			QueuePush(&q, front->right);
	}
	printf("\n");
}

代码解析：

当队列为空时，链式二叉树的层序遍历就实现了
但最开始队列没有数据，所以要先将指向根节点的指针存放入队列
且存放节点指针是为了方便查找左右子树
然后在利用 while 循环，只要队列不为空，就循环下去
先访问队头的数据，队头的数据就是链式二叉树节点的指针
所以使用 BTNode* front 来接收，再利用 printf 函数打印指针所指向节点中的数据
再把队头数据出队列，并且把出队列那个节点的左右子树存放入队列
注意为空时就不要放入队列，所以每次放入队列前要判断是否为空
直到队列为空时，也就是不满足 while 循环时，层序遍历就实现了

此代码的关键是利用 BTNode* front 接收每次要出队列的节点指针，这样就方便查找当前节点的左右子树，并且利用 BTNode* front 接收从而替代了递归逻辑

代码验证：