在Javascript二进制搜索树中搜索最小值和最大值

在二元搜索树中，如果我们查看左孩子总是比父孩子小的属性，我们会发现，如果继续向左孩子迭代直到到达没有左孩子的节点，我们基本上会发现BST中最小的元素。

让我们在代码中实现此功能。从现在开始，我们将仅实现该函数的单个版本，即迭代或递归。在这种情况下，我们将创建一个迭代函数-

示例

getMinVal() {
   if (this.root === null) {
      throw "空树！";
   }
   let currNode = this.root;

   while (currNode.left !== null) {
      currNode = currNode.left;
   }
   return currNode.data;
}

您可以使用以下方式进行测试：

示例

let BST = new BinarySearchTree();
BST.insertRec(10);
BST.insertRec(15);
BST.insertRec(5);
BST.insertRec(50);
BST.insertRec(3);
BST.insertRec(7);
BST.insertRec(12);
console.log(BST.getMinVal());

输出结果

这将给出输出-

3

同样，您可以扩展此代码以编写一个称为的函数getMaxVal()，该函数通过迭代最右边的子值来返回最大值。我们将代码放在这里供您验证-

示例

getMaxVal() {
if (this.root === null) {
      throw "空树！";
}
let currNode = this.root;

while (currNode.right !== null) {
   currNode = currNode.right;
}
   return currNode.data;
}