java - 关于生成树的递归方法的问题

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) 在类似 map 的结构上，add(t) 在列表上(我想知道这是否在您的困惑中发挥了作用)

就像我说的，我不完全确定你感到困惑的是什么。我已经说过我在这里所说的，因为看起来您是在专门询问类型参数，但您不清楚其他内容，请发表评论，我会更新。

(也就是说，我包含了上面的整个方法，因为如果您真正想要了解的是 BST 的一般功能，那么这是一个非常重要的理解方法。仔细检查并弄清楚每一行到底在做什么以及为什么要这样做。然后对 get() 执行相同的操作，您就可以上路了)。