必备的二叉搜索树方法:查找最小值节点

Question

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

public T min()

。设计一个交互版本的方法。

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

C。哪种方法更好?请解释。

这不是HW之类的，这是我自己的练习

Answer 1

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

注释之后，My way:

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

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

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
}

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

Answer 3

二叉搜索树的左边总是有一个较低的值，对吗?所以，你应该尽量往左边走。