二叉搜索树字符串 Insertion/Delete/Print

Question

我想使用 public 方法在此 BST 中插入、删除和打印字符串，而不是 boolean 或 void - 所以我必须return。

在我的插入方法中，我尝试检查 null 以及树的左侧和右侧。如果标签和字符串之间的比较是 < 0 我将 left 设置为当前节点的值。右边也一样。

我的问题是，我 return 在此方法的末尾做什么？我对这部分感到困惑，在这种情况下我 return 自己吗？

return false;

Answer 1

如果您想了解 BST 的稳健实现，这里有一个：

http://algs4.cs.princeton.edu/32bst/BST.java.html

此外，如果您想真正了解那里发生的事情和原因，我建议您也在那里学习 looking/reading 课程。

编辑：

嗯，首先，让我们在这里解决几个问题。

查看您的 class，您声称每个 Node 都是 Tree。现在，这可能是有道理的，但是使用 Tree 作为一组 linked Nodes 的包装应该是一种更简单的方法。
通俗点说，BST运算有两种方式，递归和迭代。我会给你一个例子。

迭代版本：

private void addIterative(T item) {
    if (root == null) {
        root = new Node(item);
        return;
    }

    Node parent = null;
    Node node = root;

    int cmp = 0;
    while (node != null) {
        cmp = item.compareTo(node.item);

        if (cmp == 0) {
            return;
        } else if (cmp < 0) {
            parent = node;
            node = node.left;
        } else {
            parent = node;
            node = node.right;
        }
    }

    Node child = new Node(item);

    if (cmp < 0) {
        parent.left = child;
    } else if (cmp > 0) {
        parent.right = child;
    }
}

递归版本：

private Node add(Node node, T item) {
    if (node == null) {
        return new Node(item);
    }

    int cmp = item.compareTo(node.item);

    if (cmp == 0) {
        // it already exists
    } else if (cmp < 0) {
        node.left = add(node.left, item);
    } else {
        node.right = add(node.right, item);
    }

    return node;
}

在迭代版本中，您使用循环在树中移动，一旦找到添加节点的位置，您只需创建并 link 它。

另一方面，递归版本可以说是自我构建的。在每次插入时，您都将 links 刷新到树下的那个路径。

因此，迭代 - 在 while 循环中遍历树；递归 - 通过递归调用在树中移动。

你的例子让我相信你打算使用迭代版本添加新元素。在那种情况下，您（我相信）只需要 return Tree 的实例来进行方法链接，因此您可以这样做：

node.insert("1").insert("2");

我仍然会建议你修改你看待 Nodes 和 Trees 的方式，但如果那不可能，那么我想你需要以某种方式解决它.

二叉搜索树字符串 Insertion/Delete/Print

Binary Search Tree String Insertion/Delete/Print

java

math

binary-search-tree