java - 带有列表的树上的 BFS

Question

所以我正在构建这棵树，它有 1..* 个节点，其中每个节点都有一个列表，该列表本身可以有 1..* 个节点。

树的前三层我可以构建得很好，但如果我不编写所有愚蠢的级别，它就不会发挥更多作用。解决方案当然是使用某种递归方法和 BFS。

基本上，在我的 TreeBuilder 类中，我希望能够调用tree.getNodesAtDepth(深度)) 并获取该深度的所有节点的列表。问题是我不明白如何实现 getNodesAtDepth(深度) 方法。

我找到的所有示例都是二叉树的。另一种方法是让 addChild 方法采用深度参数，这样我就可以指定插入子项的深度。

最后，这就是我想要的:我有一棵 Root过的树。根有一个包含 4 个子节点的列表。我想要4个 child 。为每个子节点生成三个节点。因此， child 0 有 3 个 child ， child 1 有 3 个 child ， child 3 有 3 个 child ， child 4 有 3 个 child 。等等

也许一个可能的解决办法是在每个节点上都有一个 level 属性并搜索该节点，然后返回它的父节点。因为它的父节点应该具有搜索节点处的所有节点的列表。

Answer 1

尝试这个方法:

static void getNodesAtDepth(Node root, int currentLevel, int level, List<Node> nodes) {
    if(root == null) return;
    if(level == 0) {
        nodes.add(root);
        return;
    }

    if(currentLevel + 1 == level) {
        if(root.getNodeList() != null) {
            nodes.addAll(root.getNodeList());
        }
    }

    if(currentLevel < level) {
        if(root.getNodeList() != null) {
            for(Node node : root.getNodeList()) {
                getNodesAtDepth(node, currentLevel + 1,  level , nodes);
            }
        }
    }
}

如何使用它:

List<Node> nodeList = new LinkedList<>();
getNodesAtDepth(root, 0, 2, nodeList);

root 当然是树的根。 nodeList 会将所有节点存储在所需级别(在我的例子中为 2)。第二个参数始终为0(用于跟踪当前级别)