我有一个存储在Strings中的二进制搜索树,我已经能够找到BST中存在的Strings的深度或高度,但是我想做的就是找到一个String的深度。不在BST中。

这是我当前正在使用的算法,可以完美地找到BST中已经存在的String的深度:

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


当我在“ dog”上调用方法时,输出为:dog在深度2

当我在“河马”上调用该方法时,输出为:河马深度为0

但是“河马”的预期输出应该是:河马深度为5

因为河马是大象的孩子,而大象已经深入4了。

那么对于另一种情况,如果我想找到不在BST中的“母牛”的深度怎么办?它必须是狗的左孩子,因此深度应为3,但是我仍然为0。

所以问题是,没有使用删除和/或恢复方法,我需要在上述方法中使用哪种情况,或者需要在哪种方法中进行修改,以便确定不在BST内的字符串的深度?

最佳答案

请尝试第二个getDepth()方法的以下修改版本:

public int getDepth(Node root, String data) {
    if (root == null || root.getData().getName().equals(data)) {
        // you hit the spot - either you are below a leaf
        // or you matched the node
        // if you were doing insert/replace, you would put the data on this spot
        return 0;
    }

    if (isSmallerThan(data, root.getData().getName())) {
        return 1 + getDepth(root.leftChild, data);
    }
    return 1 + getDepth(root.rightChild, data);
}


如果isSmallerThan(String a, String b)小于true,则a返回b。此方法取决于您希望如何比较字符串。

而且您不需要一直通过level ...

关于java - Java:查找未在BST中找到的节点的深度,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/26469169/

10-09 05:46
查看更多