Landy Blog
0%

資料結構-Binary Search Tree - getMinVal && getMaxVal

發表於 更新於 分類於 ，
紀錄 Binary Search Tree 取得最大值 和 取得最小值 的實作

程式碼如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// ...
BST.prototype.getMinVal = function() {
  if(this.left) return this.left.getMinVal();
  else return this.value;
}

BST.prototype.getMaxVal = function() {
  if(this.right) return this.right.getMaxVal();
  else return this.value;
}

const bst = new BST(50);
bst.insert(30);
bst.insert(70);
bst.insert(1000);
bst.insert(-1);
console.log('MIN', bst.getMinVal()); // -1
console.log('MAX', bst.getMaxVal()); // 1000

getMinVal 的做法就是一直去判斷是否當前被遍歷到的 node 還有沒有 left-side child node，
若有，就往下遍歷到 left-side node，
若沒有，就代表這個 node 是 tree 的最左邊且最末端的 node，也就是最小值的 node。

getMaxVal 的做法就是一直去判斷是否當前被遍歷到的 node 還有沒有 right-side child node，
若有，就往下遍歷到 right-side node，
若沒有，就代表這個 node 是 tree 的最右邊且最末端的 node，也就是最大值的 node。