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

Question

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

我的问题是如果没有找到该元素，我的搜索应该如何返回它退出(或放置)的树级别。

即如果树中不存在该节点，则应返回应将其插入的树的级别。如果在树中找不到该元素，我不想返回“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

这是我目前的代码，但它一直返回 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?

不，此方法应该在找到时返回 true，否则返回 false。您不能在 Java 中返回多个值(您可以创建一个对象来保存这两个值，但那是……呃……)。但即使你可以 - 一个方法应该只做一件事!

至于depthSearch 的实现有问题:您不会返回递归调用的结果。

虽然它很容易修复:

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);
    }
}