1

下面是实现二叉搜索树的代码：

public class BST<T extends Comparable<T>> {

BSTNode<T> root;




public T search(T target)
{
    //loop to go through nodes and determine which routes to make
    BSTNode<T> tmp = root;
    while(tmp != null)
    {
        //c can have 3 values
        //0 = target found
        //(negative) = go left, target is smaller
        //(positive) = go left, target is greater than current position
        int c = target.compareTo(tmp.data);

        if(c==0)
        {
            return tmp.data;
        }
        else if(c<0)
        {
            tmp = tmp.left;
        }
        else
        {
            tmp = tmp.right;
        }

    }
    return null;
}

/*
 * Need a helper method
 */
public T recSearch(T target)
{
    return recSearch(target, root);

}

//helper method for recSearch()
private T recSearch(T target, BSTNode<T> root)
{
    //Base case
    if(root == null)
        return null;

    int c = target.compareTo(root.data);

    if(c == 0)
        return root.data;
    else if(c<0)
        return recSearch(target, root.left);
    else
        return recSearch(target, root.right);
}

为什么我需要递归辅助方法？为什么不能只使用“this.root”来执行正在发生的递归过程？此外，如果搞砸正在调用此方法的对象的根属性是一个问题，那么辅助方法如何防止这种情况发生？它是否只是创建了一个与 this.root 属性分开的指针，因此不会弄乱正在调用该方法的对象的根属性？

抱歉，如果这个问题看起来不直接，但如果有人能告诉我幕后究竟发生了什么，我将不胜感激。

4

1 回答 1

3

该方法需要一个起点。它需要有一个不变的目标节点，并且需要将它与其他一些节点进行比较以查看它们是否匹配让我们调用这个节点current而不是root因为它是递归方法正在评估的当前节点。在使用递归方法时，除了使用辅助函数并传入两个变量（许多递归方法都是这种情况）之外，确实没有一种简洁的方法可以做到这一点。正如你所说，如果你更新了根目录，你会在向左或向右移动时完全改变你的树，这是你不想做的。使用辅助函数是因为它为您的递归方法提供了一个起点。它还跟踪current您正在处理的节点，正如您所说，该方法指向正在评估的 Node 对象，但不进行任何更改。当向左或向右时，它不会修改任何内容，它只是传递对左节点或右节点的引用并继续执行此操作，直到找到目标或命中基本情况。

于 2015-10-09T01:54:15.560 回答