c＃n-ary树的深拷贝

Question

我有这样的节点的n-ry树：

class Node
{
  public Node Parent = null;
  public List<Node> Children = new List<Node>();
  public string Name;
}

我需要对原始树进行深层复制，并避免在更改原始树时更改新树。我只知道如何做浅拷贝：

public Node Copy(Node original)
{
  Node newNode = new Node();
  newNode.Parent = original.Parent;
  newNode.Children = original.Children;
  newNode.Name = original.Name;

  return newNode;
}

在这种情况下，我将两个节点指向内存中的对象复制，当原始节点更改时，newNode将更改为。任何人都可以帮我做深度克隆吗？

Answer 1

递归地做。请注意，这会将第一个节点的父节点设置为null。即如果从树的中间开始复制，则不会维护父节点。

public Node Copy()
{
  Node newNode = new Node();
  newNode.Name = this.Name;

  foreach(var child in this.Children)
  {
      newChild = child.Copy();
      newChild.Parent = newNode;
      newNode.Children.Add(newChild);
  }

  return newNode;
}

Answer 2

你要递归地做。并且您需要创建克隆的父级。

public Node Copy(Node origin, Node parent = null)
{
    if (origin == null)
    {
        return null;
    }

    var result = new Node { Parent = parent, Name = origin.Name };
    result.Children = origin.Children != null ? origin.Children.Select(x => Copy(x, result)).ToList() : null;
    return result;
}

如果您只有Node且没有系统类型，这将有所帮助。