java - 需要二叉搜索树方法：找到最小值节点

Question

任何人都可以帮助我做到这一点：我需要一个用于二叉搜索树 ADT 的公共方法，该方法返回对树中具有最小值的节点中的信息的引用。该方法的签名是：

公共 T min()

A. 设计该方法的交互式版本。

B. 设计该方法的递归版本。

C. 哪种方法更好？请解释。

这不是硬件或任何东西，它是我自己的练习。

Answer 1

因为我认为如果我给你的解决方案你不会学习，我会给你一个链接阅读更多关于二叉搜索树：http ://en.wikipedia.org/wiki/Binary_search_tree

在那条评论之后，我的方式：

public T min() {
    return recMin(root).getInfo();
}

public BSTnode<T> recMin(BSTnode<T> tree) {
    if (tree == null) {
        throw new NoSuchElementException();
    }
    if (tree.left == null) {
        return tree;
    }
    return recMin(tree.left);
}

public T IterationMin(BSTnode<T> tree) {
    if (tree == null) {
        throw new NoSuchElementException();
    }

    while (tree.left != null) {
        tree = tree.left;
    }
    return tree.getInfo();
}

Answer 2

二叉搜索树总是在左边有一个较低的值，对吗？所以，你应该尽可能向左走。如果你不能，那么你已经达到了最低值。

Answer 3

关于迭代或递归更好的问题。这真的取决于。一般来说，递归解决方案往往更容易理解，但速度较慢，因为它们消耗的堆栈空间与递归深度成正比。但是，在这种情况下，您可以提出一个尾递归解决方案，该解决方案应该易于理解并且与迭代解决方案一样有效。

public BSTNode<T> findMin(BSTNode<T> node) {
    if (node.left == null)     // if there is no left, we are done
        return node;
    return findMin(node.left); // recursively search on the left-child
}

首先在头节点上调用此方法。