//按层遍历二叉树T,依次输出其每一层结点的值
时间: 2023-12-15 10:06:59 浏览: 38
可以使用队列来实现按层遍历二叉树。具体步骤如下:
1. 将根节点入队。
2. 当队列不为空时,开始遍历:
a. 获取当前队列的大小,即当前层的节点数。
b. 依次取出队列中的节点,输出节点的值,并将其非空子节点加入队列。
3. 遍历完成后,即可输出每一层结点的值。
下面是该算法的 C++ 代码实现:
```c++
void levelOrderTraversal(TreeNode* root) {
if (root == nullptr) return;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
TreeNode* curr = q.front();
q.pop();
cout << curr->val << " ";
if (curr->left) q.push(curr->left);
if (curr->right) q.push(curr->right);
}
cout << endl;
}
}
```
其中,TreeNode 为二叉树节点的定义。
相关问题
用按层次顺序遍历二叉树的方法,统计树中度为1的结点数目
可以使用层次遍历的方法,从根节点开始,依次遍历每一层的节点,统计每一层中度为1的节点数目,最后累加得到整个树中度为1的节点数目。
具体实现方法如下:
1. 定义一个队列,将根节点入队。
2. 循环执行以下步骤,直到队列为空:
a. 取出队首节点,统计其度数。
b. 如果该节点的左子节点不为空,将左子节点入队。
c. 如果该节点的右子节点不为空,将右子节点入队。
3. 统计每一层中度为1的节点数目,累加得到整个树中度为1的节点数目。
代码实现如下:
```python
def count_degree_one(root):
if not root:
return
queue = [root]
count =
while queue:
size = len(queue)
level_count =
for i in range(size):
node = queue.pop()
if node.left:
queue.append(node.left)
level_count += 1
if node.right:
queue.append(node.right)
level_count += 1
count += level_count
return count
```
其中,变量`count`用于累加整个树中度为1的节点数目,变量`level_count`用于统计每一层中度为1的节点数目。在每一层遍历结束后,将`level_count`累加到`count`中。最后返回`count`即可。
用按层次顺序遍历二叉树的方法,统计树中具有度为1的结点数目daima
以下是用Java语言实现的按层次顺序遍历二叉树,并统计具有度为1的节点数目的代码:
```java
public int countDegreeOneNodes(TreeNode root) {
if (root == null) {
return 0;
}
int count = 0;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if (node.left == null && node.right != null) { // 只有右子节点
count++;
} else if (node.left != null && node.right == null) { // 只有左子节点
count++;
}
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
return count;
}
```
该方法使用一个队列来存储每一层的节点,并依次出队并处理每个节点。具体处理方法是,如果一个节点只有左子节点或只有右子节点,则该节点的度为1,累加器count加1。最后返回累加器的值即可。