Heim > Artikel > Web-Frontend > JavaScript implementiert Pre-Order-, In-Order- und Post-Order-Traversal-Methoden von Binärbäumen

JavaScript implementiert Pre-Order-, In-Order- und Post-Order-Traversal-Methoden von Binärbäumen

小云云Original: 2018-01-02 13:17:592060Durchsuche

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 = &#39;blue&#39;;
  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 = &#39;blue&#39;;
  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;iDaher 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 
JS-Implementierungsdatenstruktur: Baum und Binärbaum, Binärbaumdurchquerung und grundlegende Operationsmethoden 
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!

Java php c语言 JavaScript 递归数据结构堆 JS

Stellungnahme：

Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn

Vorheriger Artikel：So berechnen Sie die Gleitstrecke mithilfe eines Touch-Ereignisses auf einem JS-MobiltelefonNächster Artikel：So berechnen Sie die Gleitstrecke mithilfe eines Touch-Ereignisses auf einem JS-Mobiltelefon

In Verbindung stehende Artikel

Mehr sehen