JSでのバイナリツリートラバーサルの詳細な説明

二分木はルートノード、左サブツリー、右サブツリーで構成されます。左サブツリーとフレンドサブツリーはそれぞれ二分木です。
この記事では主に JS でバイナリ ツリー トラバーサルを実装します。

バイナリ ツリーの例

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

幅優先トラバーサル

幅優先トラバーサルは、バイナリ ツリーの最初のレベル (ルート ノード) から開始し、同じレベル内で上から下にレベルごとにトラバースし、ノードは左から右の順に 1 つずつアクセスされます。

実装:

配列を使用してキューをシミュレートします。まずルートノードをキューに入れます。キューが空でない場合は、ループを実行します。キューからノードを取り出し、ノードの左側のサブツリーが空でない場合は、ノードの右側のサブツリーが空の場合、ノードの左側のサブツリーをキューに入れます。空でない場合は、ノードの右のサブツリーをキューに入れます。
(説明がちょっとわかりにくいのでコードを見てください。)

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

再帰走査

のような気がしますこれらの文字を使用する 再帰的走査を表現するには 3 つの適切な方法があります:
D: ルート ノードにアクセスする、L: ルート ノードの左側のサブツリーを走査する、R: ルート ノードの右側のサブツリーを走査する。
プリオーダートラバーサル: DLR
インオーダートラバーサル: LDR
ポストオーダートラバーサル: LRD
文字の意味に従うと、順序は ^ ^

これら 3 種類のトラバーサルはすべて、常に
より深いところにアクセスするため、再帰的トラバーサル、または深さ優先トラバーサル (深さ優先検索、DFS) です。

事前順序走査の再帰アルゴリズム:

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

順走査の再帰アルゴリズム:

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

事後探索の再帰アルゴリズム:

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

非再帰的な深さ優先探索

実のところ、これらの概念が誰のものなのかはわかりません。一部の本では、バイナリ ツリー トラバーサルに関する上記 3 つの再帰トラバーサルについてのみ説明しています。一部のものは幅優先トラバーサルと深さ優先トラバーサルの 2 つのタイプに分類され、再帰的トラバーサルは深さ優先トラバーサルに分類されます。また、非再帰トラバーサルには幅優先トラバーサルが含まれます。そして次の縦走路。個人的には、メソッドと使用方法をマスターしている限り、分割方法は問題ではありません:)

これに対応して、この非再帰的な深さでは、幅優先トラバーサルで使用したのはキューです。 -first トラバーサルでは、 stack を使用します。 JS でシミュレートするには引き続き配列を使用します。
ここでは予約注文についてのみ説明します。
このアルゴリズムについて説明しようとしましたが、コードに従うだけで理解できるでしょう。

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

この記事を読んだ後、非再帰ポストオーダーアルゴリズムを見つけたので、ここで非再帰トラバーサルメソッドを完了します。

非再帰順

最初に数値の左側のノードをスタックにプッシュし、次にそれを取り出して、次に右側のノードをプッシュします。

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

非再帰ポストオーダー (スタックを使用)

ここでは、最後のプッシュを記録するために一時変数が使用されます/ポップノード。このアイデアは、最初にルート ノードと左側のツリーをスタックにプッシュし、次に左側のツリーを取り出し、次に右側のツリーにプッシュしてそれらを取り出し、最後に次のノードを取り出すことです。

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

非再帰ポストオーダー (2 つのスタックを使用)

このアルゴリズムの考え方は次のように似ています。上の例では、s1 は一時変数に少し似ています。

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

モリストラバーサル

このメソッドは、再帰やスタックを使用せずに 3 つの深さトラバーサルを実装し、空間計算量は O(1 ) (この概念については特に明確ではありません)
(これら 3 つのアルゴリズムは脇に置いて、時間があるときに勉強します)

モリス順序:

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

モリス ミッドオーダー:

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

モリス ポストオーダー:

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

以上ですこの記事の内容全体が皆さんの学習に役立つことを願っています。その他の関連チュートリアルについては、JavaScript ビデオ チュートリアル をご覧ください。