Geek asks and answers

How to deep copy a binary tree?

I would like to use my own Node class to implement a tree structure in Java. But I am confused how to make a deep copy to copy a tree.

My Node class will look like this:

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

I'm new to recursion, so is there any code I can learn? Thank!

+5
source share
6 answers

to try

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);
    }
}
+15
source

You can use something like this. He will go, although the old tree-like depth will be the first, and will create a copy of it.

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());
 }
}
+3
source

, , , , Node, , , . ( #):

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

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

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

    return copiedNode;
}
+1

, - node node, . .

0

.

    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;
    }
0
public static TreeNode copy( TreeNode source )
   {
      if( source == null )
         return null;
      else
         return new TreeNode( source.getInfo( ), copy( source.getLeft( ) ), copy( source.getRight( ) ) );
   }

/. . ... . ... "" ( ), null; , . .   "" , TreeNode , "copy", TreeNodes ( ). , , "", ./

0
source

More articles:


All Articles