在二元搜索树中,如果我们查看左孩子总是比父孩子小的属性,我们会发现,如果继续向左孩子迭代直到到达没有左孩子的节点,我们基本上会发现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; }