Comment implémenter la traversée d'arbre binaire à l'aide de JavaScript

Cet article présente principalement la méthode de réalisation de la définition, du parcours et de la recherche d'arbres binaires en JavaScript. Il analyse en détail les concepts associés aux arbres binaires sous forme d'exemples et les techniques opérationnelles courantes de construction d'arbres binaires, de parcours et de recherche binaires. arbres en JavaScript. Les amis qui en ont besoin peuvent Pour référence,

L'exemple de cet article décrit comment implémenter la définition, le parcours et la recherche d'arbres binaires à l'aide de JavaScript. Partagez-le avec tout le monde pour votre référence, comme suit :

Arbre binaire (arbre binaire)

Avant d'écrire cet article, parlons du structure des données et La série d'algorithmes contient de nombreuses choses, telles que le tri, les tableaux linéaires, les tableaux généralisés, les arbres et les graphiques. Tout le monde le sait, mais combien de ces choses pouvons-nous utiliser dans notre travail après les avoir apprises ? Je sais que la plupart des entreprises, des codeurs de première ligne, des perdants et des programmeurs n'utilisent pas ces choses. Dans ce cas, pourquoi devrais-je mettre l'accent sur cette série ? Je pense que les algorithmes et les structures de données sont les compétences de base de la programmation. Les codeurs de première ligne et les programmeurs ordinaires doivent, pour le dire simplement, s'améliorer. Deuxièmement, les langues sont toutes comprises. Tant que vous maîtrisez une langue, apprendre d’autres langues, c’est comme suivre le courant, sans aucun effort. Un autre point est que je continuerai à écrire cette série. Même si j'ai beaucoup cherché sur Internet et que je l'ai déjà terminée, j'ai deux objectifs en écrivant : le premier est de la partager avec tout le monde, et le second est de m'impliquer davantage. -profondeur comprendre. D'accord, pas grand chose d'autre à dire. J'ai récemment examiné les arbres binaires, je vais donc écrire ceci en premier, puis j'ajouterai des tris, des tableaux linéaires et des tableaux généralisés dans l'ordre. . . . Attendez

Arbre binaire

Quand il s'agit d'arbres binaires, nous allons certainement demander, qu'est-ce qu'un arbre binaire, qu'est-ce qu'un arbre binaire, à quoi sert-il , et pourquoi voulons-nous l'apprendre ? Si vous ne vous êtes pas posé ces questions lorsque vous appreniez les arbres binaires, alors votre compréhension n'est qu'une compréhension. Parlons maintenant de ce qu'est un arbre binaire. Un arbre binaire est une structure de données, et sa relation organisationnelle est comme un arbre dans la nature. La définition dans la langue officielle est la suivante : il s'agit d'un ensemble d'éléments finis, soit vide, soit constitué d'un élément appelé racine et de deux arbres binaires disjoints, appelés respectivement sous-arbre gauche et sous-arbre droit. Quant à savoir pourquoi je devrais l'apprendre, ma mère disait toujours, gamin, tu comprendras quand tu seras grand.

Propriétés des arbres binaires

Propriété 1 : Le nombre de nœuds au i-ème niveau d'un arbre binaire est d'au plus 2i-1 (i≥1) ;
Propriété 2 : Profondeur L'arbre binaire pour k a au plus 2k-1 nœuds (k≥1).
Propriété 3 : Dans tout arbre binaire, si le nombre de nœuds feuilles (c'est-à-dire les nœuds de degré 0) est n0, le nombre de nœuds de degré 1 est n1 et le nombre de nœuds de degré 2 est n2, Alors non=n2+1.

Structure de stockage et construction d'arbres binaires

Il existe deux façons de stocker des arbres binaires, l'une est le stockage séquentiel, par exemple :
var binaryTree = ['a', 'b', 'c', 'd', 'e', 'f', 'h', 'i']; C'est un arbre binaire, en supposant que binaireTree[i] est un nœud d'un arbre binaire, puis son nœud enfant gauche leftChild = binaireTree[i*2+1], puis le nœud enfant droit correspondant rightChild = binaireTree[i*2+2] ; Généralement stocké séquentiellement Cette structure est rarement utilisée.Une autre méthode de stockage est le stockage en chaîne.Ci-dessous, j'utiliserai le code pour décrire en détail la méthode de construction et de stockage d'une structure arborescente binaire.Il existe deux façons de construire une arborescence binaire. celui-ci est très simple, et l'autre est construit en utilisant une méthode non récursive. Celui-ci est un peu plus compliqué que le précédent, mais ne vous inquiétez pas, j'ajouterai des commentaires détaillés au code et je suivrai. cela étape par étape. Nous utilisons maintenant 26 lettres anglaises pour construire un arbre binaire

Copiez le code Le code est le suivant :

var charecters = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O ', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'];

Avant de construire un arbre binaire, nous utiliserons un objet nœud. L'objet nœud est le suivant : (Remarque : je mettrai les fonctionnalités orientées objet, prototype et grammaticales de JavaScript dans cette série de points de connaissance du langage JavaScript. )

/*
 *二叉树的节点对象
 */
