JavaScript で二分探索木を実装する

// BinarySearchTree を作成する
関数 BinarySerachTree() {
  // ノードコンストラクタ関数を作成する Node(key) {
    this.key = キー
    this.left = null
    this.right = null
  }

  // ルートプロパティを保存します this.root = null

  // 二分探索木関連の操作メソッド // 木にデータを挿入する BinarySerachTree.prototype.insert = function (key) {
    // 1. キーに応じて対応するノードを作成する
    var newNode = 新しいノード(キー)

    // 2. ルートノードに値があるかどうかを判定する if (this.root === null) {
      this.root = 新しいノード
    } それ以外 {
      this.insertNode(this.root、newNode) は、
    }
  }

  BinarySerachTree.prototype.insertNode = 関数 (ノード、newNode) {
    if (newNode.key < node.key) { // 1. 左のサブツリーにデータを挿入する準備をする if (node.left === null) { // 1.1. ノードの左のサブツリーにコンテンツがない node.left = newNode
      } else { // 1.2. ノードの左のサブツリーにはすでにコンテンツがあります this.insertNode(node.left, newNode)
      }
    } else { // 2. 右サブツリーにデータを挿入する準備をする if (node.right === null) { // 2.1. ノードの右サブツリーにコンテンツがない node.right = newNode
      } else { // 2.2. ノードの右サブツリーにコンテンツがある this.insertNode(node.right, newNode)
      }
    }
  }

  // 最大値と最小値を取得する BinarySerachTree.prototype.min = function () {
    var ノード = this.root
    (node.left !== null) の間 {
      ノード = ノード.左
    }
    ノードキーを返す
  }

  BinarySerachTree.prototype.max = 関数 () {
    var ノード = this.root
    (node.right !== null) の間 {
      ノード = ノード.right
    }
    ノードキーを返す
  }

  //特定の値を検索/*
  BinarySerachTree.prototype.search = 関数 (キー) {
    this.searchNode(this.root, key) を返します。
  }

  BinarySerachTree.prototype.searchNode = 関数 (ノード、キー) {
    // 1. 渡されたノードがnullの場合、再帰を終了します。if (node ​​=== null) {
      偽を返す
    }

    // 2. ノードの値と渡されたキーのサイズを決定します。if (node.key > key) { // 2.1. 渡されたキーの方が小さいので、左に検索を続けます。return this.searchNode(node.left, key)
    } else if (node.key < key) { // 2.2. 渡されたキーの方が大きい場合は、右方向に検索を続けます。 return this.searchNode(node.right, key)
    } else { // 2.3. 同じ、キーが見つかったことを示す
      真を返す
    }
  }
  */
  BinarySerachTree.prototype.search = 関数 (キー) {
    var ノード = this.root
    while (ノード ​​!== null) {
      （ノード.キー>キー）の場合{
        ノード = ノード.左
      } それ以外の場合 (node.key < key) {
        ノード = ノード.right
      } それ以外 {
        真を返す
      }
    }
    偽を返す
  }

  // 削除 nodeBinarySerachTree.prototype.remove = function (key) {
    // 1. 現在のノードを取得する
    var ノード = this.root
    var 親 = null

    // 2. ノードをループする
    while (ノード) {
      （ノードキー＞キー）の場合{
        親 = ノード
        ノード = ノード.左
      } それ以外の場合 (node.key < key) {
        親 = ノード
        ノード = ノード.right
      } それ以外 {
        （node.left == null && node.right == null）の場合{

        }
      }
    }
  }

  BinarySerachTree.prototype.removeNode = 関数 (ノード、キー) {
    // 1. 渡されたノードが null の場合、再帰を直接終了します。
    if (node ​​=== null) は null を返す

    // 2. キーと対応するnode.keyのサイズを決定します。if (node.key > key) {
      node.left = this.removeNode(node.left, キー)

    }
  }

  // ノードを削除する BinarySerachTree.prototype.remove = function (key) {
    // 1. 一時保存変数を定義する var current = this.root
    var 親 = this.root
    var isLeftChild = true

    // 2. ノードの検索を開始する while (current.key !== key) {
      親 = 現在
      if (キー < 現在のキー) {
        左の子 = true
        現在の = 現在の左
      } それ以外 {
        isLeftChild = false
        現在の = 現在の右
      }

      // current がすでに null を指していることがわかった場合、削除するデータが見つからないことを意味します if (current === null) return false
    }

    // 3. 削除されたノードはリーフノードです if (current.left === null && current.right === null) {
      (現在の値 == this.root) の場合 {
        this.root == null
      } それ以外の場合 (isLeftChild) {
        親.左 = null
      } それ以外 {
        親.right = null
      }
    }

    // 4. 子ノードを1つ持つノードを削除します。else if (current.right === null) {
      (現在の値 == this.root) の場合 {
        this.root = 現在の左
      } それ以外の場合 (isLeftChild) {
        親.左 = 現在の.左
      } それ以外 {
        親.右 = 現在の.左
      }
    } それ以外の場合 (current.left === null) {
      (現在の値 == this.root) の場合 {
        this.root = 現在の右
      } それ以外の場合 (isLeftChild) {
        親.左 = 現在の.右
      } それ以外 {
        親.右 = 現在の.右
      }
    }

    // 5. 2つのノードを持つノードを削除します。else {
      // 1. 後継ノードを取得する var successor = this.getSuccessor(current)

      // 2. ルートノードかどうかを判定する if (current == this.root) {
        this.root = 後継
      } それ以外の場合は (isLeftChild) {
        親.左 = 後継
      } それ以外 {
        親.右 = 後継者
      }

      // 3. 削除されたノードの左サブツリーを後続ノードに割り当てる
      後継.左 = 現在の.左
    }

    真を返す
  }

  // 後継ノードを見つける methodBinarySerachTree.prototype.getSuccessor = function (delNode) {
    // 1. 変数を使用して一時ノードを保存する var successorParent = delNode
    var 後継者 = delNode
    var current = delNode.right // 右のサブツリーから開始 // 2. ノードを検索 while (current != null) {
      後継者親 = 後継者
      後継者 = 現在
      現在の = 現在の左
    }

    // 3. 図の15を削除する場合は、次のコードも必要です。if (successor != delNode.right) {
      後継親.左 = 後継右
      successor.right = delNode.right
    }
  }

  // トラバーサルメソッド // ハンドラはコールバック関数 // 事前順序トラバーサル BinarySerachTree.prototype.preOrderTraversal = function (handler) {
    this.preOrderTranversalNode(this.root、ハンドラー)
  }

  BinarySerachTree.prototype.preOrderTranversalNode = 関数 (ノード、ハンドラー) {
    if (ノード !== null) {
      ハンドラ(node.key)
      this.preOrderTranversalNode(node.left、ハンドラー)
      this.preOrderTranversalNode(node.right、ハンドラー)
    }
  }

  // 順序付きトラバーサルBinarySerachTree.prototype.inOrderTraversal = function (handler) {
    this.inOrderTraversalNode(this.root、ハンドラー)
  }

  BinarySerachTree.prototype.inOrderTraversalNode = 関数 (ノード、ハンドラー) {
    if (ノード !== null) {
      this.inOrderTraversalNode(node.left、ハンドラー)
      ハンドラ(node.key)
      this.inOrderTraversalNode(node.right、ハンドラー)
    }
  }

  // 後続のトラバーサルBinarySerachTree.prototype.postOrderTraversal = function (handler) {
    this.postOrderTraversalNode(this.root、ハンドラー)
  }

  BinarySerachTree.prototype.postOrderTraversalNode = 関数 (ノード、ハンドラー) {
    if (ノード !== null) {
      this.postOrderTraversalNode(node.left、ハンドラー)
      this.postOrderTraversalNode(node.right、ハンドラー)
      ハンドラ(node.key)
    }
  }
  
  /*
  // トラバーサル結果をテストします (inOrderTraversal は他のトラバーサル メソッドに置き換えることができます)
    結果文字列 = ""
    bst.inOrderTraversal(関数 (キー) {
      結果文字列 += キー + " "
    })
    アラート(結果文字列) // 3 5 6 7 8 9 10 11 12 13 14 15 18 20 25 
   */
}