1—create tree; 2—inorder; 3—postorder; 4—high; 5—ancent; 6—clear tree; 7—exit. 输入“1”后，提示输入二叉树的扩充先序序列，“空”可以使用一个特殊字符代表，用输入的序列构造好二叉树。 输入“2”后，对前面构造好的二叉树进行中序遍历，打印出二叉树的中序序列。 输入“3”后，对前面构造好的二叉树进行后序遍历，打印出二叉树的后序序列。 输入“4”后，对前面构造好的二叉树进行某种遍历操作，计算出各结点的高度，并打印出各结点的高度。 输入“5”后，提示输入某结点的名字，对前面构造好的二叉树进行某种遍历操作，找出输入结点的所有祖先，并将该结点祖先打印出来。 输入“6”后，将二叉树各结点的内存释放，变成一棵空树。 输入“7”后，退出程序。 对于“1～6”的操作，执行完后，要返回主程序，打印出主提示，以便进行下一步操作。

以下是用 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. 输入查找祖先的节点时要确保该节点存在于二叉树中。 ``` [2024-12-21 16:32:32 | AI写代码神器 | 848点数解答]