Python 实现二叉树操作：构建、遍历、计算高度、找祖先及释放内存

以下是用 Python 实现的代码： ```python class TreeNode: def __init__(self, value): self.value = value self.left = None self.right = None # 构建二叉树的函数 def build_tree(pre_order): def helper(index): if index >= len(pre_order): return None value = pre_order[index] if value == '#': # 特殊字符表示空 return None node = TreeNode(value) node.left = helper(index + 1) node.right = helper(index + 2) return node return helper(0) # 中序遍历 def inorder_traversal(root): if root: inorder_traversal(root.left) print(root.value, end=" ") inorder_traversal(root.right) # 后序遍历 def postorder_traversal(root): if root: postorder_traversal(root.left) postorder_traversal(root.right) print(root.value, end=" ") # 计算节点高度的函数 def get_height(node): if node is None: return 0 left_height = get_height(node.left) right_height = get_height(node.right) return max(left_height, right_height) + 1 # 找出指定节点的祖先 def find_ancestors(root, target): def helper(node, target, ancestors): if node is None: return [] if node.value == target: return ancestors + [node.value] left_ancestors = helper(node.left, target, ancestors + [node.value]) if left_ancestors: return left_ancestors right_ancestors = helper(node.right, target, ancestors + [node.value]) if right_ancestors: return right_ancestors return [] return helper(root, target, []) # 释放二叉树内存 def clear_tree(root): if root: clear_tree(root.left) clear_tree(root.right) root.left = None root.right = None root = None # 主函数 def main(): root = None while True: choice = input("请输入操作选项（1-7）: ") if choice == '1': pre_order = input("请输入二叉树的扩充先序序列: ") root = build_tree(pre_order) elif choice == '2': print("中序序列: ") inorder_traversal(root) print() elif choice == '3': print("后序序列: ") postorder_traversal(root) print() elif choice == '4': print("各节点高度: ") def print_height(node): height = get_height(node) print(f"{node.value}: {height}") if node.left: print_height(node.left) if node.right: print_height(node.right) print_height(root) elif choice == '5': target = input("请输入要查找祖先的节点: ") ancestors = find_ancestors(root, target) print("祖先节点: ", ancestors) elif choice == '6': clear_tree(root) root = None elif choice == '7': break if __name__ == "__main__": main() # 1. 输入的先序序列格式要正确，特殊字符表示空节点。 # 2. 释放内存时要确保递归释放子节点。 # 3. 输入查找祖先的节点时要确保该节点存在于二叉树中。 ``` ######[AI写代码神器 | 848点数解答 | 2024-12-21 16:32:32]