有 N 个叶子的 Java 树？

Question

我正在解决一个 Java 问题，该问题需要一个具有 N 个叶子的树的 Java 实现。为此，我决定使用 XML Dom 树来表示问题。Dom4j 可以吗？

这个问题基本上是一个游戏树，它代表所有的移动来计算赢得游戏所需的最小移动数。这对于 Dom4j 有用吗？谢谢。

Answer 1

我会尝试回答，但要考虑到一些因素:

首先直接回答你的问题是否可以用XML Dom树来表示问题？ - 是的，这是可能的，但在我看来，使用 XML DOM 树来表示数据结构并不是那么自然(事实上我也可以称其为过度杀伤)，除非您想将该数据结构序列化到磁盘或跨磁盘网络作为 API 调用的结果。

示例如下:http://dom4j.sourceforge.net/dom4j-1.6.1/guide.html

更干净、更简单的替代方案是定义一个 Node 类，如下所示:

class Node
{
   int value; //assuming the node holds an integer value
   List<Node> childNodes; // these are the N child nodes.
}

然后，您的游戏算法可以迭代子节点列表以执行其计算逻辑。

上述定义可能出现的一个限制是，如果您想要搜索特定的子节点，则需要迭代列表 - 而如果您使用 DOM4j，则可以使用 XPath。但使用 DOM 和 XPath 在内存消耗方面有其自身的局限性 - 请参阅 this了解详情。

但是上面提到的简单数据结构不会具有相同的内存含义 - 而且在计算过程中操作数据结构也会更容易。

希望这有帮助。