In diesem Artikel werden hauptsächlich die Methoden der Vorbestellungs-, In-Order- und Post-Order-Durchquerung von Binärbäumen in JavaScript vorgestellt und analysiert Bäume in JavaScript und zugehörige Betriebsvorkehrungen in Form von Beispielen Was benötigt wird Freunde können sich darauf beziehen, ich hoffe, es kann jedem helfen.
Das Beispiel in diesem Artikel beschreibt die JavaScript-Implementierung von Pre-Order-, In-Order- und Post-Order-Traversal-Methoden von Binärbäumen. Ich teile es Ihnen als Referenz mit:
Als ich zuvor die Datenstruktur lernte, lernte ich die Vorbestellungs-, In-Order- und Post-Order-Traversal-Methoden von Binärbäumen und implementierte sie Sie werden in der C-Sprache implementiert. Das Folgende ist in js implementiert. Drei Arten der Durchquerung von Binärbäumen werden in Form einer Animation dargestellt.
Der gesamte Durchquerungsprozess verwendet immer noch rekursives Denken. Das Prinzip ist sehr grob und einfach
Funktion der Vorbestellungsdurchquerung:
function preOrder(node){ if(!(node==null)){ pList.push(node); preOrder(node.firstElementChild); preOrder(node.lastElementChild); } }
Funktion für die Durchquerung mittlerer Ordnung:
function inOrder(node) { if (!(node == null)) { inOrder(node.firstElementChild); pList.push(node); inOrder(node.lastElementChild); } }
Funktion für Durchquerung nach der Ordnung:
function postOrder(node) { if (!(node == null)) { postOrder(node.firstElementChild); postOrder(node.lastElementChild); pList.push(node); } }
Farbänderungsfunktion:
function changeColor(){ var i=0; pList[i].style.backgroundColor = 'blue'; timer=setInterval(function(argument){ i++; if(i<pList.length){ pList[i-1].style.backgroundColor="#fff"; pList[i].style.backgroundColor="blue"; } else{ pList[pList.length-1].style.backgroundColor="#fff"; } },500) }
Der Kerncode ist wie oben. Ursprünglich wollte ich eine Tiefendurchquerung und eine Breitendurchquerung schreiben. Später wurde entdeckt, dass die Tiefendurchquerung eines Binärbaums mit der Vorbestellungsdurchquerung identisch ist. Ich werde die BFS und DFS von Bäumen an einem anderen Tag zusammenfassen.
Der gesamte Code lautet wie folgt:
<!DOCTYPE html> <html> <head lang="en"> <meta charset="UTF-8"> <title></title> <style> .root{ display: flex; padding: 20px; width: 1000px; height: 300px;border: 1px solid #000000; margin: 100px auto; margin-bottom: 10px; justify-content: space-between; } .child_1{ display: flex; padding: 20px; width: 450px; height: 260px;border: 1px solid red; justify-content: space-between; } .child_2{ display: flex; padding: 20px; width: 170px; height: 220px;border: 1px solid green; justify-content: space-between; } .child_3{ display: flex; padding: 20px; width: 35px; height: 180px;border: 1px solid blue; justify-content: space-between; } input{ margin-left: 100px; width: 60px; height: 40px; font:20px italic; } </style> </head> <body> <p class="root"> <p class="child_1"> <p class="child_2"> <p class="child_3"></p> <p class="child_3"></p> </p> <p class="child_2"> <p class="child_3"></p> <p class="child_3"></p> </p> </p> <p class="child_1"> <p class="child_2"> <p class="child_3"></p> <p class="child_3"></p> </p> <p class="child_2"> <p class="child_3"></p> <p class="child_3"></p> </p> </p> </p> <input type="button" value="先序"> <input type="button" value="中序"> <input type="button" value="后序"> <script type="text/javascript" src="遍历.js"></script> </body> </html>
js:
/** * Created by hp on 2016/12/22. */ var btn = document.getElementsByTagName('input'), preBtn = btn[0], inBtn = btn[1], postBtn = btn[2], treeRoot = document.getElementsByClassName('root')[0], pList = [], timer = null; window.onload=function(){ preBtn.onclick = function () { reset(); preOrder(treeRoot); changeColor(); } inBtn.onclick = function () { reset(); inOrder(treeRoot); changeColor(); } postBtn.onclick = function () { reset(); postOrder(treeRoot); changeColor(); } } /*先序遍历*/ function preOrder(node){ if(!(node==null)){ pList.push(node); preOrder(node.firstElementChild); preOrder(node.lastElementChild); } } /*中序遍历*/ function inOrder(node) { if (!(node == null)) { inOrder(node.firstElementChild); pList.push(node); inOrder(node.lastElementChild); } } /*后序遍历*/ function postOrder(node) { if (!(node == null)) { postOrder(node.firstElementChild); postOrder(node.lastElementChild); pList.push(node); } } /*颜色变化函数*/ function changeColor(){ var i=0; pList[i].style.backgroundColor = 'blue'; timer=setInterval(function(argument){ i++; if(i<pList.length){ pList[i-1].style.backgroundColor="#fff"; pList[i].style.backgroundColor="blue"; } else{ pList[pList.length-1].style.backgroundColor="#fff"; } },500) } function reset(){ pList=[]; clearInterval(timer); var ps=document.getElementsByTagName("p"); for(var i=0;i Nach dem Login kopieren
Daher ist ersichtlich, dass die Idee des Durchlaufens eines Binärbaums dieselbe ist. Früher habe ich JS als eine Sprache zum Schreiben verschiedener Spezialeffekte betrachtet, aber jetzt war es immer zu naiv.
Verwandte Empfehlungen:
Detaillierte Erläuterung der Definitionsmethode des vollständigen Binärbaums in PHP
Implementierungsmethode des Java Minimum Binary Tree Heap Sortieren
Das obige ist der detaillierte Inhalt vonJavaScript implementiert Pre-Order-, In-Order- und Post-Order-Traversal-Methoden von Binärbäumen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!