如何在Python中递归为N叉树添加节点（羊狼过河问题）

问题核心 #

• 已手动给N叉树根节点添加5个子节点，每个对应父节点状态计算后的结果，需要编写递归生成器，为每个子节点再生成5个符合规则的子节点，直到节点达到目标状态
• 羊狼过河规则细节：
  • 初始状态：左岸3羊3狼、右岸0羊0狼，船在左岸（位置标记为0）
  • 目标状态：左岸0羊0狼、右岸3羊3狼，船在右岸（位置标记为1）
  • 约束要求：船到达对岸后，任意一岸的狼数量不能超过羊数量（若该岸羊数为0则例外，无羊可吃）
• 每个节点的5种可能操作（需注意船位置切换的双向性）
• 当前问题：child.add_child(child)语句导致最大递归深度错误，同时纠结节点生成时校验约束还是搜索阶段再过滤

错误直接修正：递归自引用问题 #

你写的child.add_child(child)是把节点自己作为子节点，这会触发无限递归调用，直接造成栈溢出。正确做法是根据父节点状态计算出合法的子节点状态，创建新的Node实例，再将这个新实例添加为父节点的子节点。

生成节点的最优选择：边生成边校验 #

绝对不建议先生成所有节点再过滤——羊狼过河的状态空间虽然不大，但无限制生成会导致节点爆炸，大量非法状态完全没必要生成，纯纯浪费内存和计算资源。正确流程是：

1. 递归处理当前节点时，先判断是否达到目标状态，是则终止递归
2. 根据当前船的位置，生成5种可能的状态变更（船在右岸时，操作是右岸动物返回左岸，对应左岸羊/狼数量增加，要反向处理）
3. 对每个生成的新状态，先做合法性校验：
   • 所有岸的羊、狼数量不能为负数，也不能超过初始总数（3羊3狼）
   • 船位置只能是0或1
   • 船离开当前岸后，对岸的狼数不能超过羊数（若对岸羊数>0）
4. 只有合法的状态，才创建新的Node实例，添加为当前节点的子节点，再递归处理这个新子节点

示例代码思路 #

Node类定义 #

class Node:
    def __init__(self, left_sheep, left_wolf, boat_pos):
        self.left_sheep = left_sheep
        self.left_wolf = left_wolf
        self.boat_pos = boat_pos
        self.children = []
    
    def add_child(self, child_node):
        self.children.append(child_node)

递归生成树的方法 #

def build_tree(current_node):
    # 先判断是否达到目标状态，是则停止递归
    if current_node.left_sheep == 0 and current_node.left_wolf == 0 and current_node.boat_pos == 1:
        return
    
    # 根据船的位置确定操作方向
    if current_node.boat_pos == 0:
        # 船在左岸，动物从左到右，左岸数量减少
        operations = [
            (-1, 0),   # 1只羊过河
            (0, -1),   # 1只狼过河
            (-2, 0),   # 2只羊过河
            (0, -2),   # 2只狼过河
            (-1, -1)   # 1羊1狼过河
        ]
    else:
        # 船在右岸，动物从右到左，左岸数量增加
        operations = [
            (1, 0),    # 1只羊返回
            (0, 1),    # 1只狼返回
            (2, 0),    # 2只羊返回
            (0, 2),    # 2只狼返回
            (1, 1)     # 1羊1狼返回
        ]
    
    for sheep_delta, wolf_delta in operations:
        new_left_sheep = current_node.left_sheep + sheep_delta
        new_left_wolf = current_node.left_wolf + wolf_delta
        new_boat_pos = 1 - current_node.boat_pos  # 切换船位置
        
        # 合法性校验：数量不能超界或为负
        if new_left_sheep < 0 or new_left_sheep > 3:
            continue
        if new_left_wolf < 0 or new_left_wolf > 3:
            continue
        
        right_sheep = 3 - new_left_sheep
        right_wolf = 3 - new_left_wolf
        
        # 合法性校验：两岸狼数不能超过羊数（羊为0时允许）
        if (new_left_sheep > 0 and new_left_wolf > new_left_sheep) or \
           (right_sheep > 0 and right_wolf > right_sheep):
            continue
        
        # 创建新节点并添加到当前节点的子节点列表
        child_node = Node(new_left_sheep, new_left_wolf, new_boat_pos)
        current_node.add_child(child_node)
        
        # 递归处理新生成的子节点
        build_tree(child_node)

初始化并生成树 #

# 创建初始节点：左岸3羊3狼，船在左岸（位置0）
root = Node(3, 3, 0)
# 启动递归生成
build_tree(root)

关键说明 #

• 递归终止条件明确：达到目标状态就停止向下生成节点
• 每一步生成子节点前都做合法性校验，彻底避免无效节点的生成
• 完全修正了自引用错误：创建全新的child_node而非用当前节点自身添加
• 补充了船在右岸时的反向操作，这是完成往返过河的必要逻辑

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