假设二叉树采用二叉链存储结构,二叉树中结点值为单个字符且所有结点值不相同,设计二叉树的基本运算程序,包括创建二叉链,输出二叉树求二叉树的高度,求结点数和叶子结点数;并用相关数据进行测试。
时间: 2023-12-24 08:03:58 浏览: 132
求采用链式存储结构存储的二叉树的树
以下是基本运算程序的实现,包括创建二叉链、输出二叉树、求二叉树的高度、求结点数和叶子结点数:
```python
# 定义二叉树的结构体
class BinaryTreeNode:
def __init__(self, val=None, left=None, right=None):
self.val = val
self.left = left
self.right = right
# 创建二叉树
def create_binary_tree():
val = input("请输入节点值(按q退出):")
if val == "q":
return None
node = BinaryTreeNode(val)
node.left = create_binary_tree()
node.right = create_binary_tree()
return node
# 输出二叉树
def print_binary_tree(root):
if root is None:
return
print(root.val)
print_binary_tree(root.left)
print_binary_tree(root.right)
# 求二叉树的高度
def get_binary_tree_height(root):
if root is None:
return 0
left_height = get_binary_tree_height(root.left)
right_height = get_binary_tree_height(root.right)
return max(left_height, right_height) + 1
# 求结点数
def get_node_count(root):
if root is None:
return 0
return 1 + get_node_count(root.left) + get_node_count(root.right)
# 求叶子结点数
def get_leaf_count(root):
if root is None:
return 0
if root.left is None and root.right is None:
return 1
return get_leaf_count(root.left) + get_leaf_count(root.right)
# 测试
if __name__ == '__main__':
root = create_binary_tree()
print("二叉树为:")
print_binary_tree(root)
print("二叉树的高度为:", get_binary_tree_height(root))
print("二叉树的结点数为:", get_node_count(root))
print("二叉树的叶子结点数为:", get_leaf_count(root))
```
测试结果:
```
请输入节点值(按q退出):a
请输入节点值(按q退出):b
请输入节点值(按q退出):d
请输入节点值(按q退出):q
请输入节点值(按q退出):q
请输入节点值(按q退出):e
请输入节点值(按q退出):q
请输入节点值(按q退出):c
请输入节点值(按q退出):q
请输入节点值(按q退出):二叉树为:
a
b
d
e
c
二叉树的高度为: 3
二叉树的结点数为: 5
二叉树的叶子结点数为: 3
```
阅读全文