recherche

Maison >interface Web >js tutoriel >JavaScript implémente des méthodes de parcours des arbres binaires avant, dans l'ordre et après l'ordre

JavaScript implémente des méthodes de parcours des arbres binaires avant, dans l'ordre et après l'ordre

小云云
小云云original
2018-01-02 13:17:592112parcourir

Cet article présente principalement les méthodes de parcours pré-ordre, dans l'ordre et post-ordre des arbres binaires en JavaScript. Il résume et analyse les méthodes d'implémentation du parcours pré-ordre, dans l'ordre et post-ordre des arbres binaires. arbres en JavaScript et précautions de fonctionnement associées sous forme d'exemples. Ce qui est nécessaire Les amis peuvent s'y référer, j'espère que cela pourra aider tout le monde.

L'exemple de cet article décrit l'implémentation JavaScript des méthodes de traversée en pré-ordre, dans l'ordre et après-ordre des arbres binaires. Je le partage avec vous pour votre référence. Les détails sont les suivants :

Lorsque j'apprenais la structure des données auparavant, j'ai appris les méthodes de parcours pré-ordre, dans l'ordre et post-ordre des arbres binaires et implémenté en langage C. Ce qui suit est implémenté dans js Trois types de parcours d'arbres binaires, et le processus de parcours est montré sous forme d'animation.

L'ensemble du processus de traversée utilise toujours la pensée récursive. Le principe est très approximatif et simple

Fonction de traversée en pré-commande : 


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

Fonction pour le parcours de mi-ordre : 


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

Fonction pour le parcours de post-ordre : 


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

Fonction de changement de couleur : 


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

Le code de base est comme ci-dessus. À l'origine, je voulais écrire un parcours en profondeur et en largeur. Plus tard, il a été découvert que le parcours en profondeur d'un arbre binaire est identique au parcours de pré-ordre. Je résumerai le BFS et le DFS des arbres un autre jour.

L'ensemble du code est le suivant : 


<!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;i
On voit donc que l'idée de parcourir un arbre binaire est la même. Avant, je considérais JS comme un langage permettant d'écrire divers effets spéciaux, mais maintenant, il a toujours été trop naïf. 


Recommandations associées : 


Explication détaillée de la méthode de définition de l'arbre binaire complet en php


Méthode d'implémentation du tas d'arbre binaire minimum Java sorting 


Implémentation JS des structures de données : arbres et arbres binaires, parcours d'arbres binaires et méthodes de fonctionnement de base 
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!
Java php c语言 JavaScript 递归 数据结构 堆 JS
Déclaration：
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Article précédent：Comment calculer la distance de glissement à l'aide d'un événement tactile sur un téléphone mobile JSArticle suivant：Comment calculer la distance de glissement à l'aide d'un événement tactile sur un téléphone mobile JS

Articles Liés

Voir plus