以二叉链表作为二叉树的存储结构,编写用层次顺序遍历二叉树的方法,统计树中度为1 的结点个数。
时间: 2023-06-14 18:06:38 浏览: 79
以下是用Python语言编写的代码:
```python
class BinaryTreeNode:
def __init__(self, value):
self.value = value
self.left_child = None
self.right_child = None
def level_order_traversal(root):
if root is None:
return
queue = [root]
while len(queue) > 0:
node = queue.pop(0)
print(node.value, end=" ")
if node.left_child is not None:
queue.append(node.left_child)
if node.right_child is not None:
queue.append(node.right_child)
def count_degree_one_nodes(root):
if root is None:
return 0
count = 0
queue = [root]
while len(queue) > 0:
node = queue.pop(0)
if (node.left_child is None and node.right_child is not None) or \
(node.left_child is not None and node.right_child is None):
count += 1
if node.left_child is not None:
queue.append(node.left_child)
if node.right_child is not None:
queue.append(node.right_child)
return count
```
其中,`BinaryTreeNode` 类表示二叉树的结点,包含一个值属性 `value` 和左右子结点属性 `left_child` 和 `right_child`。`level_order_traversal` 方法用层次遍历的方式输出二叉树的结点值。`count_degree_one_nodes` 方法统计二叉树中度为1的结点个数。
使用示例:
```python
# 构建二叉树
root = BinaryTreeNode(1)
root.left_child = BinaryTreeNode(2)
root.right_child = BinaryTreeNode(3)
root.left_child.left_child = BinaryTreeNode(4)
root.left_child.right_child = BinaryTreeNode(5)
root.right_child.right_child = BinaryTreeNode(6)
# 层次遍历二叉树
level_order_traversal(root)
# 输出: 1 2 3 4 5 6
# 统计度为1的结点个数
count = count_degree_one_nodes(root)
print("Degree-1 nodes count:", count)
# 输出: Degree-1 nodes count: 2
```
这里的二叉树为:
```
1
/ \
2 3
/ \ \
4 5 6
```
其中,度为1的结点为2和3。
阅读全文