如何构建与另一个创建的树具有相同结构的 n 叉树？

Question

我正在尝试构建与已构建树具有相同结构的 n 元树（在创建要返回的新树时，我想将子节点添加到与已构建树相同的位置一、构建树创建如下：

        Node A = new Node("","A");
        Node B = new Node("","B");
        Node C = new Node("","C");
            ...


        Node root = A;
        root.children.add(B);
        root.children.add(C);
        root.children.add(D);

        root.children.get(1).children.add(G);
        root.children.get(1).children.get(0).children.add(K);
              ...

节点 Class 如下所示：

public class Node {

    public String id;
    public ArrayList<ArrayList<String>> data;
    public Vector<Node> children = new Vector<>();

    public void setId(String id) {
        this.id = id;
    }

    public void setData(ArrayList<ArrayList<String>> data) {
        this.data = data;
    }


    public void setChildren(Vector<Node> children) {
        this.children = children;
    }

    public Node(ArrayList<ArrayList<String>> data, String id) {
        this.data = data;
        this.id = id;
    }
    public Node(ArrayList<ArrayList<String>> data,String id,Vector<Node> children) {
        this.data = data;
        this.id = id;
        this.children = children;
    }

    public Node find_parentNode(String childId) {
        if (this == null)
            return null;

        Queue<Node> queue = new LinkedList<>();
        // we add start node
        queue.add(this);

        // iterate while queue not empty
        while (!queue.isEmpty()) {
            // dequeue and print data
            Node next = queue.remove();
            

            for (Node child : next.children) {
              if (child.id == childId)
                return next;
                queue.add(child);
            }
        }
        return null;
    }

最后主要代码如下：

       // Create rootOut (the root node to be returned)
       Node rootOut = new Node(node.data,node.id,node.children);

       queue.add(node);


        // iterate while queue not empty
        while(!queue.isEmpty()){
            // dequeue
            Node next = queue.remove();
            // we add children nodes if not null after setting an increment var for the children positions
            int j =0 ;
            for (Node child : next.children) {
                
                // Update children of rootOut (the output Tree)
                Node currentNode = rootOut.find_parentNode(child.id);

                currentNode.children.get(j).setChildren(child.children);
                currentNode.children.get(j).setData(child.data);
                currentNode.children.get(j).setId(child.id);
                j++;
                queue.add(child);
            }
        }

基本上在主要代码中，我没有创建新树，而是在将旧构建树复制到新树（通过根节点 rootOut）后覆盖构建树的节点值，这是一个好方法吗？否则如何创建一个与构建树具有相同结构（节点位置）的全新树？

谢谢。

Answer 1

要复制现有树的结构，进行深度优先遍历、复制每个节点并以相同的遍历顺序添加每个子节点就足够了。

您不需要查找父节点，这是一个昂贵的搜索，因为该节点将在上一次调用该方法时添加到正确的父节点。

我无法测试你的代码，因为缺少某些东西（例如什么是 QueryNode？），但它似乎只复制了根节点，而没有实际复制树结构。

所以这个方法会递归复制树，新旧树之间唯一共享的资源是数据ArraList，这里只复制引用。

public static Node cloneNode(Node root) {
    Node copy=new Node(root.data, root.id);
    for (Node c: root.children) {
        copy.children.add(cloneNode(c)));
    }
    return copy;
}

作为对您最后评论的回答，数据的深拷贝并不常见，但如果您真的想要它，只需将方法的第一行替换为这些：

ArrayList<ArrayList<String>> copyData=new ArrayList<>();
for (ArrayList<String> l: root.data) {
    copyData.add(new ArrayList<String>(l));
}
Node copy=new Node(copyData, root.id);

一些无关的评论：

不要使用 Vector，改用 ArrayList
在方法签名和变量声明中最好使用具体 ArrayList 的 List 接口 class（例如，数据应声明为 List）

如何构建与另一个创建的树具有相同结构的 n 叉树？

How to build an n-ary tree having same structure as another created one?

java

tree

nodes

search-tree

data-structures