用队列实现二叉树的层次遍历算法
时间: 2023-10-20 18:07:14 浏览: 89
二叉树的层次遍历算法可以使用队列来实现,具体步骤如下:
1. 将二叉树的根节点入队。
2. 当队列不为空时,执行以下操作:
- 弹出队头元素,并访问该节点。
- 如果该节点有左子节点,则将左子节点入队。
- 如果该节点有右子节点,则将右子节点入队。
3. 重复步骤2,直到队列为空。
这样就可以按照层次顺序遍历二叉树了。下面是C++代码实现:
```c++
void levelOrderTraversal(TreeNode* root) {
if (root == nullptr) return;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode* node = q.front();
q.pop();
// 访问节点
cout << node->val << " ";
if (node->left != nullptr) q.push(node->left);
if (node->right != nullptr) q.push(node->right);
}
}
```
相关问题
用栈实现二叉树层次遍历算法
二叉树的层次遍历需要用到队列,而不是栈。在队列中存储每个节点,依次将每个节点的左右子节点入队,直到队列为空。
以下是用队列实现层次遍历的代码:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def levelOrder(root: TreeNode):
if not root:
return []
queue = [root]
result = []
while queue:
level_length = len(queue)
level = []
for i in range(level_length):
node = queue.pop(0)
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level)
return result
```
如果一定要使用栈实现,可以考虑使用两个栈,一个存储当前层的节点,一个存储下一层的节点,每次遍历完当前层后将下一层节点栈中的元素倒序压入当前层节点栈中。不过这种实现方式比较复杂,效率不如队列实现。
二叉树层次遍历算法代码实现c语言
以下是C语言实现二叉树层次遍历算法的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 二叉树结点结构体
typedef struct node {
int data; // 结点数据
struct node *left; // 左子树结点指针
struct node *right; // 右子树结点指针
} Node, *Tree;
// 队列结构体
typedef struct queue {
Tree data; // 队列元素数据
struct queue *next; // 下一个队列元素指针
} Queue, *Stack;
// 初始化队列
void initQueue(Queue **queue) {
*queue = (Queue *) malloc(sizeof(Queue));
(*queue)->next = NULL;
}
// 判断队列是否为空
int isQueueEmpty(Queue *queue) {
return (queue->next == NULL);
}
// 入队
void enqueue(Queue *queue, Tree data) {
Queue *newNode = (Queue *) malloc(sizeof(Queue));
newNode->data = data;
newNode->next = NULL;
Queue *p = queue;
while (p->next != NULL) {
p = p->next;
}
p->next = newNode;
}
// 出队
Tree dequeue(Queue *queue) {
Queue *p = queue->next;
Tree data = p->data;
queue->next = p->next;
free(p);
return data;
}
// 二叉树层次遍历
void levelOrderTraversal(Tree tree) {
if (!tree) {
return;
}
Queue *queue;
initQueue(&queue);
enqueue(queue, tree);
while (!isQueueEmpty(queue)) {
Tree node = dequeue(queue);
printf("%d ", node->data);
if (node->left) {
enqueue(queue, node->left);
}
if (node->right) {
enqueue(queue, node->right);
}
}
}
// 测试代码
int main() {
// 构造二叉树
Tree tree = (Tree) malloc(sizeof(Node));
tree->data = 1;
tree->left = (Tree) malloc(sizeof(Node));
tree->left->data = 2;
tree->left->left = NULL;
tree->left->right = NULL;
tree->right = (Tree) malloc(sizeof(Node));
tree->right->data = 3;
tree->right->left = NULL;
tree->right->right = NULL;
tree->left->left = (Tree) malloc(sizeof(Node));
tree->left->left->data = 4;
tree->left->left->left = NULL;
tree->left->left->right = NULL;
tree->right->right = (Tree) malloc(sizeof(Node));
tree->right->right->data = 5;
tree->right->right->left = NULL;
tree->right->right->right = NULL;
// 层次遍历
levelOrderTraversal(tree);
return 0;
}
```
以上是一个基于队列实现的二叉树层次遍历算法的 C 语言示例代码。在该示例代码中,主要包括了初始化队列、判断队列是否为空、入队、出队等队列操作函数,以及二叉树层次遍历函数 levelOrderTraversal。在 levelOrderTraversal 函数中,我们首先将根节点入队,然后进行循环遍历,每次出队一个结点,并将该结点的左右子树入队,直到队列为空为止,期间找到的各个结点就是二叉树的层次遍历结果。