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

Question

我正在观看来自 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

Answer 1

所以这是 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 就是为了达到这样的目的而设计的。它的数据在进行插入时被结构化以避免遍历整棵树的需要。它的值是有序的，因此在查找最小/最大值时不必遍历每个节点。如果你的算法需要，你没有正确使用它，即使函数产生了正确的逻辑输出。