极大极小Python树

Question

作为一个编码项目，我想在我已经实现的基于文本的connect4python游戏中为用户提供某种AI。我研究了最常用的方法，minimax是主要的算法。在

如果我对算法的理解是正确的，我必须实现一个7元树，其中每个节点都有一个棋盘状态和一个玩家可以从该棋盘状态进行的所有可能移动的7个子节点。在

为了实现这个树，我决定使用一个节点类，它有一个子节点列表和一个当前状态。这棵树只有3层，因为根据我的理解，保持完整的游戏日志是不必要的。在

node类只是：

    class _Node(object):
    def __init__(self, state, children=[]):
        self.state = state
        self.children = children

添加的DecisionTree类a构造函数将根设置为None。在

但是，我想了解方法add()如何适用于这种n元树。我写的代码是这样的：

^{pr2}$

我这里的问题是while循环，它显然不能正常工作。它从一个节点变成了一个列表。我想我必须索引子对象，因此需要将索引作为参数。然而，为n元树建立索引会变得很混乱。怎么处理？一般来说，使用列表是一个坏主意吗？在

Answer 1

首先，要小心这个def __init__(..., children=[]):

如果你用这种方式初始化你的节点children，那么下面的代码。。。在

a = Node(1)
b = Node(2)
print(a.children, b.children)

a.children.append(3)
print(a.children, b.children)
print(a.children is b.children) # they both point to same object in memory.

将产生以下输出：

^{pr2}$

之所以会发生这种情况，是因为您在构造函数中提供了空的列表值，并且此默认值在所有实例中共享。 换句话说，在用这个[]默认子值初始化多个节点后，不同节点的子节点将指向内存中的同一个列表。在

正确的方法是这样做：

class Node(object):
    def __init__(self, state, children=None):
        self.state = state
        self.children = children or []

试着先解决这个问题，看看是否有帮助。在

现在谈谈主要问题。依我看，你可以在这里使用列表，但是用while循环穿越树并不是绝地之路。我们可以在这里使用递归。在

一般来说，我不明白您为什么需要根目录，但要跨越树并添加值，您可以执行以下操作：

class Node(object):
    def __init__(self, state, children=None):
        self.state = state
        self.children = children or []

    def add(self, state):
        if self.children:
            for node in self.children: # loop over all children of root
                node.add(state)            # add all the new states
        else:
            self.state.extend(state) 

示例：

r = Node([3])
r.children = [Node([2]),Node([4]),Node([5])]
print(r.children[0].state)

r.add([25,14])
print(r.children[2].state)

# output will be
[2]
[5, 25, 14]