如果找不到节点，它应该在二叉搜索树中进入什么级别

Question

我正尝试在我的二叉搜索树中实现这个方法，它应该告诉我找到的元素的深度。

我的问题是如果找不到该元素，我应该如何搜索 return 它退出（或放置）的树级别。

即如果树中不存在该节点，则应将其插入树的级别 returned。如果在树中找不到该元素，我不想 return “0”，而是它应该放置的级别。

If I searched for "7", the method should return "3" because that is the level where the search stopped and where in theory the "7" would be added

这是我目前的代码，但它保持 returning 1.

public int depthSearch(Node root, int key){
    int depthLevel = 0;

    if (root==null || root.data==key){
        depthLevel++;
        return depthLevel;
    }

    if (root.data > key){
        depthSearch(root.left, key);
        depthLevel++;
        return depthLevel;
    }else{
        depthSearch(root.right, key);
        depthLevel++;
        return depthLevel;
    }
}

我的第二个问题是将深度级别计数器逻辑添加到我的查找方法是否有意义？

这是方法：

public boolean find(int id){
    Node current = root;
    while(current!=null){
        if(current.data==id){
            return true;
        }else if(current.data>id){
            current = current.left;
        }else{
            current = current.right;
        }
    }
    return false;
}

提前感谢您查看我的代码。我无法在 SO 上找到具有类似问题的线程。

Answer 1

My second question is would it make sense to add the depth level counter logic to my find method?

不，如果找到，此方法应该 return true，否则 false。您不能在 Java 中 return 多个值（您可以创建一个包含这两个值的对象，但那是……呃……）。但即使你可以 - 一个方法应该做一件事！

至于depthSearch执行有问题：您没有 return 递归调用的结果。

虽然可以轻松修复：

public int depthSearch(Node root, int key) {

    if (root == null || root.data == key) {
        return 1;
    }    
    else if (root.data > key) {
        return 1 + depthSearch(root.left, key);
    } else {
        return 1 + depthSearch(root.right, key);
    }
}

如果找不到节点，它应该在二叉搜索树中进入什么级别

If node not found, what level should it go in the Binary Search Tree

java

depth

binary-search-tree