search - 二叉搜索树中的搜索操作

Question

在二叉搜索树（递归或循环）中，哪个更好地实现搜索操作？

Answer 1

如果您想搜索，则无需递归。对于这种情况，递归将是一种矫枉过正。只需编写一个循环并在找到时中断或在叶节点处中断（如果未找到）

Answer 2

我通常发现递归更容易实现，并且至少使用树，使您的代码对其他人更具可读性。但最后这取决于你的树是否平衡

• 如果你的树是平衡的，那么我认为你肯定可以使用递归，因为你可以保证递归调用不会超过 log(n) （例如，对于 n=100000000，你必须进行的递归调用的最差数量只有 27 左右）

• 另一方面，如果您的树不平衡，那么我认为循环是您最好的选择，因为您可能必须检查树的所有元素，并且递归将使用大量内存来维护堆栈。

Answer 3

Assuming you have an entity class BinaryTreeNode, here is the non-recursive implementation of searching a node in Binary Search Tree:

public static BinaryTreeNode searchBstNode(BinaryTreeNode temp, int data){

    while(true){
        if(temp.getData()==data){
            break;
        }
        if(temp.getData()>data){
            if(temp.getLeft()!=null){
                temp=temp.getLeft();    
            }
            else{
                System.out.println("Data value ="+ data+" not found!");
                return null;
            }   
        }
        if(temp.getData()<data){
            if(temp.getRight()!=null){
                temp=temp.getRight();
            }
            else{
                System.out.println("Data value ="+ data+" not found!");
                return null;
            }

        }
    }
    System.out.println("Data found in the BST");
    return temp;

Answer 4

While(current != null) 作品。

public class BST<E extends Comparable<E>> 
  extends AbstractTree<E> {

  protected TreeNode<E> root;

  protected int size = 0;

~ ~ ~ ~

// Returns true if the element is in the tree 
  public boolean search(E e) {
    TreeNode<E> current = root; // Start from the root

    while (current != null) {
      if (e.compareTo(current.element) < 0) {
        current = current.left;
      }
      else if (e.compareTo(current.element) > 0) {
        current = current.right;
      }
      else // element matches current.element
        return true; // Element is found
    }

    return false;
  }

Answer 5

什么是最好的算法将取决于我们要解决的问题的上下文。这个 wiki 页面显示了这两者之间的良好 com 监狱。希望这会有所帮助。 http://en.wikipedia.org/wiki/Binary_search_algorithm