Detaillierte Erklärung der Binärbaumdurchquerung in JS

Ein Binärbaum besteht aus einem Wurzelknoten, einem linken Teilbaum und einem rechten Teilbaum. Der linke Teilbaum und der Freund-Teilbaum sind jeweils ein Binärbaum.
Dieser Artikel implementiert hauptsächlich die Binärbaumdurchquerung in JS.

Ein Beispiel für einen Binärbaum

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

Breitenorientierte Durchquerung

Die Breitenprioritätsdurchquerung beginnt auf der ersten Ebene (Wurzelknoten) des Binärbaums und durchläuft Ebene für Ebene von oben nach unten. In derselben Ebene werden die Knoten einzeln in der Reihenfolge von links nach rechts besucht.

Implementierung:

Verwenden Sie ein Array, um eine Warteschlange zu simulieren. Stellen Sie zuerst den Wurzelknoten in die Warteschlange. Wenn die Warteschlange nicht leer ist, führen Sie eine Schleife aus: Nehmen Sie einen Knoten aus der Warteschlange. Wenn der linke Teilbaum des Knotens nicht leer ist, fügen Sie den linken Teilbaum des Knotens in die Warteschlange ein Wenn es nicht leer ist, stellen Sie den rechten Teilbaum des Knotens in die Warteschlange.
(Die Beschreibung ist etwas unklar, schauen Sie sich einfach den Code an.)

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

Rekursive Durchquerung

Ich habe das Gefühl Mit diesen Buchstaben gibt es drei gute Möglichkeiten, rekursives Durchqueren auszudrücken:
D: Besuche den Wurzelknoten, L: Durchquere den linken Teilbaum des Wurzelknotens, R: Durchquere den rechten Teilbaum des Wurzelknotens.
Durchquerung vor der Bestellung: DLR
Durchquerung in der Reihenfolge: LDR
Durchquerung nach der Bestellung: LRD
Der Bedeutung der Buchstaben folgend, it ist eine Durchquerung. ^ ^

Diese drei Arten der Durchquerung sind alle rekursive Durchquerungen oder Tiefensuche (DFS), da immer
zuerst tiefer zugegriffen wird.

Rekursiver Algorithmus für die Durchquerung vor der Reihenfolge:

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

Rekursiver Algorithmus für die Durchquerung in der Reihenfolge:

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

Rekursiver Algorithmus für Post-Order-Traversal:

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

Nicht-rekursiver Depth-First-Traversal

Tatsächlich, denn ich bin nicht sicher, wem diese Konzepte gehören. In einigen Büchern wird nur über die oben genannten drei rekursiven Durchquerungen für die Durchquerung von Binärbäumen gesprochen. Einige sind in zwei Typen unterteilt: Breitendurchlauf und Tiefendurchlauf, und einige sind in zwei Typen unterteilt: rekursiver Durchlauf und nichtrekursiver Durchlauf und die folgende Durchquerung. Persönlich denke ich, dass es keine Rolle spielt, wie man es aufteilt, solange man die Methoden und Verwendungen beherrscht :)

Was wir gerade bei der Breitendurchquerung verwendet haben, ist in diesem Fall eine Warteschlange. Bei der rekursiven Tiefendurchquerung verwenden wir einen Stapel. Verwenden Sie weiterhin ein Array, um es in JS zu simulieren.
Hier reden wir nur über Vorbestellung:
Nun, ich habe versucht, diesen Algorithmus zu beschreiben, aber er war nicht klar. Folgen Sie einfach dem Code und Sie werden es verstehen.

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

Nachdem ich diesen Artikel gelesen habe, habe ich den nicht-rekursiven Post-Order-Algorithmus gefunden, daher werde ich hier die nicht-rekursive Traversal-Methode vervollständigen.

Nicht rekursiv in der Reihenfolge

Schieben Sie zuerst den linken Knoten der Zahl auf den Stapel, nehmen Sie ihn dann heraus und schieben Sie dann den rechten Knoten.

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

Nicht rekursive Nachbestellung (unter Verwendung eines Stapels)

Hier wird eine temporäre Variable verwendet, um den letzten Push aufzuzeichnen/ Pop-Knoten. Die Idee besteht darin, zuerst den Wurzelknoten und den linken Baum auf den Stapel zu schieben, dann den linken Baum herauszunehmen, dann in den rechten Baum zu schieben, sie herauszunehmen und schließlich den folgenden Knoten zu nehmen.

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

Nicht rekursive Nachbestellung (unter Verwendung von zwei Stapeln)

Die Idee dieses Algorithmus ist ähnlich Das obige, s1 ist ein bisschen wie eine temporäre Variable.

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

Morris-Durchquerung

Diese Methode implementiert drei Tiefendurchquerungen ohne Rekursion oder Stapel, und die Raumkomplexität beträgt O(1) ( Mir ist dieses Konzept nicht besonders klar)
(Ich werde diese drei Algorithmen beiseite lassen und sie studieren, wenn ich Zeit habe)

Morris-Reihenfolge:

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 Mittelbestellung:

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 Nachbestellung:

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

Das ist alles Der gesamte Inhalt dieses Artikels soll zum Lernen aller beitragen. Weitere verwandte Tutorials finden Sie unter JavaScript-Video-Tutorial!