8

我想使用自己的 Node 类在 Java 中实现树结构。但我很困惑如何做一个深拷贝来复制一棵树。

我的节点类将是这样的：

public class Node{
private String value;
private Node leftChild;
private Node rightChild;
....

我是递归新手，有什么可以学习的代码吗？谢谢！

4

7 回答 7

26

尝试

class Node {
    private String value;
    private Node left;
    private Node right;

    public Node(String value, Node left, Node right) {
        this.value = value;
        ...
    }

    Node copy() {
        Node left = null;
        Node right = null;
        if (this.left != null) {
            left = this.left.copy();
        }
        if (this.right != null) {
            right = this.right.copy();
        }
        return new Node(value, left, right);
    }
}
于 2013-04-19T06:36:10.627 回答
4

使用前序遍历递归地执行此操作。

    public static Node CopyTheTree(Node root)
    {
        if (root == null)
        {
            return null;
        }
        Node newNode = new Node(null, null, root.Value);
        newNode.Left= CopyTheTree(root.Left);
        newNode.Right= CopyTheTree(root.Right);
        return newNode;
    }
于 2017-03-24T03:07:45.370 回答
3

你可以使用这样的东西。它将首先明智地通过旧树深度并创建它的副本。

private Tree getCopyOfTree(oldTree) {
 Tree newTree = new Tree();
 newTree.setRootNode(new Node());
 copy(oldTree.getRootNode(), newTree.getRootNode())
 return newTree;
}

private void copy(Node oldNode, Node newNode) {

 if (oldNode.getLeftChild != null) { 
  newNode.setLeftChild(new Node(oldNode.getLeftChild()));
  copy(oldNode.getLeftChild, newNode.getLeftChild()); 
 }

 if (oldNode.getRightChild != null) {
  newNode.setRightChild(new Node(oldNode.getRightChild()));
  copy(oldNode.getRightChild, newNode.getRightChild());
 }
}
于 2013-04-19T06:37:17.913 回答
2

我喜欢上面 Evgeniy Dorofeev 的回答，但有时您可能无法向该类型添加方法，Node因为您可能不拥有它。在这种情况下（这是在 c# 中）：

public static TreeNode CopyTree(TreeNode originalTreeNode)
{
    if (originalTreeNode == null)
    {
        return null;
    }

    // copy current node's data
    var copiedNode = new TreeNode(originalTreeNode.Data);

    // copy current node's children
    foreach (var childNode in originalTreeNode.Children)
    {
        copiedNode.Children.Add(CopyTree(childNode));
    }

    return copiedNode;
}
于 2016-04-23T12:03:58.710 回答
0

不确定，但尝试对树进行后序遍历并为您遍历的每个节点创建一个新节点。您可能需要堆栈来存储您创建的节点以创建左右子链接。

于 2013-04-19T06:29:04.557 回答
0 
public static TreeNode copy( TreeNode source )
   {
      if( source == null )
         return null;
      else
         return new TreeNode( source.getInfo( ), copy( source.getLeft( ) ), copy( source.getRight( ) ) );
   }

/当然。抱歉耽搁了。无论如何......任何递归方法都有一个基本案例和一个或多个递归案例。在这种情况下，第一行很明显......如果参数'source'的参数为null（因为它最终评估为以结束方法的操作），它将返回null；如果不是，则启动递归案例。在这种情况下，一旦递归完成，您将返回整个复制的树。使用了“new”操作符，表示在遍历期间每次访问树的各个节点时实例化一个 TreeNode，通过对“copy”的递归调用发生，其参数成为对左右 TreeNodes 的引用（如果有是任何）。一旦 source 在每个参数中变为 null，就会启动基本情况，/

于 2018-02-27T06:07:26.170 回答
0 
 Node copy(Node node)
  {
    if(node==null) return node;
    Node node1 =new Node(node.data);
    node1.left=copy(node.left);
    node1.right=copy(node.right);
    return node1;
  }
于 2021-12-28T22:59:26.880 回答