如何在科特林深度复制一棵N-芳基树

Question

如果您想创建树的深度副本(以便中的每个节点都被深度复制(，您必须使用下面答案中提供的递归算法。

我还没有找到这样一篇关于SO的文章，关于在Kotlin中实现这一点，更不用说关于N元树的文章太少和稀疏了。这就是为什么我把代码留在这里给任何需要解决这样一个问题的人。

Answer 1

假设我们有一个类型为T:的树类

data class Tree<T>(var root: TreeNode<T>) {
}

在该类中，我们有一个TreeNode类：

data class TreeNode<T>(var name: String, private var nodeAttributes: MutableList<T> = mutableListOf()) {
var parent: TreeNode<T>? = null
val childrenList: MutableList<TreeNode<T>> = mutableListOf()
var depth = 0
private set
var index = 0
private set
var childLowestIndex = 0
private set
fun addChild(node: TreeNode<T>) {
node.parent = this
node.index = this.childLowestIndex
this.childLowestIndex++
node.depth = this.depth + 1
childrenList.add(node)
}
}

TreeNode有一个String名称和nodeAttributes——后者是树初始化时使用的类型为T的可变列表。它允许在创建时或以后通过addAttributes((和getAttributes(

树结构建立在嵌套的树节点上。

假设我们必须深入复制这个树或特定的树节点。为了做到这一点，我们应该在Tree类中添加这样一个方法

fun clone() = Tree(this.root.clone())

但是，为了深度复制用根节点初始化的树，该树包含整个数据结构，我们还必须深入复制整个数据结构，即结构中的每个树节点。

为此，我们可以在树节点类中添加以下方法：

/**
* Return a new independent instance of this TreeNode (deep copy), uses recursion
*/
fun clone(): TreeNode<T> {
val newNode = TreeNode(this.name, this.nodeAttributes.map { it }.toMutableList())
newNode.depth = this.depth
this.childrenList.forEach {
val newChild = it.clone()
newNode.addChild(newChild)
}
return newNode
}

这种方法在每次调用中的作用是：

1. 从调用clone((的节点具有的相同初始参数创建一个新的临时节点newNode

2. 同时复制节点的深度。无需复制其余参数。

3. 对于该节点的每个子节点，将添加该子节点的clone((作为子节点，因此该函数是递归的。

4. 它一直持续到调用最深节点上的clone((，该节点没有children，因此之后不会执行克隆，并且clone((返回最深节点的深层副本。

5. 该算法一直返回所有新的深度复制节点及其深度复制的子节点，并将它们作为子节点添加到层次结构中更高的节点，直到调用clone((的原始节点达到

因此，treeNode.clone((返回任何选定treeNode的深度副本

然后，从深度复制的原始节点创建原始树的深度副本。再次：

fun clone() = Tree(this.root.clone())

我希望，这篇文章是有用的，请随时在评论中添加任何更正和建议。

这是完整代码的链接。https://github.com/lifestreamy/TreeBuilder/blob/master/src/main/kotlin/treeBuilder/Tree.kt