function Node() {
  this.text = '';      //节点的文本
  this.leftChild = null;  //节点的左孩子引用
  this.rightChild = null;  //节点右孩子引用
}

Construire récursivement un arbre binaire

Après avoir construit les nœuds de l'arbre binaire, nous utilisons ensuite la récursion pour construire l'arbre binaire

var charecters = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'];
function buildTree(node, i) {
    var leftIndex = 2*i+1,             //左孩子节点的索引
      rightIndex = 2*i+2;             //右孩子节点的索引
    if(leftIndex < charecters.length) {       //判断索引的长度是否超过了charecters数组的大小
      var childNode = new Node();         //创建一个新的节点对象
      childNode.text = charecters[leftIndex];   //给节点赋值
      node.leftChild = childNode;         //给当前节点node加入左孩子节点
      buildTree(childNode, leftIndex);      //递归创建左孩子
    }
    if(rightIndex < charecters.length) {      //下面注释参照上面的构建左孩子的节点
      var childNode = new Node();
      childNode.text = charecters[rightIndex];
      node.rightChild = childNode;
      buildTree(childNode, rightIndex);
    }
}
//下面构造二叉树
var node = new Node();
node.text = charecters[0];
buildTree(node, 0);  //索引i是从0开始构建

Construire de manière non récursive un arbre binaire

Ce qui suit est une manière non récursive de construire un arbre binaire :

var root;
function createBinaryTree() {
    var len = charecters.length,        //数组的长度
      index = 0,               //索引从0开始
      nodes = new Array();          //创建一个临时数组，用于存放二叉树节点
    //循环创建二叉树节点存放到数组中
    for (var i = 0 ; i < charecters.length ; i++) {
      var node = new Node();
      node.text = charecters[i];
      nodes.push(node);
    }
    //循环建立二叉树子节点的引用
    while(index < len) {
      var leftIndex = 2*index+1,       //当前节点左孩子索引
        rightIndex = 2*index+2;       //当前节点右孩子索引
      //给当前节点添加左孩子
      nodes[index].leftChild = nodes[leftIndex];
      //给当前节点添加右孩子
      nodes[index].rightChild = nodes[rightIndex];
      index++;
    }
    root = nodes[0];
}

Trois parcours d'un arbre binaire

好了，现在我们已经成功构建了二叉树的链式结构，在构建了二叉树的链式结构后我们进入二叉树的最基本的遍历了，遍历有三种最基本的遍历，我不说想必大家都知道，先序遍历，中序遍历和后续遍历。虽然这三种遍历递归方式都比较简单，但非递归方式就不是那么容易了，当时我在实现的时候都卡了半天，真的是说起来容易做起来难啊，在实现遍历前我们首先要来实现的是栈，因为在非递归遍历的时候会用到栈，那到底什么是栈呢，这里我就简单介绍下吧，有兴趣的朋友可以去维基百科有权威的定义，栈和队列也是一种数据结构，栈存放数据的时候是先进先出，而队列是先进后出。

实现栈的对象

下面用javascript来实现栈的对象

function Stack() {
    var stack = new Array();        //存放栈的数组
    //压栈
    this.push = function(o) {
      stack.push(o);
    };
    //出栈
    this.pop = function() {
      var o = stack[stack.length-1];
      stack.splice(stack.length-1, 1);
      return o;
    };
    //检查栈是否为空
    this.isEmpty = function() {
      if(stack.length <= 0) {
        return true;
      }
      else {
        return false;
      }
    };
}
//使用方式如下
var stack = new Stack();
stack.push(1);    //现在栈中有一个元素
stack.isEmpty();   //false , 栈不为空
alert(stack.pop()); //出栈, 打印1
stack.isEmpty();   //true, 此时栈为空，因为在调用了stack.pop()之后元素出栈了，所以为空

1. 先序遍历

在实现了栈对象以后我们首先来进行先序遍历的递归方式

function firstIteration(node) {
    if(node.leftChild) {          //判断当前节点是否有左孩子
      firstIteration(node.leftChild);  //递归左孩子
    }
    if(node.rightChild) {         //判断当前节点是否有右孩子
      firstIteration(node.rightChild);  //递归右孩子
    }
}
//递归遍历二叉树
firstIteration(root);

先序遍历的非递归方式

上面的代码大家可以在firstIteration()方法中加个alert()函数来验证是否正确。那么下面就要说说先序遍历的非递归方式，遍历思想是这样的：先访问根节点在访问左节点， 最后访问右节点。从根节点一直往下访问找左孩子节点，直到最后一个左孩子节点（将这条路径保存到栈中），然后再访问最后一个左孩子的兄弟节点（右孩子节点），之后回溯到上一层（将栈中的元素取出 就是出栈），又开始从该节点（回溯到上一层的节点）一直往下访问找左孩子节点... 直到栈中的元素为空，循环结束。

