Binärer Suchbaum in Javascript

Implementierung eines binären Suchbaums in JavaScript

In diesem Beitrag erfahren Sie, wie Sie einen einfachen binären Suchbaum (BST) in JavaScript implementieren. Wir behandeln das Einfügen von Knoten und die Durchführung verschiedener Baumdurchquerungsmethoden – in der Reihenfolge, vor der Bestellung und nach der Bestellung.

Die Knotenklasse
Definieren wir zunächst eine Node-Klasse, um jeden Knoten im Baum darzustellen:

class Node {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

Jedes Node-Objekt hat drei Eigenschaften:

• Wert: Die im Knoten gespeicherten Daten.
• links: Ein Zeiger auf den linken untergeordneten Knoten.
• rechts: Ein Zeiger auf den rechten untergeordneten Knoten.

Die BinarySearchTree-Klasse

Als nächstes definieren wir eine BinarySearchTree-Klasse, die die Knoten verwaltet und Methoden für die Interaktion mit dem Baum bereitstellt:

class BinarySearchTree {
    constructor() {
        this.root = null;
    }

    isEmpty() {
        return this.root === null;
    }

    insertNode(root, newNode) {
        if(newNode.value < root.value) {
            if(root.left === null) {
                root.left = newNode;
            } else {
                this.insertNode(root.left, newNode);
            }
        } else {
            if(root.right === null) {
                root.right = newNode;
            } else {
                this.insertNode(root.right, newNode);
            }
        }
    }

    search(root, value) {
        if(!root) {
            return false;
        }
        if(root.value === value) {
            return true;
        } else if(root.value > value) {
            return this.search(root.left, value);
        } else {
            return this.search(root.right, value);
        }
    }

    insert(value) {
        const newNode = new Node(value);
        if(this.isEmpty()) {
            this.root = newNode;
        } else {
            this.insertNode(this.root, newNode);
        }
    }
}

Schlüsselmethoden:

• isEmpty(): Prüft, ob der Baum leer ist.
• insertNode(root, newNode): Fügt einen neuen Knoten in den Baum ein und behält dabei die binäre Suchbaumeigenschaft bei.
• search(root, value): Sucht rekursiv nach einem Wert im Baum.
• insert(value): Eine praktische Methode, um einen neuen Wert in den Baum einzufügen.

Baumdurchquerungsmethoden

Sobald wir einen Baum haben, müssen wir ihn oft durchqueren. Hier sind die drei gängigen Traversal-Methoden:

In-order Traversal

In-Order-Traversierung besucht die Knoten in der folgenden Reihenfolge: Links, Wurzel, Rechts.

inOrder(root) {
    if(root) {
        this.inOrder(root.left);
        console.log(root.value);
        this.inOrder(root.right);
    }
}

Dieser Durchlauf druckt die Knoten in nicht absteigender Reihenfolge für einen binären Suchbaum.

Traversal vorbestellen

Bei der Vorbestellungsdurchquerung werden die Knoten in der folgenden Reihenfolge besucht: Root, Left, Right.

preOrder(root) {
    if(root) {
        console.log(root.value);
        this.preOrder(root.left);
        this.preOrder(root.right);
    }
}

Dieser Durchlauf ist nützlich zum Kopieren der Baumstruktur.

Post-Order-Traversal

Post-Order-Traversal besucht die Knoten in der folgenden Reihenfolge: Links, Rechts, Wurzel.

postOrder(root) {
    if(root) {
        this.postOrder(root.left);
        this.postOrder(root.right);
        console.log(root.value);
    }
}

Dieser Durchlauf wird häufig zum Löschen oder Freigeben von Knoten verwendet.

Beispielverwendung

Sehen wir uns an, wie diese Methoden zusammenarbeiten:

const bst = new BinarySearchTree();
bst.insert(10);
bst.insert(5);
bst.insert(20);
bst.insert(3);
bst.insert(7);

console.log('In-order Traversal:');
bst.inOrder(bst.root);

console.log('Pre-order Traversal:');
bst.preOrder(bst.root);

console.log('Post-order Traversal:');
bst.postOrder(bst.root);

Fazit

Mit dieser Implementierung können Sie jetzt einen binären Suchbaum in JavaScript erstellen und damit interagieren. Das Verständnis von Baumstrukturen und Traversierungsmethoden ist für viele algorithmische Probleme von entscheidender Bedeutung, insbesondere in Bereichen wie Suchalgorithmen, Parsen von Ausdrücken und Verwalten hierarchischer Daten.

Das obige ist der detaillierte Inhalt vonBinärer Suchbaum in Javascript. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!