Implementieren eines binären Suchbaums in JavaScript

// Erstelle einen BinarySearchTree
Funktion BinarySerachTree() {
  //Erstelle eine Knotenkonstruktorfunktion Node(key) {
    dieser.Schlüssel = Schlüssel
    this.left = null
    dies.rechts = null
  }

  // Speichern Sie die Root-Eigenschaft this.root = null

  // Mit dem binären Suchbaum verbundene Operationsmethoden // Daten in den Baum einfügen BinarySerachTree.prototype.insert = function (key) {
    // 1. Erstellen Sie den entsprechenden Knoten entsprechend dem Schlüssel
    var neuer Knoten = neuer Knoten(Schlüssel)

    // 2. Bestimmen Sie, ob der Stammknoten einen Wert hat, wenn (this.root === null) {
      this.root = neuer Knoten
    } anders {
      dieser.insertNode(dieser.root, neuerNode)
    }
  }

  BinarySerachTree.prototype.insertNode = Funktion (Knoten, neuer Knoten) {
    if (newNode.key < node.key) { // 1. Bereiten Sie das Einfügen von Daten in den linken Teilbaum vor if (node.left === null) { // 1.1. Der linke Teilbaum des Knotens node.left = newNode enthält keinen Inhalt
      } else { // 1.2. Der linke Teilbaum des Knotens hat bereits Inhalt this.insertNode(node.left, newNode)
      }
    } else { // 2. Bereiten Sie das Einfügen der Daten in den rechten Teilbaum vor, if (node.right === null) { // 2.1. Es gibt keinen Inhalt im rechten Teilbaum des Knotens node.right = newNode
      } else { // 2.2. Es gibt Inhalt im rechten Teilbaum des Knotens this.insertNode(node.right, newNode)
      }
    }
  }

  // Holen Sie sich die Maximal- und Minimalwerte BinarySerachTree.prototype.min = function () {
    var Knoten = diese.Wurzel
    während (node.left !== null) {
      Knoten = Knoten.links
    }
    node.key zurückgeben
  }

  BinarySerachTree.prototype.max = Funktion () {
    var Knoten = diese.Wurzel
    während (node.right !== null) {
      Knoten = Knoten.rechts
    }
    node.key zurückgeben
  }

  //Suche nach einem bestimmten Wert/*
  BinarySerachTree.prototype.search = Funktion (Schlüssel) {
    gib diesen.searchNode(diesen.root, Schlüssel) zurück.
  }

  BinarySerachTree.prototype.searchNode = Funktion (Knoten, Schlüssel) {
    // 1. Wenn der übergebene Knoten null ist, dann beende die Rekursion, wenn (Knoten === null) {
      return false
    }

    // 2. Bestimme den Wert des Node und die Größe des übergebenen Schlüssels if (node.key > key) { // 2.1. Der übergebene Schlüssel ist kleiner, suche weiter nach links return this.searchNode(node.left, key)
    } else if (node.key < key) { // 2.2. Der übergebene Schlüssel ist größer, suche weiter nach rechts return this.searchNode(node.right, key)
    } else { // 2.3. Dasselbe, zeigt an, dass der Schlüssel gefunden wurde
      returniere wahr
    }
  }
  */
  BinarySerachTree.prototype.search = Funktion (Schlüssel) {
    var Knoten = diese.Wurzel
    während (Knoten !== null) {
      wenn (node.key > key) {
        Knoten = Knoten.links
      } sonst wenn (node.key < key) {
        Knoten = Knoten.rechts
      } anders {
        returniere wahr
      }
    }
    return false
  }

  // Löschen nodeBinarySerachTree.prototype.remove = Funktion (Schlüssel) {
    // 1. Den aktuellen Knoten abrufen
    var Knoten = diese.Wurzel
    var übergeordnetes Element = null

    // 2. Durchlaufen Sie die Knoten
    während (Knoten) {
      wenn (node.key > key) {
        übergeordneter Knoten = Knoten
        Knoten = Knoten.links
      } sonst wenn (node.key < key) {
        übergeordneter Knoten = Knoten
        Knoten = Knoten.rechts
      } anders {
        wenn (node.left == null und node.right == null) {

        }
      }
    }
  }

  BinarySerachTree.prototype.removeNode = Funktion (Knoten, Schlüssel) {
    // 1. Wenn der übergebene Knoten null ist, beenden Sie die Rekursion direkt.
    if (Knoten === null) return null

    // 2. Bestimmen Sie die Größe des Schlüssels und des entsprechenden node.key if (node.key > key) {
      node.left = this.removeNode(node.left, Schlüssel)

    }
  }

  // Knoten löschen BinarySerachTree.prototype.remove = function (key) {
    // 1. Definieren Sie temporär gespeicherte Variablen var current = this.root
    var übergeordnetes Element = diese.root
    var istLeftChild = true

    // 2. Beginnen Sie mit der Suche nach Knoten, während (current.key !== key) {
      übergeordnetes Element = aktuell
      if (Schlüssel < aktueller.Schlüssel) {
        istLeftChild = true
        aktuell = aktuell.links
      } anders {
        istLeftChild = false
        aktuell = aktuell.rechts
      }

      // Wenn Sie feststellen, dass current bereits auf null zeigt, bedeutet dies, dass die zu löschenden Daten nicht gefunden wurden, if (current === null) return false
    }

    // 3. Der gelöschte Knoten ist ein Blattknoten, wenn (current.left === null && current.right === null) {
      wenn (aktuell == diese.root) {
        this.root == null
      } sonst wenn (istLinkesKind) {
        übergeordnetes Element.links = null
      } anders {
        übergeordnetes Recht = null
      }
    }

    // 4. Lösche den Knoten mit einem untergeordneten Knoten, sonst wenn (current.right === null) {
      wenn (aktuell == diese.root) {
        diese.Wurzel = aktuell.links
      } sonst wenn (istLinkesKind) {
        übergeordnetes Element = aktuelles Element
      } anders {
        übergeordnetes Element: rechts = aktuell. links
      }
    } sonst wenn (current.left === null) {
      wenn (aktuell == diese.root) {
        diese.Wurzel = aktuell.rechts
      } sonst wenn (istLinkesKind) {
        übergeordnetes Element: links = aktuelles Element: rechts
      } anders {
        übergeordnetes Recht = aktuelles Recht
      }
    }

    // 5. Lösche den Knoten mit zwei Knoten sonst {
      // 1. Den Nachfolgeknoten abrufen var successor = this.getSuccessor(current)

      // 2. Bestimmen Sie, ob es sich um den Stammknoten handelt, wenn (current == this.root) {
        this.root = Nachfolger
      } sonst wenn (istLinkesKind) {
        parent.left = Nachfolger
      } anders {
        übergeordnetes Recht = Nachfolger
      }

      // 3. Weisen Sie den linken Teilbaum des gelöschten Knotens dem Nachfolger zu
      Nachfolger.links = aktuell.links
    }

    returniere wahr
  }

  // Finde den Nachfolger methodBinarySerachTree.prototype.getSuccessor = function (delNode) {
    // 1. Verwenden Sie Variablen, um temporäre Knoten zu speichern var successorParent = delNode
    var Nachfolger = delNode
    var current = delNode.right // Beginne mit dem rechten Teilbaum // 2. Suche den Knoten while (current != null) {
      successorParent = Nachfolger
      Nachfolger = aktuell
      aktuell = aktuell.links
    }

    // 3. Wenn du 15 in der Abbildung löschen möchtest, benötigst du zusätzlich folgenden Code if (successor != delNode.right) {
      NachfolgerParent.left = Nachfolger.right
      Nachfolger.rechts = delNode.rechts
    }
  }

  // Traversal-Methode // Handler ist eine Callback-Funktion // Pre-Order-Traversal BinarySerachTree.prototype.preOrderTraversal = function (handler) {
    this.preOrderTranversalNode(diese.root, Handler)
  }

  BinarySerachTree.prototype.preOrderTranversalNode = Funktion (Knoten, Handler) {
    if (node ​​​​!== null) {
      Handler (Knoten.Schlüssel)
      dies.preOrderTranversalNode(node.left, handler)
      this.preOrderTranversalNode(Knoten.rechts, Handler)
    }
  }

  // In-Order-TraversierungBinarySerachTree.prototype.inOrderTraversal = function (handler) {
    dies.inOrderTraversalNode(diese.root, Handler)
  }

  BinarySerachTree.prototype.inOrderTraversalNode = Funktion (Knoten, Handler) {
    if (node ​​​​!== null) {
      dies.inOrderTraversalNode(node.left, handler)
      Handler (Knoten.Schlüssel)
      dies.inOrderTraversalNode(node.right, handler)
    }
  }

  // Nachfolgende DurchquerungBinarySerachTree.prototype.postOrderTraversal = function (handler) {
    this.postOrderTraversalNode(this.root, Handler)
  }

  BinarySerachTree.prototype.postOrderTraversalNode = Funktion (Knoten, Handler) {
    if (node ​​​​!== null) {
      this.postOrderTraversalNode(Knoten.links, Handler)
      this.postOrderTraversalNode(node.right, handler)
      Handler (Knoten.Schlüssel)
    }
  }
  
  /*
  // Ergebnisse der Testdurchquerung (inOrderTraversal kann durch andere Durchquerungsmethoden ersetzt werden)
    Ergebniszeichenfolge = ""
    bst.inOrderTraversal(Funktion (Schlüssel) {
      resultString += Schlüssel + " "
    })
    alert(ErgebnisString) // 3 5 6 7 8 9 10 11 12 13 14 15 18 20 25 
   */
}