如何基于<x,y>格式输入实现Python非二叉树构建？

问题说明 #

需要基于<x,y>格式的输入构建非二叉树，规则如下：

• x为节点值：?表示非叶子节点（存在子节点），字母表示叶子节点
• y为该节点的子节点数量

示例输入：

? 3
? 1
? 3
? 1
V 0
V 0
? 3
V 0
V 0
D 0
? 1
D 0
D 0
break

已定义节点类：

class NewNode():
    def __init__(self, val):
        self.key = val
        self.child = []

已将输入存入input_list：

input_list = []
while True:
    inp = input().split()
    if inp == ['break']:  # 修正原代码判断逻辑：inp是列表，需与列表比较
        break
    input_list.append(inp)

# 示例对应的列表：
# [['?', '3'], ['?', '1'], ['?', '3'], ['?', '1'], ['V', '0'], ['V', '0'], ['?', '3'], ['V', '0'], ['V', '0'], ['D', '0'], ['?', '1'], ['D', '0'], ['D', '0']]

原构建函数在递归处理非叶子节点时遇到瓶颈，需完成函数实现。

解决方案 #

采用递归方式构建树，利用输入列表的顺序特性（根节点后紧跟其子节点，子节点的子节点紧跟该子节点），每次处理当前节点后，递归创建其所有子节点：

def build_the_tree(input_list):
    # 取出当前节点的输入项，同时从列表中移除
    val, num_child_str = input_list.pop(0)
    num_child = int(num_child_str)
    # 创建当前节点
    current_node = NewNode(val)
    # 为当前节点递归创建所有子节点
    for _ in range(num_child):
        child_node = build_the_tree(input_list)
        current_node.child.append(child_node)
    return current_node

代码说明 #

1. 递归逻辑：每次处理列表的第一个元素，创建当前节点后，根据子节点数量循环调用自身，依次生成每个子节点并添加到当前节点的child列表中
2. 叶子节点处理：叶子节点的y值为0，不会进入循环，直接返回节点，符合叶子节点无子节点的规则
3. 输入列表修改：使用pop(0)会修改原输入列表，若需保留原列表，可传入副本：build_the_tree(input_list.copy())

使用示例 #

# 假设input_list已按示例填充
root = build_the_tree(input_list)
# 验证根节点的子节点数量
print(len(root.child))  # 输出3，符合示例根节点的子节点数

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