Analysieren eines binären baumartigen JSON-Objekts Level für Level in JavaScript

Question

Ich habe mich mit der binären Baum-ADT-Implementierung von Javascript herumgeschlagen und mich gefragt, ob jemand mir helfen könnte, dieses bestimmte JSON-Objekt zu analysieren.

{"root":{"info":1,"right":{"info":3,"left":{"info":2,"count":1},"right":{"info":5,"left":{"info":4,"count":1},"count":1},"count":1},"count":1}} 

Eine schnelle http://json.parser.online.fr/ Online sagt, dass die ausgegeben werden soll:

1 
3 
2 5 
4 

wenn ich die json Ebene für Ebene bin zu drucken. "info" enthält die Daten des Baumknotens und "links" & "rechts" zeigt auf Unterknoten. Mein printTreeByLevel,

this.printTreeByLevel = function(node){ 

    nodesQueue = []; 
    var nodesInCurrentLevel = 1; 
    var nodesInNextLevel = 0; 
    nodesQueue.push(node); 
    while (nodesQueue.length != 0) { 
    currNode = nodesQueue[nodesQueue.length-1]; 
    nodesQueue.pop(); 
    nodesInCurrentLevel--; 
    if (currNode) { 
     document.getElementById("main").innerHTML = document.getElementById("main").innerHTML + currNode.info +" "; 
     nodesQueue.push(currNode.left); 
     nodesQueue.push(currNode.right); 
     nodesInNextLevel += 2; 
    } 
    if (nodesInCurrentLevel == 0) { 
     document.getElementById("main").innerHTML = document.getElementById("main").innerHTML + "<br>"; 
     nodesInCurrentLevel = nodesInNextLevel; 
     nodesInNextLevel = 0; 
    } 
    } 
} 
} 

produziert

1 
3 5 
4 
2 

Answer 1

Sie haben den Baum in depth-first statt atem erste Parsen und das ist, warum die Elemente nicht in der Reihenfolge, wie sie wollten erschienen .

Was dies bedeutet

Bei jeder Iteration Sie tatsächlich wurden die zuletzt eingefügte Element bekommen. Dies führt dazu, dass Sie tatsächlich in Tiefe drucken, anstatt den Baum in der Reihenfolge zu analysieren, in der er eingefügt wurde (auf Ebenen).

ist hier ein JSFiddle: https://jsfiddle.net/duha7tx3/

Und hier ist das Stück falsche Code:

currNode = nodesQueue[0]; 
nodesQueue.splice(0, 1); 

Was ich hier mache ist, dass ich das erste Element immer bin und es dann aus dem Array entfernt . Wenn ich den Baum auf diese Weise analysiere, besuche ich alle Knoten auf dem aktuellen Level vor gehe zum nächsten. Die Art, wie du es gemacht hast, bedeutete, dass du die Knoten auf der Ebene neben besuchst, bevor du die auf der aktuellen Ebene besuchst.

Hoffe das beantwortet Ihre Frage.