JSでのバイナリツリートラバーサルの詳細な説明-jsチュートリアル-php.cn

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

PHPz

リリース： 2018-09-28 15:37:17

オリジナル

1736 人が閲覧しました

二分木はルートノード、左サブツリー、右サブツリーで構成されます。左サブツリーとフレンドサブツリーはそれぞれ二分木です。
この記事では主に 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(&#39;Empty Tree&#39;)
 } 
 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(&#39;Empty Tree&#39;)
 } 
 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(&#39;Empty Tree&#39;)
 } 
 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(&#39;Empty Tree&#39;)
 } 
 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 ビデオチュートリアルをご覧ください。