Explication détaillée de la traversée de l'arbre binaire dans JS

Un arbre binaire est composé d'un nœud racine, d'un sous-arbre gauche et d'un sous-arbre droit. Le sous-arbre gauche et le sous-arbre ami sont chacun un arbre binaire.
Cet article implémente principalement la traversée d'arbres binaires en JS.

Un exemple d'arbre binaire

var tree = {
 value: 1,
 left: {
  value: 2,
  left: {
   value: 4
  }
 },
 right: {
  value: 3,
  left: {
   value: 5,
   left: {
    value: 7
   },
   right: {
    value: 8
   }
  },
  right: {
   value: 6
  }
 }
}

Parcours en largeur d'abord

Le parcours de priorité en largeur commence à partir du premier niveau (nœud racine) de l'arbre binaire et traverse niveau par niveau de haut en bas dans le même niveau, les nœuds sont visités un par un dans l'ordre de gauche à droite ;

Implémentation :

Utilisez un tableau pour simuler une file d'attente. Mettez d’abord le nœud racine dans la file d’attente. Lorsque la file d'attente n'est pas vide, exécutez une boucle : retirez un nœud de la file d'attente, et si le sous-arbre gauche du nœud n'est pas vide, mettez le sous-arbre gauche du nœud dans la file d'attente si le sous-arbre droit du nœud l'est ; S'il n'est pas vide, placez le sous-arbre droit du nœud dans la file d'attente.
(La description est un peu floue, il suffit de regarder le code.)

var levelOrderTraversal = function(node) { 
 if(!node) {  
  throw new Error('Empty Tree')
 } 
 var que = []
 que.push(node) 
 while(que.length !== 0) {
  node = que.shift()  
  console.log(node.value)  
  if(node.left) que.push(node.left)  
  if(node.right) que.push(node.right)
 }
}

Parcours récursif

J'ai l'impression en utilisant ces lettres Il existe trois bonnes façons d'exprimer un parcours récursif :
D : visiter le nœud racine, L : parcourir le sous-arbre gauche du nœud racine, R : parcourir le sous-arbre droit du nœud racine.
Parcours de pré-commande : DLR
Parcours dans l'ordre : LDR
Parcours de post-commande : LRD
En suivant la signification des lettres, il est la traversée. Dans l'ordre ^ ^

Ces trois types de traversées sont toutes des traversées récursives, ou des traversées en profondeur (Depth-First Search, DFS), car elles
accèdent toujours en premier plus profondément.

Algorithme récursif pour le parcours en pré-ordre :

var preOrder = function (node) { 
 if (node) {  
  console.log(node.value);
  preOrder(node.left);
  preOrder(node.right);
 }
}

Algorithme récursif pour le parcours en ordre :

var inOrder = function (node) { 
 if (node) {
  inOrder(node.left);  
  console.log(node.value);
  inOrder(node.right);
 }
}

Algorithme récursif pour le parcours post-ordre :

var postOrder = function (node) { 
 if (node) {
  postOrder(node.left);
  postOrder(node.right);  
  console.log(node.value);
 }
}

Parcours non récursif en profondeur d'abord

En fait, car je ne sais pas vraiment à qui appartiennent ces concepts. Certains livres ne parlent que des trois parcours récursifs ci-dessus pour le parcours d'arbres binaires. Certains sont divisés en deux types : le parcours en largeur d'abord et le parcours en profondeur d'abord, et le parcours récursif est divisé en parcours en profondeur ; certains sont divisés en deux types : le parcours récursif et le parcours non récursif incluent le parcours en largeur d'abord. et la traversée suivante. Personnellement, peu importe la façon dont vous le divisez, tant que vous maîtrisez les méthodes et les utilisations :)

Ce que je viens d'utiliser dans le parcours en largeur d'abord est une file d'attente, en conséquence, dans cette profondeur non récursive. -première traversée, nous utilisons une pile. Utilisez toujours un tableau pour le simuler dans JS.
Ici on ne parle que de précommande :
Eh bien, j'ai essayé de décrire cet algorithme, mais ce n'était pas clair. Suivez simplement le code et vous comprendrez.

var preOrderUnRecur = function(node) { 
 if(!node) {  
  throw new Error('Empty Tree')
 } 
 var stack = []
 stack.push(node) 
 while(stack.length !== 0) {
  node = stack.pop()  
  console.log(node.value)  
  if(node.right) stack.push(node.right)  
  if(node.left) stack.push(node.left)
 }
}

