通过基于层级的树遍历创建一棵 n 叉树

Question

所以我正在逐层遍历一棵 n 元树，该树的节点具有属性 id 和名称，我想更改每个节点的名称并创建另一个具有更改节点（根节点）的类似 n 元树A 作为 id)

    Queue<Node> queue = new LinkedList<>();
    // node being the root node of the already created n-ary tree
    queue.add(node);
    Node rootOut = new Node(node.id,node.name);
    Node copiedNode = null;
    Node resNode = null;
    // iterate while queue not empty
    while(!queue.isEmpty()){

        // dequeue
        Node next = queue.remove();
    
 
        
        copiedNode = new Node(next.id,next.name);
        for (Node child : next.children) {
           

            Node copiedChildNode = new Node(child.id,child.name);
            copiedNode.children.add(copiedChildNode);
            if (next.id == "A") rootOut = copiedNode;
            queue.add(child);
        }
    }
    return rootOut ;

但这不是 return 正确的新树的根节点。事实上，这个 return 只是根节点及其直接子节点，没有更深的深度。谁能帮助正确地做到这一点

Answer 1

你的尝试不是跟踪你正在制作的副本，所以你不是在构建树，只是一堆单节点副本及其子节点：

    queue.add(node);
    Node copiedNode = null;

    while(!queue.isEmpty()){
        Node next = queue.remove();

        // A new copy (not being referenced by anything)
        copiedNode = new Node(next.id,next.name);
        for (Node child : next.children) {
           

            // A new copy (referenced by only the aforementioned copy
            Node copiedChildNode = new Node(child.id,child.name);
            copiedNode.children.add(copiedChildNode);

            // If the original was "A", store a reference to the copy.
            if (next.id == "A") rootOut = copiedNode;

            // The original is queued, not the copy
            queue.add(child);
        }
    }
 
    // Return only the shallow copy
    return rootOut ;

您需要在副本中构建结构，跟踪引用：

    Queue<Node> queue = new LinkedList<>();
    queue.add(node);
    Node rootOut = new Node(node.id,node.name);

    // For tracking copies
    Map<String, Node> copiedNodesById = new HashMap<>();
    copiedNodesById.put(rootOut.id, rootOut);

    while(!queue.isEmpty()){

        Node currentOriginal = queue.remove();
        // Get an existing copy rather than making a new one.
        Node currentCopy = copiedNodesById.get(currentOriginal.id);
        
        for (Node childOriginal : currentOriginal.children) {

            Node copiedChildNode = new Node(childOriginal.id,childOriginal.name);
            currentCopy.children.add(copiedChildNode);

            // Track the copy that was just made.
            copiedNodesById.put(copiedChildNode.id, copiedChildNode);
            
            if (next.id == "A") rootOut = currentCopy;
            queue.add(childOriginal);
        }
    }
    return rootOut ;

我冒昧地重命名了一些变量，以便更清楚地知道什么是原始版本，什么是副本。

复制的节点也可能在另一个队列中被跟踪。或者队列可以跟踪（原始，复制）元组。

至于根据“A”的位置重组副本，我会把它留给你，因为我不清楚它应该如何运作。

通过基于层级的树遍历创建一棵 n 叉树

Creation of a n-ary tree through level based tree traversal of another

java

tree

data-structures