Итеративное копирование (клонирование) 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

Один из подходов, который вы можете попробовать, - это создать пару стеков. Единственное отличие от обычного итеративного обхода дерева с использованием одного стека и l oop - это второй стек, который хранит ссылки на родителей, чтобы потомки могли быть связаны. При каждом посещении узла выталкивайте родительский стек и добавляйте текущий узел в список дочерних родительских узлов. Впоследствии, при нажатии дочерних узлов для текущего узла для расширения исходного стека, pu sh ссылка на текущий узел в родительский стек для каждого дочернего элемента. Два стека всегда будут одного размера.

Это имитирует легкость построения дочерних деревьев с использованием рекурсии и передачи их клонов обратно родительскому вызову для заполнения его списка дочерних элементов.

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