javascript - 在js中获取二叉搜索树的最大值

我将跟踪来自udemy的JS数据结构有关二进制搜索树的视频。我们有一种方法可以通过递归找到最大值。

我想更多地比较所有数字，例如

BST.prototype.getMaxVal = function() {
  let num = null;
  if (num === null) num = this.value;
  else if (this.value > num) num = this.value;
  if (this.left) return this.left.getMaxVal();
  return num;
}

但是答案是

BST.prototype.getMaxVal = function() {
  if (this.right) return this.right.getMaxVal();
  else return this.value;
}

105是没有自己的叶子的最后一个数字，但是此方法在它之前找到107？在没有任何比较逻辑的情况下如何找到它？

function BST(value) {
  this.value = value;
  this.left = null;
  this.right = null;
}

BST.prototype.insert = function(value) {
  if (value <= this.value) {
    if (!this.left) this.left = new BST(value);
    else this.left.insert(value);
  } else {
    if (!this.right) this.right = new BST(value);
    else this.right.insert(value);
  }

  return this;
}


const bst = new BST(50);

bst.insert(30);
bst.insert(70);
bst.insert(107);
bst.insert(60);
bst.insert(59);
bst.insert(20);
bst.insert(45);
bst.insert(35);
bst.insert(85);
bst.insert(105);
bst.insert(10);

bst.getMaxVal();

https://repl.it/repls/NumbYellowgreenPlans

最佳答案

这就是BST的视觉表示。如果某个值小于您，则将其传递到左侧，然后让左侧的子BST决定将其放置在何处。如果某个值大于您的值，则将其传递到正确的子BST上，然后让其决定将值放置在何处。



在此设置中，可以确保在最左边的叶子上它必须是最小值，而在最右边的叶子上它必须包含最大值。因此，从每一个BST的角度来看，这个想法都是关于他的左棵树什么都没有，或者它的值必须小于我。因此，算法写道：

BST.prototype.getMinVal = function() {
  // if left tree is not null, it must be smaller tha me. Return its value
  if (this.left) return this.left.getMinVal();
  // if left tree is null, indicate i'm the smallest available, return me instead.
  else return this.value;
}

更新1

有一件事情要注意。 BST旨在满足这样的目的。在进行插入时，其数据的结构避免了遍历整个树的需要。它的值是有序排列的，因此查找最小值/最大值时不必遍历每个节点。如果您的算法需要，则说明您没有正确使用它，即使该函数也会产生正确的逻辑输出。