未按顺序搜索二进制搜索树

Question

i有一个由值x排序的对象的二进制搜索树（较低值x的对象添加到左侧，而较大的对象则在右侧）。

它们还具有尊敬的属性y。我将如何浏览树上的每个节点寻找匹配项？如果没有匹配，我将如何返回null？

我目前拥有的代码（确实确实有很多缺陷，因此我要问）是：

public BinaryTreeNode<E> inOrderIdSearch(BinaryTreeNode<E> n, int usrId) {
      if (n!=null) {
          inOrderIdSearch(n.getLeft(),usrId);
          if (n.getValue().getId() == usrId) {
            return n;
          }
          inOrderIdSearch(n.getRight(),usrId);
      }
      return null;
  }

Answer 1

假设您的树未在搜索的值中排序，您必须搜索每个节点，并且遍历的顺序无关紧要。因此，先搜索每个节点，然后再去孩子。另外，您需要返回递归电话的结果，而不是像上面的那样忽略它们。

public BinaryTreeNode<E> inOrderIdSearch(BinaryTreeNode<E> n, int usrId) {
    if (n==null) {
        return null;
    }
    if (n.getValue().getId() == usrId) {
        return n;
    }
    BinaryTreeNode<E> leftResult =inOrderIdSearch(n.getLeft(),usrId);    
    if (leftResult!=null) {
        return leftResult;
    }
    BinaryTreeNode<E> rightResult = inOrderIdSearch(n.getRight(),usrId);
    if (rightResult != null) {
        return rightResult;
    }
}

Answer 2

public BinaryTreeNode<E> inOrderIdSearch(BinaryTreeNode<E> n, int usrId) {
  if(n==null) return null;
  int candidate=n.getValue().getId();
  if(candidate==userId) return n;
  return inOrderIdSearch(candidate>userId?n.getLeft():n.getRight(),userId);
}