java - 递归计算多态bst对象的深度

我正在尝试计算多态bst中的键的深度（不是空对象，而是用EmptyTrees表示空对象），而且我不确定如何实现实际代码。

private int calcDepth(K keyIn, int level){
 if (this.key.compareTo(keyIn) == 0) return level;

  if (this.key.compareTo(keyIn) < 0){
  return left.calcDepth(keyIn, level+1);
  }

  if (this.key.compareTo(keyIn) > 0){
  return right.calcDepth(keyIn, level+1);
  }

  return -1;
}

我对Java非常陌生，因此请原谅问题的基本性质或混淆性质

所以我的问题是，我该如何计算bst中的钥匙深度？

最佳答案

好的，问题出在calcDepth方法中的这两行代码，

return left.calcDepth(keyIn, level+1);

和

return right.calcDepth(keyIn, level+1);

您只能在具有calcDepth方法的对象上调用calcDepth。但是，由于calcDepth仅在NonEmptyTree中定义，当您到达分支的末尾并按下EmptyTree时会发生什么？这是您将收到错误的地方，因为EmptyTree没有此方法。这花了我一段时间，因为错误并没有说明这一点，但是由于它是Tree<K,V>的子类，因此将直接说该方法在超类中不存在。所以我有两个建议


将calcDepth方法放在您的超类Tree中，以便两个子类都可以访问它


要么


在进行递归调用之前，请首先检查left或right是EmptyTree。如果是，则在这种情况下返回level+1（假设您将空节点算作额外的级别，如果不是，则仅返回level）。