Java:查找 BST 中未找到的节点的深度

Question

我有一个存储在字符串中的二叉搜索树，并且我已经能够找到 BST 中存在的字符串的深度或高度，但我想要做的是找到深度是什么不在 BST 中的字符串。

这是我当前正在使用的算法，它非常适合查找 BST 中已存在的字符串的深度:

public int getDepth(String data) {
    return getDepth(root, data, 1);
}

public int getDepth(Node root, String data, int level) {
    if (root == null)
        return 0;

    if (root.getData().getName().equals(data))
        return level;

    int ret = getDepth(root.leftChild, data, level + 1);
    if (ret != 0)
        return ret;

    ret = getDepth(root.rightChild, data, level + 1);
    return ret;

}

我的 BST 具有按以下顺序插入的元素:“cat”、“bird”、“dog”、“tiger”、“elephant”、“panda”。

所以二叉树应该是这样的:

                                   cat
                                  /   \
                               bird   dog
                                         \
                                        tiger
                                       /     \
                                  elephant  panda

当我在“dog”上调用该方法时，输出为:dog 位于深度 2

当我调用“hippo”上的方法时，输出为:hippo 位于深度 0

但是“hippo”的预期输出应该是:hippo is at height 5

因为河马是大象的 child ，而大象的深度已经为 4。

那么对于另一种情况，如果我想找到不在BST中的“cow”的深度怎么办？它必须是狗的左 child ，所以深度应该是3，但是，我仍然得到0。

所以问题是在不使用删除和/或恢复方法的情况下，我需要什么情况或者我需要在上面的方法中修改什么情况才能确定不在内部的字符串的深度BST？

Answer 1

您需要模拟一个插入操作，该操作可以执行真正插入会执行的所有操作，只是它不会将新节点附加到树中并跟踪深度。
搜索插入新值的正确位置 - 从根开始，将值与当前节点进行比较，根据比较结果沿树向下下降。
一旦找到正确的位置，不要将值添加到树中，只返回深度。