Python实现用户输入数据的BST（前序遍历）问题求助

原代码的核心问题 #

• 重复输入问题：多次调用main()，每次调用都会触发input()，导致重复要求用户输入数据。且原main()函数逻辑错误，遍历keys时直接return key，会提前终止函数，无法返回完整的输入数据列表。
• Insert函数错误：当root为None时，错误返回main().keys[0]（字符串类型），而非创建新的Node对象，后续访问root.key时自然会抛出属性错误。
• 调用逻辑混乱：Node(main())属于无效操作，insert函数的调用参数完全错误，既没有正确创建根节点，也没有遍历所有输入数据进行插入。

修正后的完整代码 #

class Node:
    def __init__(self, key):
        self.key = key
        self.leftBranch = None
        self.rightBranch = None

def insert(root, key):
    # 当前节点为空时，创建新节点作为插入位置
    if root is None:
        return Node(key)
    # 已存在相同key，直接返回原节点
    if root.key == key:
        return root
    # key大于当前节点key，插入右子树
    elif root.key < key:
        root.rightBranch = insert(root.rightBranch, key)
    # key小于当前节点key，插入左子树
    else:
        root.leftBranch = insert(root.leftBranch, key)
    return root

def preorder(root):
    if root:
        print(root.key, end=' ')
        preorder(root.leftBranch)
        preorder(root.rightBranch)
    
def main():
    # 获取用户输入并转换为整数列表（可自行扩展处理空输入、非数字的情况）
    input_str = input('Enter data to construct a BST (numbers divided by a space): ')
    keys = [int(k) for k in input_str.split() if k.strip()]
    
    if not keys:
        print('No valid input data')
        return
    
    # 第一个数字作为根节点
    root = Node(keys[0])
    # 插入剩余所有数据
    for key in keys[1:]:
        insert(root, key)
    
    # 前序遍历输出
    print('Pre-order traversal result:')
    preorder(root)

# 启动程序
if __name__ == "__main__":
    main()

关键修改说明 #

1. main()函数重构：
   • 一次性获取用户输入，将输入字符串转换为整数列表，避免重复调用input()。
   • 先创建根节点，再遍历剩余数据逐个插入，逻辑清晰。
2. Insert函数修正：
   • 当root为None时，返回新的Node对象，确保所有节点都是Node类型，避免属性错误。
   • 简化逻辑，保证递归插入的正确性。
3. 调用逻辑优化：
   • 通过if __name__ == "__main__":启动main()，符合Python程序的标准结构，避免代码被导入时自动执行。
   • 前序遍历输出用end=' '让结果更美观，可根据需求调整格式。

内容的提问来源于stack exchange，提问作者paparonnie