我有一个存储在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/