Jak głęboko skopiować drzewo?

Question

Chciałbym użyć mojej własnej klasy węzła do zaimplementowania struktury drzewa w Javie. Ale jestem zdezorientowany, jak zrobić głęboką kopię, aby skopiować drzewo.

klasa

My Węzeł byłoby tak:

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

Jestem nowy na rekurencji, więc jest jakiś kod można studiować? Dziękuję Ci!

Answer 1

spróbować

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); 
    } 
} 

Answer 2

Nie jesteś pewien, ale spróbuj czegoś z przechodzeniem do porządku swojego drzewa i tworząc nowy węzeł dla każdego przeszukiwanego węzła. Możesz potrzebować stosu do przechowywania utworzonych węzłów, aby utworzyć lewe i prawe odsyłacze podrzędne.

Answer 3

Można użyć czegoś takiego. Najpierw pójdzie stara głębokość drzewa i utworzy jego kopię.

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

Answer 4

Lubię odpowiedź Evgeniy Dorofeev jest wyżej, ale czasami może nie być w stanie dodać metodę do rodzaju Node jak nie może jej właścicielem. W takim przypadku (to jest w języku 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; 
} 

Answer 5

Wykonuje to rekurencyjnie, korzystając z przeniesienia zamówienia przed zamówienia.

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; 
    } 

Answer 6

public static TreeNode copy(TreeNode source) 
    { 
     if(source == null) 
     return null; 
     else 
     return new TreeNode(source.getInfo(), copy(source.getLeft()), copy(source.getRight())); 
    } 

/Jasne. Przepraszam za opóźnienie. W każdym razie ... każda metoda rekurencyjna ma przypadek podstawowy i jeden lub więcej przypadków rekursywnych. W tym przypadku pierwsza linia jest oczywista ... jeśli argument parametru "source" ma wartość NULL (ponieważ w końcu zostanie obliczona, aby zakończyć działanie metody), zwróci wartość null; jeśli nie, inicjowana jest sprawa rekursywna. W takim przypadku zwracasz całe skopiowane drzewo po zakończeniu rekurencji. Używany jest operator "nowy", który wskazuje instancję TreeNode przy każdej wizycie w różnych węzłach drzewa podczas przejścia, występujący poprzez rekursywne wywołania "copy", którego argumenty stają się odniesieniami do lewego i prawego TreeNodes (jeśli są jakieś). Gdy w każdym argumencie źródło stanie się puste, inicjowana jest podstawowa sprawa, zwalniając stos rekursji z powrotem do pierwotnego wywołania "kopiuj", które jest kopią korzenia pierwotnego drzewa./