Java二叉搜索樹遞歸複製樹

我正在處理一個問題，它需要我遞歸複製二叉搜索樹並返回樹。我在二叉搜索樹類中編碼，所以它會複製它所調用的任何二叉搜索樹。要求說私有方法必須具有返回類型Entry<E>和類型Entry<E>的參數。我遇到的問題是將多個條目添加到樹中。Java二叉搜索樹遞歸複製樹

這是我目前有：

public BinarySearchTree<E> rcopy(){ 
    BinarySearchTree newTree = new BinarySearchTree(); 
    newTree.add(rcopy(root).element); 
    return newTree; 
} 


private Entry <E> rcopy(Entry <E> current){ 
    if(current.left!=null) return rcopy(current.left); 
    if(current.right!=null) return rcopy(current.right); 
    return current; 
}

這裏是入門級的，所以你知道我有什麼可以對我說：

protected static class Entry<E> { 
    protected E element; 
    protected Entry<E> left = null, 
         right = null, 
         parent; 
    protected int pos; 
protected Entry<E> link = null; 
public Entry() { } 
    public Entry (E element, Entry<E> parent) 
{ 
     this.element = element; 
     this.parent = parent; 
    } 
}

來源

2011-03-20 jbeverid

n00b - re：你提出的編輯：你可以發佈自己問題的答案，而不是編輯別人的答案。 – 2011-03-22 16:49:13

private Entry <E> rcopy(Entry <E> current){ 
    if(current.left!=null) return rcopy(current.left); 
    if(current.right!=null) return rcopy(current.right); 
    return current; 
}

這不會複製任何東西。它將返回當前節點的最左側（或最右側，如果沒有左側子節點;或當前節點，如果它是葉節點）子節點。因爲你總是迴流。你需要這樣的東西：

private Entry <E> rcopy(Entry <E> current){ 
    if (current == null) return null; 
    return new Entry <E> (current.element, rcopy(current.left), rcopy(current.right)); //write a constructor for that 
}

實際上覆制節點。我沒有測試過代碼，現在有點晚了，希望它仍然是正確的。

是否有理由區分BinarySearchTree<E>和Entry<E>？樹不是樹的一部分嗎？

來源

2011-03-21 00:19:20 paztulio

它看起來像你的代碼可以工作，除非它不是我的老師正在尋找的東西。我只允許編輯rcopy（）方法。 – jbeverid 2011-03-21 02:14:39

@ n00b：因此，爲節點創建一個新條目，遞歸複製左側和右側子樹，並將它們添加到節點。原理相同，只能在'rcopy'方法中使用。 – 2011-03-21 02:58:10

當然，我們可以爲您提供您所需要的解決方案，但是您什麼都不會學到。嘗試根據您的需求調整樣本。如果你陷入困境，你仍然可以再問。也許你想閱讀這篇文章：http://en.wikipedia.org/wiki/Tree_traversal – paztulio 2011-03-21 09:34:37

只是想我會分享我得到的解決方案。我的主要問題是沒有對對象進行深層複製，所以它會引用對象而不是創建新對象。

public BinarySearchTree<E> rcopy(){ 
    BinarySearchTree<E> newTree = new BinarySearchTree<E>(); 
    newTree.root = rcopy(root); 
    newTree.size=newTree.nodes(); 
    return newTree; 
} 
private Entry <E> rcopy(Entry <E> current){ 
    Entry <E> b=new Entry<E>(); 
    if(current!=null){ 
     if(current.left!=null)b.left=rcopy(current.left); 
     if(current.right!=null)b.right=rcopy(current.right); 
     b.element = current.element; 
     b.parent = successor(current); 
    } 
    return b; 
}

（繼任者是返回preceeds它的對象的條目的方法） 謝謝每一個與此問題的幫助！

來源

2011-03-23 03:31:32 jbeverid

Java二叉搜索樹遞歸複製樹

回答

相關問題