Javascriptバイナリ検索ツリーで最小値と最大値を検索する

二分探索木で、左の子が常に親よりも小さいというプロパティを見ると、左の子に向かって反復し続けると、子が残っていないノードの場合、基本的にBSTで最小の要素が見つかります。

この関数をコードに実装しましょう。今後は、関数の単一バージョン、つまり反復または再帰のいずれかのみを実装します。この場合、反復関数を作成します-

例

getMinVal() {
   if (this.root === null) {
      throw "Empty tree!";
   }
   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 "Empty tree!";
}
let currNode = this.root;

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