Explication détaillée de l'arborescence JavaScript-js tutoriel-php.cn

Explication détaillée de l'arborescence JavaScript

高洛峰

Libérer： 2017-01-10 13:08:32

original

1460 Les gens l'ont consulté

Tout le monde doit être familier avec "l'arbre" de la structure de données Aujourd'hui, nous allons passer en revue l'arbre binaire et l'arbre dans la structure de données et les implémenter avec JavaScript.

ps : La structure arborescente se reflète clairement à de nombreux endroits dans le front-end, comme le DOM virtuel de Vue et le bouillonnement, etc.

Arbre binaire

--Concept--

L'arbre binaire est une structure arborescente caractérisée par le fait que chaque nœud a au plus deux sous-arbres (c'est-à-dire qu'il y a non (il existe des nœuds avec un degré supérieur à 2), et les sous-arbres de l'arbre binaire peuvent être divisés en sous-arbres gauche et droit, et leur ordre ne peut pas être inversé arbitrairement.

est le suivant, qui est un arbre binaire (remarque : les exemples d'arbres binaires suivants sont tous basés sur cet arbre binaire) :

Explication détaillée de larborescence JavaScript

Et, En parcourant l'arbre binaire (traversing Binary Tree), il existe trois méthodes couramment utilisées, comme suit :

1), parcours pré-commandé de l'arbre binaire (à gauche et à droite de la racine)

Si l'arbre binaire est vide, aucune opération ; sinon

-- Visiter le nœud racine

—Parcourir le sous-arbre de gauche dans l'ordre

—Parcourir le sous-arbre de droite ; en ordre.

Par exemple, pour l'arbre binaire dans l'exemple ci-dessus, le résultat du parcours est le suivant :

Explication détaillée de larborescence JavaScript

2), parcours dans l'ordre du binaire arbre (racine gauche droite)

Si l'arbre binaire est vide, aucune opération sinon

— parcourez le sous-arbre gauche dans l'ordre

— visitez le nœud racine

— parcourir dans l'ordre le sous-arbre droit.

Par exemple, pour l'arbre binaire dans l'exemple ci-dessus, le résultat du parcours est le suivant :

Explication détaillée de larborescence JavaScript

3), parcours post-ordre du binaire arbre (racines gauche et droite)

Si l'arbre binaire est vide, aucune opération sinon

— traverse le sous-arbre gauche en post-ordre

— traverse la droite ; sous-arbre en post-commande ;

--visitez le nœud racine.

Par exemple, pour l'arbre binaire dans l'exemple ci-dessus, le résultat du parcours est le suivant :

Explication détaillée de larborescence JavaScript

D'accord, maintenant que nous comprenons l'arbre binaire et comment le parcourir, faisons-le ensemble. Utilisez JavaScript pour l'implémenter, bien sûr en utilisant une structure de stockage en chaîne.

Tout d'abord, utilisez le constructeur JavaScript pour créer un nœud d'arbre binaire, comme suit :

function TreeNode(){
 this.data = null;//该节点数据
 this.lchild = null;//左子树
 this.rchild = null;//右子树   
};

Copier après la connexion

Ensuite, nous pouvons construire un arbre binaire via la traversée d'arbre binaire L'algorithme, comme suit , utilise la séquence de pré-commande pour construire une méthode d'arbre binaire :

/*
*method:采用先序序列建立二叉树
*@params: nodeList（Array） --树节点，以先序序列存入数组中，null代表空节点
*/
TreeNode.createBiTree = function(nodeList){
 var i = 0;
 return (function getNode(){
  var node = null,
   val = nodeList[i++];
  if(!val){
   node = null;
  }else{
   node = new TreeNode();
   node.data = val;
   node.lchild = getNode();
   node.rchild = getNode();
  }
  return node;
 })();
};

Copier après la connexion

Enfin, il s'agit de parcourir un arbre binaire, qui sont des traversées de pré-commande ( PreOrderTraverse) et le parcours dans l'ordre (InOrderTraverse) et le parcours post-ordre (PostOrderTraverse), comme suit :

