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;
}