已知一个二叉树(从键盘输入),求双亲结点个数和叶子结点个数
时间: 2024-01-28 22:03:49 浏览: 76
假设二叉树的每个结点包含三个属性:值、左子结点和右子结点。可以使用递归的方法来求双亲结点个数和叶子结点个数。
代码如下:
```python
# 定义二叉树结点类
class TreeNode:
def __init__(self, val=None, left=None, right=None):
self.val = val
self.left = left
self.right = right
# 从键盘输入构建二叉树
def create_tree():
val = input("Enter the value of the node (or None): ")
if val == "None":
return None
node = TreeNode(val)
node.left = create_tree()
node.right = create_tree()
return node
# 计算双亲结点个数
def count_parent_nodes(root):
if not root:
return 0
if root.left or root.right:
return 1 + count_parent_nodes(root.left) + count_parent_nodes(root.right)
return 0
# 计算叶子结点个数
def count_leaf_nodes(root):
if not root:
return 0
if not root.left and not root.right:
return 1
return count_leaf_nodes(root.left) + count_leaf_nodes(root.right)
# 主函数
if __name__ == "__main__":
root = create_tree()
parent_node_count = count_parent_nodes(root)
leaf_node_count = count_leaf_nodes(root)
print("Parent node count: ", parent_node_count)
print("Leaf node count: ", leaf_node_count)
```
运行程序后,按照提示输入二叉树的结点值,输入 "None" 表示该结点为空。程序会自动构建二叉树并计算双亲结点个数和叶子结点个数。
阅读全文