1. 实验采用二叉链表作为二叉树的存储结构, 2. 完成对二叉树的建立、先序、中序、后序; 3. 完成按层次遍历的操作; 4. 求所有叶子及结点总数的操作; 5. 编写主程序实现对这些运算的测试。
时间: 2023-06-11 08:08:43 浏览: 124
以下是Python实现该实验的代码:
```python
# 二叉树的存储结构
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
# 二叉树的建立
def build_tree(preorder, inorder):
if not preorder or not inorder:
return None
root = TreeNode(preorder[0])
index = inorder.index(preorder[0])
root.left = build_tree(preorder[1:index+1], inorder[:index])
root.right = build_tree(preorder[index+1:], inorder[index+1:])
return root
# 先序遍历
def preorder_traversal(root):
if not root:
return []
return [root.val] + preorder_traversal(root.left) + preorder_traversal(root.right)
# 中序遍历
def inorder_traversal(root):
if not root:
return []
return inorder_traversal(root.left) + [root.val] + inorder_traversal(root.right)
# 后序遍历
def postorder_traversal(root):
if not root:
return []
return postorder_traversal(root.left) + postorder_traversal(root.right) + [root.val]
# 层次遍历
def levelorder_traversal(root):
if not root:
return []
queue = [root]
result = []
while queue:
node = queue.pop(0)
result.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return result
# 求叶子结点数和总结点数
def count_leaves_nodes(root):
if not root:
return 0, 0
if not root.left and not root.right:
return 1, 1
left_leaves, left_nodes = count_leaves_nodes(root.left)
right_leaves, right_nodes = count_leaves_nodes(root.right)
leaves = left_leaves + right_leaves
nodes = left_nodes + right_nodes + 1
return leaves, nodes
# 测试主程序
if __name__ == '__main__':
# 建立二叉树
preorder = [1, 2, 4, 5, 3, 6]
inorder = [4, 2, 5, 1, 3, 6]
root = build_tree(preorder, inorder)
# 遍历测试
print("先序遍历:", preorder_traversal(root))
print("中序遍历:", inorder_traversal(root))
print("后序遍历:", postorder_traversal(root))
print("层次遍历:", levelorder_traversal(root))
# 计算叶子结点数和总结点数
leaves, nodes = count_leaves_nodes(root)
print("叶子结点数:", leaves)
print("总结点数:", nodes)
```
输出结果为:
```
先序遍历: [1, 2, 4, 5, 3, 6]
中序遍历: [4, 2, 5, 1, 3, 6]
后序遍历: [4, 5, 2, 6, 3, 1]
层次遍历: [1, 2, 3, 4, 5, 6]
叶子结点数: 3
总结点数: 6
```