爲二叉搜索樹實現添加方法

Question

我的合作伙伴和我正在爲數據結構實現二叉搜索樹&算法課程。我們遇到的問題與我們的添加方法。此代碼如下所示：

public class BinarySearchTree<Type extends Comparable<? super Type>> implements SortedSet<Type> 
{ 


BinaryNode<Type> thisRoot; 

/** 
* Constructor for this BinarySearchTree 
*/ 
public BinarySearchTree() 
{ 
    thisRoot = null; 
} 

/** 
* Adds the specified item to this BinarySearchTree, if it is 
* not already contained in this BinarySearchTree. 
* 
* @param Type item 
* 
* @return boolean 
*/ 
public boolean add(Type item) { 

    // If the specified item is null, throw an exception. 
    if(item == null) 
     throw new NullPointerException(); 

    // Otherwise, add the item. 
    return addItem(item, thisRoot); 

} 

private boolean addItem(Type item, BinaryNode<Type> thisRoot) 
{ 
    // Base case - check if thisRoot is null. If it is null, 
    // we have reached the base case where the item is not contained 
    // in this BinarySearchTree. Insert the item. 
    if(thisRoot == null) 
    { 
     thisRoot = new BinaryNode<Type>(item); 
     return true; 
    } 

    // Reduction step - recursively call the helper method until the 
    // specified item is found or added. 

    // If the item is less than the data in thisNode, then go to 
    // the left in this BinarySearchTree. 
    if(item.compareTo(thisRoot.getData()) < 0) 
     return addItem(item, thisRoot.getLeft()); 

    // If the item is greater than the data in thisNode, then go 
    // to the right in this BinarySearchTree. 
    else if (item.compareTo(thisRoot.getData()) > 0) 
     return addItem(item, thisRoot.getRight()); 
    else 
     // Item is already contained in this BinarySearchTree. 
     return false; 

} 

在我們的測試案例中，我們沒有得到我們預期的結果。我們最初創建了一個空的BinarySearchTree，並調用添加方法。從這裏我們將一個Integer對象（10）傳遞給該方法。這樣做後，遞歸的addItem方法應該已被調用。 thisRoot當前應該引用null（因爲我們創建了一個空的BinarySearchTree），因此thisRoot現在應該引用新的BinaryNode對象。但是，方法調用後，BST中不包含10。 thisRoot仍然指向null。如果任何人有任何建議或見解，爲什麼這可能是，我們將不勝感激。

Answer 1

在addItem方法中，thisRoot只是一個局部變量（綁定到方法的第二個參數）。重置它除了在方法內部之外不會改變任何東西。您必須將您構造的new BinaryNode<Type>(item)分配給現有節點的左側或右側指針。

（如果我是模糊的，那是因爲我不想給出答案了。）

Answer 2

約在斯坦福大學網站BST好文章： http://cslibrary.stanford.edu/110/BinaryTrees.html#s1