我在制作井字棋机器人的时候，遇到了理解“树”的巨大障碍。我理解这个概念，但我不知道如何实现它们。

有没有人可以展示一个如何为这种情况生成树的例子？或者一个关于生成树的好的教程？ 我想困难的部分是生成部分树。我知道如何实现生成整棵树，但不知道如何生成部分树。

回答：

想象一下，在井字棋棋盘的任何时刻，每一个可能的走法都是一个分支。棋盘的当前状态是根。一次走法是一个分支。现在假设（一次一个），每个分支都变成当前状态。每个可能的走法都变成一个新的分支。树的叶子是做出最后一步棋并且棋盘满了的时候。

你需要一棵树的原因是，一旦它被构建，你需要找出哪个分支拥有最多的’赢’场景的叶子。你构建所有可能结果的分支，将获胜的总数加起来，然后做出最有机会最终赢得最多胜利的走法。

把树做成这样：

class Node {public:   std::list< Node > m_branches;   BoardState m_board;   int m_winCount;}std::list< Node > tree;

现在，你遍历树中的分支列表，并为每个分支，遍历它的分支。这可以用递归函数完成：

int recursiveTreeWalk( std::list< Node >& partialTree){   for each branch in tree       if node has no branches           calculate win 1/0;       else           recursiveTreeWalk( branch );   partialTree.m_winCount = sum of branch wins;}// initial callrecursiveTreeWalk( tree )

非常伪的代码。