JavaScript implémente des méthodes de parcours des arbres binaires avant, dans l'ordre et après l'ordre-js tutoriel-php.cn

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

小云云

Libérer： 2018-01-02 13:17:59

original

2086 Les gens l'ont consulté

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

Copier après la connexion

Fonction pour le parcours de mi-ordre :

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

Copier après la connexion

Fonction pour le parcours de post-ordre :

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

Copier après la connexion

Fonction de changement de couleur :

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

Copier après la connexion

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>

Copier après la connexion

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;iCopier après la connexion

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!