Après avoir lu cet article, j'ai trouvé l'algorithme de post-commande non récursif, je vais donc compléter ici la méthode de parcours non récursif.

Dans l'ordre non récursif

Poussez d'abord le nœud gauche du numéro sur la pile, puis retirez-le, puis poussez le nœud droit.

var inOrderUnRecur = function(node) { 
 if(!node) {  
  throw new Error('Empty Tree')
 } 
 var stack = [] 
 while(stack.length !== 0 || node) {  
  if(node) {
   stack.push(node)
   node = node.left
  } else {
   node = stack.pop()   
   console.log(node.value)
   node = node.right
  }
 }
}

Post-commande non récursive (à l'aide d'une pile)

Une variable temporaire est utilisée ici pour enregistrer le dernier push/ nœud pop. L'idée est d'abord de pousser le nœud racine et l'arbre de gauche sur la pile, puis de retirer l'arbre de gauche, puis de pousser dans l'arbre de droite, de les retirer et enfin de prendre le nœud suivant.

var posOrderUnRecur = function(node) { 
 if(!node) {  
  throw new Error('Empty Tree')
 } 
 var stack = []
 stack.push(node) 
 var tmp = null
 while(stack.length !== 0) {
  tmp = stack[stack.length - 1]  
  if(tmp.left && node !== tmp.left && node !== tmp.right) {
   stack.push(tmp.left)
  } else if(tmp.right && node !== tmp.right) {
   stack.push(tmp.right)
  } else {   
   console.log(stack.pop().value)
   node = tmp
  }
 }
}

Post-commande non récursive (utilisant deux piles)

L'idée de​​cet algorithme est similaire à celle ci-dessus, s1 est un peu comme une variable temporaire.

var posOrderUnRecur = function(node) { 
 if(node) {  
  var s1 = []  
  var s2 = []
  s1.push(node)  
  while(s1.length !== 0) {
   node = s1.pop()
   s2.push(node)   
   if(node.left) {
    s1.push(node.left)
   }   
   if(node.right) {
    s1.push(node.right)
   }
  }  
  while(s2.length !== 0) {   
   console.log(s2.pop().value);
  }
 }
}

Parcours de Morris

Cette méthode implémente trois parcours en profondeur sans récursion ni pile, et la complexité spatiale est O(1 ) ( Je ne suis pas particulièrement clair sur ce concept)
(Je laisserai ces trois algorithmes de côté et les étudierai quand j'aurai le temps)

Ordre de Morris :

var morrisPre = function(head) { 
 if(!head) {  
  return
 } 
 var cur1 = head,
   cur2 = null
 while(cur1) {
  cur2 = cur1.left  
  if(cur2) {   
   while(cur2.right && cur2.right != cur1) {
    cur2 = cur2.right
   }   
   if(!cur2.right) {
    cur2.right = cur1    
    console.log(cur1.value)
    cur1 = cur1.left    
    continue
   } else {
    cur2.right = null
   }
  } else {   
    console.log(cur1.value)
  }
  cur1 = cur1.right
 }
}

Morris en cours de commande :

var morrisIn = function(head) { 
 if(!head) {  
  return
 } 
 var cur1 = head,
   cur2 = null
 while(cur1) {
  cur2 = cur1.left  
  if(cur2) {   
   while(cur2.right && cur2.right !== cur1) {
    cur2 = cur2.right
   }   
   if(!cur2.right) {
    cur2.right = cur1
    cur1 = cur1.left    
    continue
   } else {
    cur2.right = null
   }
  }  
  console.log(cur1.value)
  cur1 = cur1.right
 }
}

Morris après-commande :

var morrisPost = function(head) { 
 if(!head) {  
  return
 } 
 var cur1 = head,
   cur2 = null
 while(cur1) {
  cur2 = cur1.left  
  if(cur2) {   
   while(cur2.right && cur2.right !== cur1) {
    cur2 = cur2.right
   }   
   if(!cur2.right) {
    cur2.right = cur1
    cur1 = cur1.left    
    continue
   } else {
    cur2.right = null
    printEdge(cur1.left)
   }
  }
  cur1 = cur1.right
 }
 printEdge(head)
}
var printEdge = function(head) {

C'est tout J'espère que l'intégralité du contenu de cet article sera utile à l'apprentissage de chacun. Pour plus de didacticiels connexes, veuillez visiter le Tutoriel vidéo JavaScript !