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

Question

我正在尝试计算多态 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 中键的深度？

Answer 1

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

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

和

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

您只能调用calcDepth在具有 calcDepth 的对象上方法。然而，因为calcDepth仅在 NonEmptyTree 中定义，当您到达分支末端并点击 EmptyTree 时会发生什么？这是您会收到错误的地方，因为 EmptyTree没有这个方法。我花了一段时间才意识到这一点，因为错误没有说明这一点，但因为它是 Tree<K,V> 的子类。 ，它会直接说该方法在父类(super class)中不存在。所以我有两个建议，要么

1. 输入 calcDepth父类(super class)中的方法 Tree这样两个子类都可以访问它

或

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