Penjelasan terperinci tentang traversal pokok binari dalam JS

Pokok binari terdiri daripada nod akar, subpokok kiri dan subpokok kanan Subpokok kiri dan subpokok rakan ialah setiap pokok binari.
Artikel ini terutamanya melaksanakan traversal pokok binari dalam JS.

Contoh pokok binari

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

Breadth-first traversal

Breadth Priority traversal bermula dari peringkat pertama (nod akar) pokok binari dan melintasi peringkat demi tahap dari atas ke bawah dalam tahap yang sama, nod dilawati satu demi satu mengikut urutan dari kiri ke kanan;

Pelaksanaan:

Gunakan tatasusunan untuk mensimulasikan baris gilir. Mula-mula masukkan nod akar ke dalam baris gilir. Apabila baris gilir tidak kosong, laksanakan gelung: keluarkan nod daripada baris gilir, dan jika subpokok kiri nod tidak kosong, letakkan subpokok kiri nod ke dalam baris gilir jika subpokok kanan nod itu; Jika ia tidak kosong, letakkan subpokok kanan nod ke dalam baris gilir.
(Penerangan agak tidak jelas, lihat kod sahaja.)

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

Rekursif traversal

Saya rasa macam menggunakan huruf ini Terdapat tiga cara yang baik untuk menyatakan traversal rekursif:
D: melawati nod akar, L: melintasi subpokok kiri nod akar, R: melintasi subpokok kanan nod akar.
Prepesan traversal: DLR
In-order traversal: LDR
Post-order traversal: LRD
Mengikuti maksud huruf, ia adalah traversal. Secara tertib^ ^

Tiga jenis traversal ini semuanya adalah traversal rekursif, atau depth-first search (DFS), kerana ia sentiasa
mula-mula mengakses lebih dalam.

Algoritma rekursif untuk traversal prapesanan:

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

Algoritma rekursif untuk traversal tertib:

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

Algoritma rekursif untuk lintasan pasca pesanan:

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

Traversal pertama mendalam bukan rekursif

Malah, kerana saya tidak pasti konsep ini milik siapa. Sesetengah buku hanya bercakap tentang tiga traversal rekursif di atas untuk traversal pokok binari. Ada yang dibahagikan kepada dua jenis: lintasan lebar-pertama dan lintasan-dalam-pertama, dan lintasan rekursif dibahagikan kepada lintasan kedalaman; lintasan rekursif dan lintasan bukan rekursif termasuk lintasan lebar-pertama dan lintasan berikut. Secara peribadi, saya fikir ia tidak kira bagaimana anda membahagikannya, asalkan anda menguasai kaedah dan penggunaan:)

Apa yang baru sahaja kami gunakan dalam lintasan pertama adalah baris gilir. rekursif depth-first traversal, kami menggunakan stack . Masih menggunakan tatasusunan untuk mensimulasikannya dalam JS.
Di sini kita hanya bercakap tentang prapesanan:
Nah, saya cuba menerangkan algoritma ini, tetapi ia tidak jelas. Ikuti kod dan anda akan faham.

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

Selepas membaca artikel ini, saya menemui algoritma pasca pesanan bukan rekursif, jadi saya akan melengkapkan kaedah traversal bukan rekursif di sini.

Tertib bukan rekursif

Mula-mula tolak nod kiri nombor ke dalam tindanan, kemudian keluarkannya dan kemudian tolak nod kanan.

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

Paspesanan bukan rekursif (menggunakan tindanan)

Pembolehubah sementara digunakan di sini untuk merekodkan tolakan terakhir/ nod pop. Ideanya adalah untuk mula-mula menolak nod akar dan pokok kiri ke atas timbunan, kemudian keluarkan pokok kiri, kemudian tolak ke dalam pokok kanan, keluarkannya, dan akhirnya ambil nod berikut.

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

Paspesanan bukan rekursif (menggunakan dua tindanan)

Idea ​​algoritma ini serupa dengan yang di atas, s1 adalah sedikit seperti Pembolehubah sementara.

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 traversal

Kaedah ini melaksanakan tiga depth traversal tanpa rekursi atau tindanan, dan kerumitan ruang ialah O(1 ) ( Saya tidak begitu jelas tentang konsep ini)
(Saya akan meninggalkan ketiga-tiga algoritma ini dan mengkajinya apabila saya mempunyai masa)

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