Wie erstelle und durchlaufe ich einen Binärbaum in Javascript? (Codebeispiel)

In diesem Artikel erfahren Sie, wie Sie mit JavaScript einen Binärbaum erstellen und durchlaufen. Es hat einen gewissen Referenzwert. Freunde in Not können sich darauf beziehen. Ich hoffe, es wird für alle hilfreich sein.

1. Lassen Sie uns zuerst über die Durchquerung des Binärbaums sprechen:

Vorbestellungsdurchquerung: Durchqueren Sie zuerst den Wurzelknoten und dann den linken Teilbaum , und dann der rechte Teilbaum.

Durchquerung in der Reihenfolge: Zuerst den linken Teilbaum durchqueren, dann den Wurzelknoten, dann den rechten Teilbaum

Nachfolgende Durchquerung: Zuerst den linken Teilbaum durchqueren, dann der rechte Teilbaum, dann der Wurzelknoten

Der obige Code: hauptsächlich unter Verwendung von Rekursion

function TreeCode() {
    let BiTree = function (ele) {
        this.data = ele;
        this.lChild = null;
        this.rChild = null;
    }

    this.createTree = function () {
        let biTree = new BiTree('A');
        biTree.lChild = new BiTree('B');
        biTree.rChild = new BiTree('C');
        biTree.lChild.lChild = new BiTree('D');
        biTree.lChild.lChild.lChild = new BiTree('G');
        biTree.lChild.lChild.rChild = new BiTree('H');
        biTree.rChild.lChild = new BiTree('E');
        biTree.rChild.rChild = new BiTree('F');
        biTree.rChild.lChild.rChild = new BiTree('I');
        return biTree;
    }
}

//前序遍历
function ProOrderTraverse(biTree) {
    if (biTree == null) return;
    console.log(biTree.data);
    ProOrderTraverse(biTree.lChild);
    ProOrderTraverse(biTree.rChild);
}

//中序遍历
function InOrderTraverse(biTree) {
    if (biTree == null) return;
    InOrderTraverse(biTree.lChild);
    console.log(biTree.data);
    InOrderTraverse(biTree.rChild);
}

//后续遍历
function PostOrderTraverse(biTree) {
    if (biTree == null) return;
    PostOrderTraverse(biTree.lChild);
    PostOrderTraverse(biTree.rChild);
    console.log(biTree.data);
}

let myTree = new TreeCode();
console.log(myTree.createTree());
console.log('前序遍历')
ProOrderTraverse(myTree.createTree());
console.log('中序遍历')
InOrderTraverse(myTree.createTree());
console.log('后续遍历')
PostOrderTraverse(myTree.createTree());

Nicht rekursives Durchlaufen von Binärbäumen

• Tiefenorientierte Durchquerung (hauptsächlich unter Verwendung des First-in-Last-out des Stapels)

• Breitenorientierte Durchquerung (hauptsächlich unter Verwendung von (das First-In-First-Out der Warteschlange)

//深度优先非递归
function DepthFirstSearch(biTree) {
    let stack = [];
    stack.push(biTree);

    while (stack.length != 0) {
        let node = stack.pop();
        console.log(node.data);
        if (node.rChild) {
            stack.push(node.rChild);
        }
        if (node.lChild) {
            stack.push(node.lChild);
        }

    }

}


//广度优先非递归
function BreadthFirstSearch(biTree) {
    let queue = [];
    queue.push(biTree);
    while (queue.length != 0) {
        let node = queue.shift();
        console.log(node.data);
        if (node.lChild) {
            queue.push(node.lChild);
        }
        if (node.rChild) {
            queue.push(node.rChild);
        }
    }

}

Tiefenpriorität verwendet hauptsächlich den Stapel, wobei zuerst der rechte Teilbaum und dann der linke Teilbaum gedrückt wird

Breitenpriorität Verwendet hauptsächlich die Warteschlange und gibt zuerst den linken Teilbaum und dann den rechten Teilbaum ein

Tiefenpriorität Das Durchlaufergebnis ist das gleiche wie das Durchlaufergebnis vor der Bestellung ABDGHCEIF, und das Durchlaufergebnis in der Breite zuerst ist ABCDEFGHI

2. Erstellen Sie einen Binärbaum

Die Methode zum Erstellen eines Binärbaums in 1 ist zu umständlich und für uns falsch. Erstellen Sie Ihren eigenen Binärbaum basierend auf dem vollständigen Binärbaum Modell. Wie in der Abbildung unten dargestellt, nennen wir es einen erweiterten Binärbaum. Wir nehmen die Sequenz AB#D##C## der Vorbestellungsdurchquerung.

Der obige Code: verwendet auch Rekursion

//前序遍历得到的字符串
let strArr = 'AB#D##C##'.split('');

function BiTree(ele) {
    this.data = ele;
    this.lChild = null;
    this.rChild = null;
}
var newTree = new BiTree('#');

function createBiTree(biTree) {
    if (strArr.length == 0) return;
    let str = strArr.shift();
    if (str == '#') return;
    biTree.data = str;
    if (strArr[0] != '#') {
        biTree.lChild = new BiTree('#')
    }
    createBiTree(biTree.lChild);
    if (strArr[0] != '#') {
        biTree.rChild = new BiTree('#')
    }
    createBiTree(biTree.rChild);
}
createBiTree(newTree);
console.log(newTree);
ProOrderTraverse(newTree)

Sie können auch In-Order-Traversal oder Post-Order-Traversal verwenden, um einen Binärbaum zu erstellen generiert Knoten und tauscht einfach die Reihenfolge der Codes zum Erstellen der linken und rechten Teilbäume aus

Empfohlenes Tutorial: „JavaScript-Video-Tutorial“

Das obige ist der detaillierte Inhalt vonWie erstelle und durchlaufe ich einen Binärbaum in Javascript? (Codebeispiel). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!