如何在不使用递归方法的情况下找到二叉搜索树的节点

Question

如果我有一个只将值作为参数（而不是节点）的方法，称为 public Node finder (E val) 我如何找到相应的节点，而不管树的高度和宽度如何。如果该方法将 Node 作为参数，那么使用递归将是一个简单的解决方案。但不幸的是，我不允许更改方法签名。我怎样才能以聪明的方式而不是我在下面尝试的愚蠢方式来做到这一点，最终会得到大量嵌入式 if 函数

public class BinarySearchTree<E extends Comparable<E>> {
    class Node {
        E value;
        Node leftChild = null;
        Node rightChild = null;
        Node(E value) {
            this.value = value;
        }
    }

    public Node finder(E val) {
        
        if (val == null) return null;
        if (root == null) return null;
        
        boolean flag = false;  
        Node temp = root;
        
        //find if Root Node matches value
        if(temp.value.compareTo(val) == 0) {
            flag = true;
            return temp;
        } 
        //if value is less than root check the left branch
        else if (temp.value.compareTo(val) > 0) {
            
            if(temp.leftChild.value.compareTo(val) == 0) {
                flag = true;
                return temp.leftChild;
            } 
            //more if statements here
        } 
        //if value is more than root check the right branch 
        else {
            if(temp.rightChild.value.compareTo(val) == 0) {
                flag = true;
                return temp.rightChild;
            }
            
            //more if statements here
        }
        
        return null;
    }
}

Answer 1

二叉搜索树有这个有趣的东西属性:

一个节点的左子树只包含值小于该节点值的节点。
节点的右子树只包含值大于节点键的节点。

假设您的 class BinarySearchTree 持有对根的引用，您可以 迭代地遍历二叉树 直到达到值或达到叶节点，这意味着您的值不存在于您的二叉搜索树中。这个搜索操作的时间复杂度是O(log(n)).

这是一些伪代码

Find-Node(val):

    node = root
    while node != null:
      if val == node.val then return root
      if val < node.val then node = node.left
      if val > node.val then node = node.right

    return null

如何在不使用递归方法的情况下找到二叉搜索树的节点

How to find a Node of a Binary Search Tree without using a recursive method

java

tree

binary-tree

nodes