關於生成樹的recusive方法的問題

Question

我想了解一個簡單的拼寫檢查程序。該程序基本上讀取一個字典文件，把這些單詞放在一棵樹中。當它執行檢查功能時，它會從文件中一次一個字地檢查，並使用retrieve（）來查看這個單詞是否在樹中。

我的問題是，我不明白這個「添加」方法是如何工作的。它應該將字典中的單詞添加到樹結構中。你能幫我解釋一下這是如何工作的嗎？非常感謝！

private static BinarySearchTree<StringItem, String> tree = new BinarySearchTree<StringItem, String>(); 
    //Does this create a tree with StringItems as nodes? 
    //In which part does this method assign value to the tree nodes? 


    private static ArrayList<String> dictionary;//number is the number of strings in the dictionary 

    private static TreeNode<StringItem> add (int number) { // adds to the tree 
    //the numberOfWords has been counted in other methods. 

    if (numberOfWords < 1) { 
     return null; 
    } 

    TreeNode<StringItem> left = add(number/2); //What does this do? 

    StringItem word = new StringItem(dictionary.remove(0) + ""); 

    TreeNode<StringItem> right = add((number - 1)/2); 

    return new TreeNode<StringItem>(word, left, right); // I don't understand this part. 
    //which node are we returning here? 

} 

Answer 1

退房this真的普林斯頓由人書寫（在事實上好的執行二叉搜索樹的 - 檢查了所有他們已經公佈了各種的真的好的實現基本算法here）

我有點不清楚您的具體問題是什麼，但讓這個開始：

private static BinarySearchTree<StringItem, String> tree = ... 
//Does this create a tree with String items as nodes? 

如果你認爲BST更像是一個映射（一種類型的鍵映射到另一種類型的值），而不是簡單的單一類型對象列表，我認爲它會有所幫助。如果我們看一下連接到上面實施，我認爲這是一個有點清晰：

public class BST<Key extends Comparable<Key>, Value> { 
    private class Node { 
     private Key key;   // sorted by key 
     private Value val;   // associated data 
     private Node left, right; // left and right subtrees 
     private int N;    // number of nodes in subtree 
     ... 
    } 
    ... 
    private Node put(Node x, Key key, Value val) { 
     if (x == null) return new Node(key, val, 1); 
     int cmp = key.compareTo(x.key); 
     if  (cmp < 0) x.left = put(x.left, key, val); 
     else if (cmp > 0) x.right = put(x.right, key, val); 
     else    x.val = val; 
     x.N = 1 + size(x.left) + size(x.right); 
     return x; 
    } 
    ... 
} 

注意，類型參數被明確命名Key和Value這裏，應該加強什麼，我說以上。還要注意，一個Node包含一個值和值 - 值是「有效負載」，實際數據被存儲，而密鑰用於排序和組織樹（因此Key必須實現Comparable）。順便說一句，注意，不是add()，這裏的等效方法被稱爲put()，我認爲這是很清晰，因爲我們習慣叫上列出put(k, v)地圖狀結構和add(t)（我不知道這是否可能有在你的困惑中扮演角色）

就像我說的，雖然我不完全確定你對此感到困惑。我已經說過我在這裏所說的內容，因爲它好像是在具體詢問類型參數，但是您不清楚其他內容是否發佈了評論，我會更新。 （這就是說，我將上面的整個方法都包括進去了，因爲如果你真正想了解的是BSTs的一般功能，那麼這是一個非常重要的方法。仔細檢查每一行是什麼這樣做，爲什麼這樣做，然後做同樣的get()，你會在你的路上）。