function notFirstIteration(node) {
    var stack = new Stack(),         //开辟一个新的栈对象
      resultText = '';           //存放非递归遍历之后的字母顺序
    stack.push(root);            //这个root在上面非递归方式构建二叉树的时候已经构建好的
    var node = root;
    resultText += node.text;
    while(!stack.isEmpty()) {
      while(node.leftChild) {       //判断当前节点是否有左孩子节点
        node = node.leftChild;      //取当前节点的左孩子节点
        resultText += node.text;     //访问当前节点
        stack.push(node);        //将当前节点压入栈中
      }
      stack.pop();             //出栈
      node = stack.pop().rightChild;    //访问当前节点的兄弟节点（右孩子节点）
      if(node) {              //当前节点的兄弟节点不为空
        resultText += node.text;     //访问当前节点
        stack.push(node);        //将当前节点压入栈中
      }
      else {                //当前节点的兄弟节点为空
        node = stack.pop();       //在回溯到上一层
      }
    }
}
//非递归先序遍历
notFirstIteration(root);

2. 中序遍历

只要把思路理清楚了现实起来其实还是挺容易的，只要我们熟悉了一种二叉树的非递归遍历方式，其他几种非递归方式就容易多了，照着葫芦画瓢，下面是中序遍历的递归方式，中序遍历的思想是：先访问左孩子节点，在访问根节点，最后访问右节点

var strText = "";
function secondIteration(node) {
    //访问左节点
    if(node.leftChild) {
      if(node.leftChild.leftChild) {
        secondIteration(node.leftChild);
      }
      else {
        strText += node.leftChild.text;
      }
    }
    //访问根节点
    strText += node.text;
    //访问右节点
    if(node.rightChild) {
      if(node.rightChild.leftChild) {
        secondIteration(node.rightChild);
      }
      else {
        strText += node.rightChild.text;
      }
    }
}
secondIteration(root);
alert(strText);

中序遍历的非递归方式

思想是：1. 从根节点一直往下找左孩子节点，直到找到最后一个左孩子节点（用栈将此路径保存，但不访问）2.访问最后一个左孩子节点，然后再访问根节点（要先弹出栈，就是在栈中取上一层节点）3.在访问当前节点（最后一个左孩子节点）的兄弟节点（右孩子节点），这里要注意如果兄弟节点是一个叶节点就直接访问，否则是兄弟节点是一颗子树的话不能马上访问，要先来重复 1， 2，3步骤， 直到栈为空，循环结束

function notSecondIteration() {
    var resultText = '',
      stack = new Stack(),
      node = root;
    stack.push(node);
    while(!stack.isEmpty()) {
      //从根节点一直往下找左孩子节点直到最后一个左孩子节点，然后保存在栈中
      while(node.leftChild) {
        node = node.leftChild;
        stack.push(node);
      }
      //弹出栈
      var tempNode = stack.pop();
      //访问临时节点
      resultText += tempNode.text;
      if(tempNode.rightChild) {
        node = tempNode.rightChild;
        stack.push(node);
      }
    }
    alert(resultText);
}

3. 后续遍历

最后就还剩下一种遍历方式，二叉树的后续遍历，后续遍历的思想是：先访问左孩子节点，然后在访问右孩子节点，最后访问根节点

后续遍历的递归方式

var strText = '';
function lastIteration(node) {
    //首先访问左孩子节点
    if(node.leftChild) {
      if(node.leftChild.leftChild) {
        lastIteration(node.leftChild);
      }
      else {
        strText += node.leftChild.text;
      }
    }
    //然后再访问右孩子节点
    if(node.rightChild) {
      if(node.rightChild.rightChild) {
        lastIteration(node.rightChild);
      }
      else {
        strText += node.rightChild.text;
      }
    }
    //最后访问根节点
    strText += node.text;
}
//中序递归遍历
lastIteration(root);
alert(strText);

后续非递归遍历

后续非递归遍历的思想是：1.从根节点一直往下找左孩子节点，直到最后一个左孩子节点（将路径保存到栈中，但不访问）2.弹出栈访问最后一个左孩子节点 3.进入最后一个左孩子节点的兄弟节点，如果兄弟节点是叶节点就访问它，否则将该节点重复 1， 2步骤, 直到栈中的元素为空，循环结束。3.访问根节点

function notLastIteration() {
    var strText = '',
    stack = new Stack();
    nodo = root;
    stack.push(node);
    while(!stack.isEmpty()) {
      while(node.leftChild) {
        node = node.leftChild;
        stack.push(node);
      }
      //弹出栈
      var tempNode = stack.pop();
      //访问左孩子节点
      strText += tempNode.text;
      //访问右孩子节点
      if(tempNode.rightChild) {
        if(tempNode.rightChild.leftChild || tempNode.rightChild.rightChild) { //判断最后一个左孩子节点的兄弟节点是否为页节点
          stack.push(tempNode.rightChild);
        }
        else {
          strText += tempNode.rightChild.text;
        }
      }
    }
    alert(strText);
}

上面是我整理给大家的，希望今后会对大家有帮助。

相关文章：

如何使用vuex实现菜单管理

详细解读Angular5.1新功能

使用nodejs如何实现gulp打包

在vue2中通过keep-alive如何使用

在webpack中有关于jquery插件的环境配置（详细教程）

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!