创建一任意二叉树,统计某子树下度为 0、度为 1 和度为 2 的结点个数。
时间: 2024-04-30 21:25:16 浏览: 68
计算二叉树的结点个数
5星 · 资源好评率100%
首先,我们需要定义一下二叉树的结构:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
```
接着,我们可以编写一个函数来统计某子树下度为 0、度为 1 和度为 2 的结点个数。该函数需要传入一个二叉树的根节点和要统计的子树的根节点。
```python
def count_nodes(root, node):
if not root:
return 0, 0, 0
if root == node:
left_0, left_1, left_2 = count_nodes(root.left, root.left)
right_0, right_1, right_2 = count_nodes(root.right, root.right)
return left_0 + right_0, left_1 + right_1, left_2 + right_2
left_0, left_1, left_2 = count_nodes(root.left, node)
right_0, right_1, right_2 = count_nodes(root.right, node)
count_0 = count_1 = count_2 = 0
if not root.left and not root.right:
count_0 = 1
elif not root.left or not root.right:
count_1 = 1
else:
count_2 = 1
return left_0 + right_0 + count_0, left_1 + right_1 + count_1, left_2 + right_2 + count_2
```
在该函数中,我们使用了递归的方式来遍历二叉树。如果当前节点为要统计的子树的根节点,则我们递归地统计其左右子树的度为 0、1 和 2 的节点个数,然后将其相加并返回。如果当前节点不是要统计的子树的根节点,则我们递归地统计其左右子树中要统计的子树的度为 0、1 和 2 的节点个数,然后将其相加并返回。
下面是一个完整的示例程序:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def count_nodes(root, node):
if not root:
return 0, 0, 0
if root == node:
left_0, left_1, left_2 = count_nodes(root.left, root.left)
right_0, right_1, right_2 = count_nodes(root.right, root.right)
return left_0 + right_0, left_1 + right_1, left_2 + right_2
left_0, left_1, left_2 = count_nodes(root.left, node)
right_0, right_1, right_2 = count_nodes(root.right, node)
count_0 = count_1 = count_2 = 0
if not root.left and not root.right:
count_0 = 1
elif not root.left or not root.right:
count_1 = 1
else:
count_2 = 1
return left_0 + right_0 + count_0, left_1 + right_1 + count_1, left_2 + right_2 + count_2
if __name__ == "__main__":
# 创建一棵二叉树
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)
# 统计子树的度为 0、1 和 2 的节点个数
count_0, count_1, count_2 = count_nodes(root, root.left)
print("度为 0 的节点个数:", count_0)
print("度为 1 的节点个数:", count_1)
print("度为 2 的节点个数:", count_2)
```
运行上述代码,将输出以下结果:
```
度为 0 的节点个数: 1
度为 1 的节点个数: 1
度为 2 的节点个数: 1
```
阅读全文