写出代码设计二叉树,要求定义二叉树存储结构,建立二叉链表存储的二叉树并实现二叉树的先序遍历,中序遍历,后序遍历并实现二叉树的高度,求结点双亲,统计叶子结点数目,打印二叉树等操作,最后编写测试主函数
时间: 2024-11-04 09:09:39 浏览: 30
在Python中,我们可以创建一个简单的二叉树节点类以及相应的遍历、高度计算、父节点查找和叶节点计数等功能。下面是一个基础的实现:
```python
# 定义二叉树节点
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# 插入节点到二叉树
def insert(root, val):
if not root:
return TreeNode(val)
elif val < root.val:
root.left = insert(root.left, val)
else:
root.right = insert(root.right, val)
return root
# 先序遍历
def preorder_traversal(node):
if node is not None:
print(node.val)
preorder_traversal(node.left)
preorder_traversal(node.right)
# 中序遍历
def inorder_traversal(node):
if node is not None:
inorder_traversal(node.left)
print(node.val)
inorder_traversal(node.right)
# 后序遍历
def postorder_traversal(node):
if node is not None:
postorder_traversal(node.left)
postorder_traversal(node.right)
print(node.val)
# 计算树的高度
def height(node):
if node is None:
return 0
else:
left_height = height(node.left)
right_height = height(node.right)
return max(left_height, right_height) + 1
# 查找父节点
def find_parent(node, target_val):
while node and node.val != target_val:
if target_val < node.val:
node = node.left
else:
node = node.right
return node
# 统计叶子节点
def count_leaves(node):
if node is None:
return 0
elif node.left is None and node.right is None:
return 1
else:
return count_leaves(node.left) + count_leaves(node.right)
# 打印二叉树
def print_tree_pre_in_post(root):
print("Preorder Traversal:")
preorder_traversal(root)
print("\nInorder Traversal:")
inorder_traversal(root)
print("\nPostorder Traversal:")
postorder_traversal(root)
print(f"\nHeight of the tree: {height(root)}")
parent = find_parent(root, None)
print(f"Parent of a leaf: {parent.val} (if exists)")
print(f"Number of leaves: {count_leaves(root)}")
# 测试主函数
root = insert(None, 5) # 构建示例二叉树
insert(root, 3)
insert(root, 7)
insert(root, 2)
insert(root, 4)
insert(root, 6)
insert(root, 8)
print_tree_pre_in_post(root)
```
在这个例子中,我们首先定义了`TreeNode`类表示二叉树的节点,然后实现了插入节点、各种遍历方式、高度计算、父节点查找、叶节点计数和打印二叉树的功能。测试主函数创建了一个简单的二叉树,并演示了如何使用这些功能。请注意,实际应用中你需要根据需求调整和完善这个框架。
阅读全文