java - N 叉树的迭代复制(克隆)

Question

如何迭代地克隆/复制 N 叉树，而不需要递归？只需要迭代地重写 cloneRecursive 函数即可:

import java.util.ArrayDeque

sealed class Row {

    abstract val name: String

    data class Section(override val name: String, val rows: List<Row>) : Row()

    data class Field(override val name: String, val data: String) : Row()
}

fun main() {
    val root = Row.Section(
        "root", listOf(
            Row.Section(
                "section 1", listOf(
                    Row.Section(
                        "section 1.1", listOf(
                            Row.Field("field 1.1.1", "1.1.1 - 1"),
                            Row.Field("field 1.1.2", "1.1.2 - 1")
                        )
                    ),
                    Row.Field("field 1.2", "1.2 - 1")
                )
            ),
            Row.Field("field 2", "2 - 1"),
            Row.Field("field 3", "3 - 1"),
            Row.Section(
                "section 4", listOf(
                    Row.Field("field 4.1", "4.1 - 1"),
                    Row.Field("field 4.2", "4.2 - 1"),
                    Row.Section(
                        "section 4.3", listOf(
                            Row.Field("field 4.3.1", "4.3.1 - 1"),
                            Row.Field("field 4.3.2", "4.3.2 - 1")
                        )
                    )
                )
            )
        )
    )

    println(root)
    println(recursiveClone(root))
    println(root == recursiveClone(root))
}

fun recursiveClone(root: Row): Row {
    return when (root) {
        is Row.Section -> {
            val rows = root.rows.map { row ->
                recursiveClone(row)
            }
            Row.Section(root.name, rows)
        }
        is Row.Field -> {
            Row.Field(root.name, root.data)
        }
    }
}

Answer 1

您可以尝试的一种方法是创建几个堆栈。与使用单个堆栈和循环的正常迭代树遍历的唯一区别是第二个堆栈保留对父级的引用，以便可以链接子级。每当访问一个节点时，弹出父堆栈并将当前节点添加到父节点的子列表中。之后，当推送当前节点的子节点以扩展原始堆栈时，将对当前节点的引用推送到每个子节点的父堆栈上。两个堆栈的大小始终相同。

这模拟了使用递归构建子树并将其克隆传递回父调用以填充其子列表的简便性。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Stack;

class Main {
    public static Row clone(Row root) {
        if (root == null) return null;

        var originStack = new Stack<Row>();
        var parentStack = new Stack<Section>();
        originStack.push(root);
        parentStack.push(null);
        Row result = null;

        while (!originStack.isEmpty()) {
            Row curr = originStack.pop();
            Section parent = parentStack.pop();
            Row clone;

            if (curr instanceof Section) {
                clone = new Section(curr.name, new ArrayList<Row>());
                var sec = (Section)curr;

                for (int i = sec.children.size() - 1; i >= 0; i--) {
                    originStack.push(sec.children.get(i));
                    parentStack.push((Section)clone);
                }
            }
            else {
                clone = new Field(curr.name, ((Field)curr).data);
            }

            if (parent == null) {
                result = clone;
            }
            else {
                parent.children.add(clone);
            }
        }

        return result;
    }

    public static void print(Row root) {
        if (root != null) print(root, 0);
    }

    public static void print(Row root, int indent) {        
        for (int i = 0; i < indent; i++) {
            System.out.print(" ");
        }

        System.out.print(root.name);

        if (root instanceof Section) {
            System.out.println();

            for (Row child : ((Section)root).children) {
                print(child, indent + 2);
            }
        }
        else {
            System.out.println(" [" + ((Field)root).data + "]");
        }
    }

    public static void main(String[] args) {
        var root = new Section(
            "a", new ArrayList<>(Arrays.asList(
                new Section(
                    "b", new ArrayList<>(Arrays.asList(
                        new Section(
                            "c", new ArrayList<>(Arrays.asList(
                                new Field("d", "1")
                            ))
                        ),
                        new Section(
                            "e", new ArrayList<>(Arrays.asList(
                                new Field("f", "2"),
                                new Section(
                                    "g", new ArrayList<>(Arrays.asList(
                                        new Field("h", "3"),
                                        new Field("i", "4"),
                                        new Field("j", "5") 
                                    ))
                                )
                            ))
                        )
                    ))
                ),
                new Section(                    
                    "k", new ArrayList<>(Arrays.asList(
                        new Section(
                            "l", new ArrayList<>()
                        ),
                        new Field("m", "6"),
                        new Field("n", "7"),
                        new Section(
                            "o", new ArrayList<>(Arrays.asList(
                                new Field("p", "8")
                            ))
                        )
                    ))
                )
            ))
        );
        var clone = clone(root);
        ((Section)(((Section)clone).children.get(0)))
            .children.add(new Field("a new field", "42"));
        print(root);
        System.out.println("------------");
        print(clone);
        System.out.println("root is the same object as the clone: " + (root == clone));
    }
}

abstract class Row {
    String name;
}

final class Section extends Row {
    ArrayList<Row> children;

    public Section(String name, ArrayList<Row> children) {
        this.name = name;
        this.children = children;
    }
}

final class Field extends Row {
    String data;

    public Field(String name, String data) {
        this.name = name;
        this.data = data;
    }
}

输出:

a
  b
    c
      d [1]
    e
      f [2]
      g
        h [3]
        i [4]
        j [5]
  k
    l
    m [6]
    n [7]
    o
      p [8]
------------
a
  b
    c
      d [1]
    e
      f [2]
      g
        h [3]
        i [4]
        j [5]
    a new field [42]
  k
    l
    m [6]
    n [7]
    o
      p [8]
root is the same object as the clone: false