为什么我需要一个辅助方法来递归搜索二叉搜索树？

Question

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

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 属性分开的指针，因此不会弄乱调用该方法的对象的根属性？

抱歉，如果问题看起来不是很直截了当，但如果有人能启发我了解幕后到底发生了什么，我将不胜感激。

Answer 1

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

为什么我需要一个辅助方法来递归搜索二叉搜索树？

Why do I need a helper method to recursively search a binary search tree?

java

recursion

helpermethods

binary-search-tree