时间戳

首页 > 解决方案 > 如何构建与另一个创建的具有相同结构的 n 叉树？

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

问题描述

我正在尝试构建这个与已经构建的具有相同结构的 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);
              ...

节点类如下所示：

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）之后覆盖构建树的节点的值，这是一个好方法吗？否则如何创建与构建树具有相同结构（节点位置）的全新树？

谢谢。

标签： javadata-structurestreenodessearch-tree

解决方案

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

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

我无法测试您的代码，因为缺少某些内容（例如，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);

一些无关的评论：

  1. 不要使用 Vector，而是使用 ArrayList
  2. 在方法签名和变量声明中，最好使用具体 ArrayList 类的 List 接口（例如，数据应声明为 List<List>）

推荐阅读