二叉树层序遍历用队列
时间: 2023-12-24 17:23:04 浏览: 87
二叉树的层序遍历可以使用队列来实现。具体步骤如下:
1. 首先,创建一个空队列,并将根节点入队。
2. 进入循环,直到队列为空:
a. 从队列中取出一个节点,并输出该节点的值。
b. 若该节点有左孩子,则将左孩子入队。
c. 若该节点有右孩子,则将右孩子入队。
3. 完成循环后,即可完成二叉树的层序遍历。
相关问题
二叉树层序遍历python
二叉树的层序遍历是一种广度优先搜索(BFS)的方法,它按照从上到下、从左到右的顺序逐层遍历二叉树的节点。下面是一个用Python实现二叉树层序遍历的示例代码:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def levelOrder(root):
if not root:
return []
result = []
queue = [root]
while queue:
level = []
size = len(queue)
for _ in range(size):
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
```
在这个示例代码中,我们定义了一个`TreeNode`类来表示二叉树的节点。`levelOrder`函数接受一个二叉树的根节点作为输入,并返回一个二维列表,其中每个子列表表示二叉树的一层。
在函数内部,我们使用一个队列`queue`来辅助进行层序遍历。首先将根节点加入队列中,然后进入循环,直到队列为空。在每一轮循环中,我们先记录当前队列的大小`size`,然后依次从队列中取出`size`个节点,并将它们的值加入到当前层的列表`level`中。同时,如果节点有左子节点或右子节点,我们将它们加入队列中。最后,将当前层的列表`level`加入到结果列表`result`中。
这样,当循环结束后,我们就得到了二叉树的层序遍历结果。
C语言二叉树层序遍历
C语言中二叉树的层序遍历是一种广度优先搜索算法,它按照从上到下、从左到右的顺序遍历二叉树的每个节点。具体实现可以使用队列来辅助实现。具体步骤如下:
1. 首先将根节点入队。
2. 当队列不为空时,取出队首元素,输出该节点的值,并将其左右子节点(如果有)入队。
3. 重复步骤2,直到队列为空。
下面是一个示例代码,其中levelwise函数实现了二叉树的层序遍历:
```
void levelwise(BTnodePtr root) {
if (root == NULL) {
return;
}
QueuePtr queue = (QueuePtr)malloc(sizeof(struct BTNodePtrQueue));
queue->nodePtrs = (BTnodePtr*)malloc(sizeof(BTnodePtr) * MAX_QUEUE_SIZE);
queue->front = 0;
queue->rear = -1;
enqueue(queue, root);
while (!isEmpty(queue)) {
BTnodePtr node = dequeue(queue);
printf("%c ", node->element);
if (node->left != NULL) {
enqueue(queue, node->left);
}
if (node->right != NULL) {
enqueue(queue, node->right);
}
}
free(queue->nodePtrs);
free(queue);
}
```
阅读全文