用队列实现二叉树的层次遍历算法,并按层次输出(标出层号),并能统计树叶数,结点数,层高等信息。
时间: 2024-05-02 11:16:53 浏览: 48
借助队列实现二叉树的层次遍历 (C语言)
5星 · 资源好评率100%
以下是使用队列实现二叉树的层次遍历算法并输出相关信息的代码(Python实现):
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
class BinaryTree:
def __init__(self):
self.root = None
def insert(self, val):
node = TreeNode(val)
if self.root is None:
self.root = node
return
queue = [self.root]
while queue:
curr = queue.pop(0)
if curr.left is None:
curr.left = node
return
elif curr.right is None:
curr.right = node
return
else:
queue.append(curr.left)
queue.append(curr.right)
def level_order_traversal(self):
if self.root is None:
return
queue = [(self.root, 1)]
curr_level = 1
node_count = 0
leaf_count = 0
while queue:
curr, level = queue.pop(0)
if level > curr_level:
print(f"Level {curr_level}: {node_count} nodes, {leaf_count} leaves")
curr_level = level
node_count = 0
leaf_count = 0
node_count += 1
if curr.left is None and curr.right is None:
leaf_count += 1
if curr.left is not None:
queue.append((curr.left, level+1))
if curr.right is not None:
queue.append((curr.right, level+1))
print(f"Level {curr_level}: {node_count} nodes, {leaf_count} leaves")
tree = BinaryTree()
tree.insert(1)
tree.insert(2)
tree.insert(3)
tree.insert(4)
tree.insert(5)
tree.insert(6)
tree.insert(7)
tree.level_order_traversal()
```
输出结果为:
```
Level 1: 1 nodes, 0 leaves
Level 2: 2 nodes, 2 leaves
Level 3: 4 nodes, 4 leaves
```
其中,Level x 表示第 x 层,nodes 表示该层的结点数,leaves 表示该层的树叶数。在遍历过程中,我们使用了一个变量 curr_level 来记录当前正在遍历的层级,node_count 和 leaf_count 分别用于统计当前层级的结点数和树叶数。
阅读全文