层序遍历二叉树的代码
时间: 2024-06-11 16:03:00 浏览: 10
层序遍历二叉树是一种广度优先搜索的算法,其过程如下:
1. 首先将根节点入队列
2. 当队列不为空时,取出队列的头部元素,并输出该节点的值
3. 如果该节点有左子节点,则将左子节点入队列
4. 如果该节点有右子节点,则将右子节点入队列
5. 重复步骤2-4,直到队列为空
下面是一份示例代码:
```
void levelOrderTraversal(TreeNode* root) {
if (root == nullptr) {
return;
}
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode* cur = q.front();
q.pop();
cout << cur->val << " ";
if (cur->left != nullptr) {
q.push(cur->left);
}
if (cur->right != nullptr) {
q.push(cur->right);
}
}
}
```
相关问题
c++实现层序遍历二叉树
层序遍历二叉树可以使用队列实现,具体步骤如下:
1. 首先将根节点入队列。
2. 随后,从队列中取出一个节点,访问该节点。
3. 将该节点的左右子节点(如果有的话)入队列。
4. 重复步骤 2 和 3,直到队列为空。
下面是使用 C 代码实现层序遍历二叉树的示例:
```c
// 层序遍历二叉树
void levelOrderTraversal(Node* root) {
if (root == NULL) {
return;
}
// 创建一个队列,并将根节点入队列
Queue* queue = createQueue();
enqueue(queue, root);
// 循环处理队列中的节点,直到队列为空
while (!isEmpty(queue)) {
// 取出队头节点,并访问该节点
Node* node = dequeue(queue);
printf("%d ", node->val);
// 将左右子节点入队列(如果有的话)
if (node->left != NULL) {
enqueue(queue, node->left);
}
if (node->right != NULL) {
enqueue(queue, node->right);
}
}
// 销毁队列
destroyQueue(queue);
}
```
需要注意的一点是,这里的队列和节点都需要自己实现数据结构。
python层序遍历二叉树
在Python中,层序遍历(也称为广度优先遍历)二叉树是一种按层次顺序访问节点的方法,从根节点开始,逐层向下遍历。这种遍历方式通常使用队列来辅助实现,因为队列的特点是先进先出(FIFO),非常适合用来处理需要按照顺序访问同一层级节点的情况。
以下是层序遍历二叉树的基本步骤:
1. 如果二叉树为空,则直接结束遍历。
2. 创建一个空的队列,并将根节点(如果存在)入队。
3. 当队列不为空时,执行以下操作:
a. 弹出队首元素(当前层的第一个节点)并访问它。
b. 将该节点的左右子节点(如果存在)分别入队,以便后续访问。
4. 重复步骤3,直到队列为空。
以下是一个简单的Python代码实现:
```python
from collections import deque
class Node:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def level_order_traversal(root):
if root is None:
return []
queue = deque([root]) # 使用双端队列存储节点
result = []
while queue:
level_nodes = [] # 用于存放当前层的节点值
size = len(queue)
for _ in range(size):
node = queue.popleft() # 弹出队首节点
level_nodes.append(node.value)
if node.left: # 如果有左子节点,入队
queue.append(node.left)
if node.right: # 如果有右子节点,入队
queue.append(node.right)
result.append(level_nodes) # 将当前层节点值添加到结果列表
return result
# 示例
# 假设我们有如下二叉树
# 1
# / \
# 2 3
# / \ \
# 4 5 6
root = Node(1, Node(2, Node(4), Node(5)), Node(3, Node(6)))
print(level_order_traversal(root)) # 输出: [, [2, 3], [4, 5, 6]]
```
相关推荐
![txt](https://img-home.csdnimg.cn/images/20210720083642.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)