解析字符串向量中的 Java 树结构中的节点

Question

我有一个看起来像这样的数据结构

private String name;
private ArrayList<Node> children;
private String parent="";

public Node(String name) {
setName(name);
children = new ArrayList<Node>();
}

在我的程序的其他地方，我有一个名为“root”的节点，其中包含整个树数据结构。

从概念上讲，它看起来像这样

                                       root
                                      /     \
                                     /       \
                                  node1     node2
                                   /           \
                                  /             \
                                node2          node3
                                / 
                               /
                             node3

正如您所看到的，节点可以具有相同的名称。这是有意的。我想为每个节点创建一个字符串，其中包含其自己的名称及其沿袭，并将它们存储在向量中。

因此左侧的节点 3 为 "root|node1|node2|node3" 右侧的节点 3 为 "root|node2|node3" node1 为“root|node1”等。

我有一种方法可以迭代节点结构来打印每个节点，但我发现很难设置每个父节点，因为我无法找到一种方法来做到这一点。任何帮助都会很棒，因为到目前为止我尝试过的一切都失败了。一个重要的注意事项是，该树不一定是二叉树，我只是用它作为示例。

这是我用来打印树的每个节点的代码。希望它很容易调整。

public void print() {
        LinkedList<Node> open = new LinkedList<Node>();
        LinkedList<Node> closed = new LinkedList<Node>();

        open.add(this);

        while(!open.isEmpty()) {
            Node currentNode = open.removeFirst();
            System.out.println(currentNode.getName());

            ArrayList<Node> children = currentNode.getChildren();
            closed.add(currentNode);

            for(int i = 0; i < children.size(); i++) {
                Node current = children.get(i);
                open.addLast(current);
            }
        }
    }

谢谢你们。

Answer 1

我假设您已经创建了这些节点，并且它们是与子节点一起创建的，但没有父节点？似乎有几个选项：

1. 创建子项时，设置父项（我认为您实际上无法控制它，因为您在问这个问题）所以......
2. 可以使用某种类型的 Map 而不是 Vector您可以在其中将密钥设置为沿袭。然后，当您迭代节点时，进行一些字符串调整以删除当前节点的名称，并留下父谱系。
3. 与 #2 相关，不要使用 Map（并保留 Vector）并仍然执行字符串操作，但您必须迭代 Vector 中的每个节点以按其谱系查找父节点。

希望这有帮助，希望我的假设是正确的
-戴夫

Answer 2

似乎在构建树时添加父节点会更容易，但是如果构建了树并且想要向每个节点添加父节点，则可以使用递归。
我会尝试类似的方法

addParent(root, "");

public void addParent(Node node, String parent) {
  node.setParent(parent);

  // if this node has children iterate through them
  // and call addParent with current node name.
  for(Node childNode : node.getChildren()) {
        addParent(childNode, node.getName());
  }
}

注意：在发布之前我无法测试此代码。