我想建立一棵类似于下面的树。

但是，似乎每个节点的子节点设置不正确，我不确定为什么。

作为背景，我正在尝试使用遗传编程 (GP) 来实现 Boolean 6-Multiplexer Problem。 Function 是一个将其子项作为输入的运算符。例如，IF 表示操作：if children[0],return children[1],else return children[2]。 Terminal 基本上是树的叶节点，它有一个值并且没有子节点。

class Node:
    def __init__(self,val: int = None,children: "list[Node]" = []):
        self.val = val
        self.children = children

    def add_child(self,node):
        self.children.append(node)

    def __str__(self,level=0) -> str:
        ret = "\t" * level + self.__repr__() + f"({self.val})" + "\n"
        for child in self.children:
            ret += child.__str__(level + 1)

        return ret

    def required_children_count(self) -> int:
        return 0

    def eval(self) -> int:
        pass


class Terminal(Node):
    def __repr__(self):
        return "Terminal"

    def required_children_count(self):
        return 0

    def eval(self):
        return self.val


class Function(Node):
    pass


class AND(Function):
    def __repr__(self):
        return "AND"

    def required_children_count(self):
        return 2

    def eval(self):
        return self.children[0].eval() and self.children[1].eval()


class OR(Function):
    def __repr__(self):
        return "OR"

    def required_children_count(self):
        return 2

    def eval(self):
        return self.children[0].eval() or self.children[1].eval()


class NOT(Function):
    def __repr__(self):
        return "NOT"

    def required_children_count(self):
        return 1

    def eval(self):
        return not self.children[0].eval()


class IF(Function):
    def __repr__(self):
        return "IF"

    def required_children_count(self):
        return 3

    def eval(self):
        return (
            self.children[1].eval()
            if self.children[0].eval()
            else self.children[2].eval()
        )


class GP:
    def __init__(
        self,terminals: "list[Type[Terminal]]" = [],# TODO: figure out this struct
        functions: "list[Type[Function]]" = [],solutions={},pop_size=100,pm=0.05,pc=0.4,max_depth=3,):
        self.pop_size = pop_size
        self.terminals = terminals
        self.functions = functions
        self.population = []
        self.max_depth = max_depth

    def generate_full_tree_helper(self,node: Node,depth=0):
        for i in range(node.required_children_count()):
            if depth == self.max_depth:
                node.children.append(Terminal(4))
            else:
                new_node = random.choice(self.functions)()
                self.generate_full_tree_helper(new_node,depth + 1)
                node.add_child(new_node)
                print(
                    f"depth: {depth},node: {node.__repr__()},children: {len(node.children)}"
                )

    def generate_full_tree(self):
        head = random.choice(self.functions)()
        self.generate_full_tree_helper(head)
        return head

    # ...


# (a0,a1) -> (d0,d1,d2,d3)
if __name__ == "__main__":
    gp = GP(functions=[AND,OR,NOT,IF])
    gp.generate_full_tree()

将打印的内容：

depth: 2,node: IF,children: 3
depth: 2,children: 6
depth: 2,children: 10
depth: 1,node: NOT,children: 11
depth: 0,children: 12
depth: 2,children: 15
depth: 1,children: 16
depth: 0,children: 17
depth: 2,children: 20
depth: 2,children: 23
depth: 2,children: 25
depth: 1,children: 26
depth: 0,children: 27

我希望它何时打印（由于每个 Function 的子项计数要求）：

depth: 2,children: 3
depth: 1,children: 1
depth: 0,children: 1
depth: 1,children: 3

如果我尝试 print(gp.generate_full_tree())，我会得到以下结果，我认为这是由于孩子们不知何故处于一个循环中：

Traceback (most recent call last):
  File "/Users/michaelvytlingam/Development/ECE457A/a4/q3/q3.py",line 99,in <module>
    print(gp.generate_full_tree())
  File "/Users/michaelvytlingam/Development/ECE457A/a4/q3/functions.py",line 13,in __str__
    ret += child.__str__(level + 1)
  File "/Users/michaelvytlingam/Development/ECE457A/a4/q3/functions.py",in __str__
    ret += child.__str__(level + 1)
  [Previous line repeated 993 more times]
  File "/Users/michaelvytlingam/Development/ECE457A/a4/q3/functions.py",line 11,in __str__
    ret = "\t" * level + self.__repr__() + f"({self.val})" + "\n"
RecursionError: maximum recursion depth exceeded

我通常对递归有很好的理解，但出于某种原因，这已经让我难住了一段时间。如果我猜的话，我会说 node.add_child(new_node) 行并没有像我想的那样做。任何帮助将不胜感激。