【数据结构】使用队列解决二叉树问题

1.层序遍历

A先进队列，迭代-》队列不为空，拿出队头的数据然后将队头的左右节点放入队列，不断拿出放入，又队列满足先进先出的特性，无论这棵树多大都能实现层序遍历；

我们这里需要用到队列，可以在我的这篇文章中获取:

【数据结构】队列-CSDN博客

修改一下队列的数据类型

//层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{Queue q;QueueInit(&q);if (root == NULL)return;QueuePush(&q, root);  // 根节点先入队while (!QueueEmpty(&q))  // 队列不为空时循环{BTNode* front = QueueFront(&q);  // 获取队头节点QueuePop(&q);  // 队头节点出队printf("%c ", front->_data);  // 访问节点（打印数据）// 左右子节点入队（如果存在）if (front->_left)QueuePush(&q, front->_left);if (front->_right)QueuePush(&q, front->_right);}QueueDestroy(&q);printf("\n");
}

假设我们有如下二叉树：

        A/ \B   C/ \   \D   E   F

执行流程如下：

1. 初始化队列，将 A 入队 → 队列：[A]

2. 队列非空，取出 A 并打印，将 B、C 入队 → 队列：[B, C]，输出：A

3. 队列非空，取出 B 并打印，将 D、E 入队 → 队列：[C, D, E]，输出：A B

4. 队列非空，取出 C 并打印，将 F 入队 → 队列：[D, E, F]，输出：A B C

5. 队列非空，取出 D 并打印，无子女入队 → 队列：[E, F]，输出：A B C D

6. 队列非空，取出 E 并打印，无子女入队 → 队列：[F]，输出：A B C D E

7. 队列非空，取出 F 并打印，无子女入队 → 队列：[]，输出：A B C D E F

8. 队列为空，循环结束，销毁队列

最终输结果为：A B C D E F ，正好是按层序访问的结果。

2.判断二叉树是否为完全二叉树

遇到NULL就break跳出循环，然后接着判断剩下队列的数据，如果都是空，说明这个是完全二叉树；

//判断二叉树是否为满二叉树
//是返回1，不是返回0
int BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(&q);if (root == NULL)return;QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);if (front == NULL){break;}QueuePush(&q, front->_left);QueuePush(&q, front->_right);}while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);if (front){QueueDestroy(&q);return 0;}}QueueDestroy(&q);return 1;
}

相关文章：

【数据结构】树的概念及结构-CSDN博客

【数据结构】二叉树概念及结构 -CSDN博客

【数据结构】堆-“此堆非比堆”-CSDN博客