Làm thế nào để sao chép sâu một cây?

Question

Tôi muốn sử dụng lớp Node của riêng tôi để thực hiện cấu trúc cây trong Java. Nhưng tôi đang bối rối làm thế nào để làm một bản sao sâu để sao chép một cây.

My Node lớp sẽ là như thế này:

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

Tôi mới để đệ quy, như vậy là có bất kỳ mã tôi có thể học? Cảm ơn bạn!

Answer 1

thử

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

Không chắc chắn nhưng hãy thử điều gì đó với việc truyền tải thứ tự bài đăng của cây của bạn và tạo nút mới cho mỗi nút bạn đi qua. Bạn có thể yêu cầu ngăn xếp để lưu trữ các nút bạn đã tạo để tạo liên kết con bên trái và bên phải.

Answer 3

Bạn có thể sử dụng một cái gì đó như thế này. Nó sẽ đi mặc dù chiều sâu cây cũ đầu tiên khôn ngoan và tạo ra một bản sao của nó.

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

Tôi thích câu trả lời Evgeniy Dorofeev của trên, nhưng đôi khi bạn có thể không có thể thêm một phương pháp để loại Node như bạn có thể không sở hữu nó. Trong trường hợp đó (điều này là trong 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

Làm theo cách đệ quy sử dụng truyền tải đơn đặt hàng trước.

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

/chắc. Xin lỗi về sự chậm trễ. Dù sao ... bất kỳ phương pháp đệ quy nào cũng có trường hợp cơ bản và một hoặc nhiều trường hợp đệ quy. Trong trường hợp này, dòng đầu tiên là hiển nhiên ... nếu đối số cho tham số 'nguồn' là null (vì nó cuối cùng đánh giá để kết thúc hoạt động của phương thức), nó sẽ trả về null; nếu không, trường hợp đệ quy được bắt đầu. Trong trường hợp này, bạn sẽ trả lại toàn bộ cây đã sao chép khi quá trình đệ quy hoàn tất. Toán tử 'mới' được sử dụng, biểu thị sự khởi tạo của TreeNode với mỗi lần truy cập đến các nút khác nhau của cây trong quá trình truyền tải, xảy ra thông qua các cuộc gọi đệ quy đến 'sao chép', đối số của nó trở thành tham chiếu đến TreeNode trái và phải (nếu có bất kỳ). Khi nguồn trở thành null trong mỗi đối số, trường hợp cơ sở được bắt đầu, phát hành ngăn xếp đệ quy trở lại cuộc gọi ban đầu để 'sao chép', là bản sao gốc của cây gốc./