TreeNode.prototype = {
 constructor: TreeNode,
 _PreOrderTraverse: function(node){
  if(node){
   console.log(node.data);
   this._PreOrderTraverse(node.lchild);
   this._PreOrderTraverse(node.rchild);
  }
 },
 PreOrderTraverse: function(){
  console.log(&#39;PreOrder:&#39;);
  this._PreOrderTraverse(this);
 },
 _InOrderTraverse: function(node){
  if(node){
   this._InOrderTraverse(node.lchild);
   console.log(node.data);
   this._InOrderTraverse(node.rchild);
  }
 },
 InOrderTraverse: function(){
  console.log(&#39;InOrder:&#39;);
  this._InOrderTraverse(this);
 },
 _PostOrderTraverse: function(node){
  if(node){
   this._PostOrderTraverse(node.lchild);
   this._PostOrderTraverse(node.rchild);
   console.log(node.data);
  }
 },
 PostOrderTraverse: function(){
  console.log(&#39;PostOrder:&#39;);
  this._PostOrderTraverse(this);
 }
};

Copier après la connexion

D'accord, en utilisant l'exemple d'arbre binaire ci-dessus, nous pouvons le tester nous-mêmes :

var treeNode = null,
 nodeList = [&#39;A&#39;, &#39;B&#39;, &#39;C&#39;, null, null, &#39;D&#39;, &#39;E&#39;, null, &#39;G&#39;, null, null, &#39;F&#39;, null, null, null];
//getting a binary tree from nodeList
treeNode = TreeNode.createBiTree(nodeList);
//traversing the tree of treeNode
treeNode.PreOrderTraverse();//ABCDEGF
treeNode.InOrderTraverse();//CBEGDFA
treeNode.PostOrderTraverse();//CGEFDBA

Copier après la connexion

Arbre

--Concept--

Un arbre est un ensemble fini de n (n>= 0) nœuds. Dans tout arbre non vide, il n'y a et n'y a qu'un seul nœud spécifique appelé racine. Lorsque n>1, les nœuds restants peuvent être divisés en m (m>0) nœuds finis mutuellement disjoints, dont chacun est lui-même un. arbre, appelé sous-arbre de la racine. Bien entendu, les arbres binaires appartiennent définitivement aux arbres.

Ce qui suit est un arbre (remarque : les exemples d'arbres suivants sont tous basés sur cet arbre) :

Explication détaillée de larborescence JavaScript

Et traversez plus d'un arbre là-bas Il existe deux méthodes de parcours couramment utilisées pour les arbres enfants, comme suit :

1) Le parcours racine-premier, qui est similaire au parcours de recherche en profondeur d'abord (Depth_First Search). Ils utilisent tous la pile pour parcourir les éléments, comme suit :

Explication détaillée de larborescence JavaScript

2), parcours par niveau, similaire au parcours Breadth_First Search. Ils utilisent tous des files d'attente pour parcourir les éléments, comme suit :

Explication détaillée de larborescence JavaScript

D'accord, maintenant que nous comprenons l'arborescence et la méthode de traversée, utilisons JavaScript pour l'implémenter ensemble. utilise également une structure de stockage en chaîne.

Tout d'abord, utilisez JavaScript pour créer des nœuds d'arborescence, comme suit :

/*
*@Params: data --节点数据
   children -- 所有孩子结点
*/
function TreeNode(data, children){
 if(!(this instanceof TreeNode)){
  return new TreeNode(data, children);
 }
 this.data = data || null;
 this.children = children || [];
};

Copier après la connexion

根据上述TreeNode构造函数，我们可以将例子中的树，表示如下：

var treeNode = TreeNode(&#39;A&#39;, [
       TreeNode(&#39;B&#39;, [TreeNode(&#39;E&#39;)]),
       TreeNode(&#39;C&#39;),
       TreeNode(&#39;D&#39;)
     ]);

Copier après la connexion

接着，就是编写遍历树方法咯，分别为先根遍历和按层次遍历，如下：

TreeNode.prototype = {
 constructor: TreeNode,
 _traverseAsDFS: function(node){//先根遍历
  var self = this;
  if(node){
   console.log(node.data);
   node.children.forEach(function(child){
    if(child.children.length){
     self._traverseAsDFS(child);
    }else{
     console.log(child.data);
    }
   });
  }
 },
 traverseAsDFS: function(){
  console.log(&#39;Depth_First Search&#39;);
  this._traverseAsDFS(this);
 },
 traverseAsBFS: function(){//按层次遍历
  var queue = [];
  console.log(&#39;Breadth_First Search&#39;);
  console.log(this.data);
  if(this.children.length){
   queue.push(this);
  }
  while(queue.length){
   let tempNode = queue.shift();
   tempNode.children.forEach(function(child){
    console.log(child.data);
    if(child.children.length){
     queue.push(child);
    }      
   });
  }
 }
};

Copier après la connexion

好了，利用上述二叉树例子，我们可以自行测试下：

var treeNode = TreeNode(&#39;A&#39;, [
       TreeNode(&#39;B&#39;, [TreeNode(&#39;E&#39;)]),
       TreeNode(&#39;C&#39;),
       TreeNode(&#39;D&#39;)
     ]);
treeNode.traverseAsDFS();//ABECD
treeNode.traverseAsBFS();//ABCDE

Copier après la connexion

关于上述全部代码，见github。

以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，同时也希望多多支持脚本之家PHP中文网

更多Explication détaillée de larborescence JavaScript相关文章请关注PHP中文网！