毎日5分間エンコードされる「Binary Search Tree」

≪バイナリ検索ツリー|Binary Search Tree|oraolap≫:ツリーの1つで、バイナリ検索ツリーには最大2つのサブツリーしかありません。

異メソッドではノードの値はソートメソッドの存在順であり、ノードの左サブツリーの値はノード値より小さく、右サブツリーの値はノード値より大きい.

ぐるりと回る

グラフィックは非線形構造であるため、特殊な方法ですべてのノードを参照します.検索順によっては、Depth First SearchとBreadth Firts Searchの2つの方法があります.木もグラフィックなので、2つの方法が使えます.

ナビゲーション方法

フォワードツアー:親->左->右

中尉回り:左->親->右

後続ツアー:左->右->親

巡回結果

フォワードツアー:6.42 5 9 8 11 13

中尉ツアー:2.45 6 8 9 10 11 13

後列巡り:25 4 8 10 13 11 9

Method

insert(value)-バイナリ・ツリーにノードを追加します.

contains(value)-バイナリナビゲーションツリーにノードが存在するかどうかを返します.

inorder(callback)-中尉はバイナリナビゲーションツリーを巡視する.

  insert(value) {
    let newnode = new BinarySearchTreeNode(value);
      if(this.value > value){
        if(this.left === null){
          this.left = newnode
        }else{
          return this.left.insert(value)
        }
      }
      else if(this.value < value){
        if(this.right === null){
          this.right = newnode
        }else{
          return this.right.insert(value)
        }
    }
  }

  contains(value) {
  if(this.value === value){
    return true;
  }else if(this.value < value){
    if(this.right === null){
      return false;
    }else if(this.right.contains(value)){
      return true;
    }
  }else if(this.value > value){
    if(this.left === null){
      return false;
    }else if(this.left.contains(value)){
      return true;
    }
  }
  return false;
}

inorder(callback) {//중위순회 왼 루트 오른쪽 
 if(this.left !== null){
   this.left.inorder(callback)
 }
 callback(this.value)
 if(this.right !== null){
   this.right.inorder(callback)
 }
}