JavaScript implementiert Pre-Order-, In-Order- und Post-Order-Traversal-Methoden von Binärbäumen-js-Tutorial-php.cn

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

小云云

Freigeben： 2018-01-02 13:17:59

Original

2086 Leute haben es durchsucht

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);
  }
}

Nach dem Login kopieren

Funktion für die Durchquerung mittlerer Ordnung:

function inOrder(node) {
  if (!(node == null)) {
    inOrder(node.firstElementChild);
    pList.push(node);
    inOrder(node.lastElementChild);
  }
}

Nach dem Login kopieren

Funktion für Durchquerung nach der Ordnung:

function postOrder(node) {
  if (!(node == null)) {
    postOrder(node.firstElementChild);
    postOrder(node.lastElementChild);
    pList.push(node);
  }
}

Nach dem Login kopieren

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)
}

Nach dem Login kopieren

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>

Nach dem Login kopieren

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;iNach 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

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!