JavaScript'te Ağaç Geçişini Keşfetmek: Örneklerle Inorder, Preorder ve Postorder

Ağaç geçişi, bilgisayar biliminde bir ağaç veri yapısındaki her düğümün sistematik olarak ziyaret edilmesini içeren temel bir kavramdır. Ağaç geçişi aracılığıyla, düğümleri önceden belirlenmiş bir sırayla işleyebilir, ifadeleri arama, sıralama ve değerlendirme gibi işlemleri kolaylaştırabiliriz.

Bu makalede en yaygın kullanılan ağaç geçiş yöntemlerinden üçünü inceleyeceğiz: inorder, preorder ve postorder.

JavaScript'te uygulanan açık ve özlü örnekler sayesinde bu geçiş tekniklerini sağlam bir şekilde anlayacaksınız.

Ağaç Yapısı Tanımı

Ağaç geçiş algoritmalarına dalmadan önce ikili ağaç için kullanacağımız yapıyı tanımlayalım. Ağaç, her düğümün bir değer içerdiği ve sol ve sağ alt düğümlerine referanslar içerdiği düğümlerden oluşacaktır.

 function TreeNode(val = 0, left = null, right = null) { this.val = val; this.left = left; this.right = right; }

Artık ağaç yapısını tanımladığımıza göre üç ağaç geçiş yöntemini keşfetmeye devam edebiliriz.

Sıralı Geçiş

Sıralı geçiş, bir ikili ağaçtaki düğümleri ziyaret etmenin bir sonraki modelini takip eder - algoritma önce sol alt ağacı geçer, ardından mevcut düğümü ziyaret eder ve son olarak sağ alt ağacı geçer. Bu, ağacın sıralanmış bir veri yapısını temsil etmesi durumunda düğümlerin artan sırada ziyaret edilmesini sağlar.

 A / \ BC / \ / \ DEFG // Inorder traversal result: D -> B -> E -> A -> F -> C -> G

Özyinelemeli Sıralı Geçiş

1. Geçerli düğümün boş olup olmadığını kontrol edin. Eğer öyleyse geri dönün.

   
   

2. Sol alt ağaçtaki işlevi yinelemeli olarak çağırın.

   
   

3. Geçerli düğümü ziyaret edin.

   
   

4. Sağ alt ağaçtaki işlevi yinelemeli olarak çağırın.

 function inorderRecursive(tree) { const result = []; function inorderTraverse(node) { if (!node) return; inorderTraverse(node.left); result.push(node.val); inorderTraverse(node.right); } inorderTraverse(tree); return result; }

Özyinelemeli Olmayan Sıralı Geçiş

1. Boş bir yığın başlatın ve geçerli düğümü ağacın köküne ayarlayın.

   
   

2. Yığın boş değilken veya geçerli düğüm boş değilken yineleyin.

   • Boş bir sol çocuğa ulaşana kadar tüm sol düğümleri yığının üzerine itin.

   • Yığından bir düğüm açın, onu ziyaret edin ve mevcut düğümü sağ alt düğüme ayarlayın.

     
     

3. Yığın boşalana ve geçerli düğüm boş olana kadar 2. adımı tekrarlayın.

 function inorderRecursive(tree) { const stack = []; const result = []; let currentNode = tree; while (currentNode || stack.length) { while (currentNode) { stack.push(currentNode); currentNode = currentNode.left; } const node = stack.pop(); result.push(node.val); currentNode = node.right; } return result; }

Ön Sipariş Geçişi

Ön sipariş geçişinde, algoritma önce mevcut düğümü ziyaret eder, ardından sol alt ağacı geçer ve son olarak sağ alt ağacı geçer. Bu sıralama, düğümlerin kökten başlayıp yapraklara doğru "yukarıdan aşağıya" bir şekilde ziyaret edilmesini sağlar.

 A / \ BC / \ / \ DEFG // Preorder traversal result: A -> B -> D -> E -> C -> F -> G

Yinelemeli Ön Sipariş Geçişi

1. Geçerli düğümün boş olup olmadığını kontrol edin. Eğer öyleyse geri dönün.

   
   

2. Geçerli düğümü ziyaret edin.

   
   

3. Sol alt ağaçtaki işlevi yinelemeli olarak çağırın.

   
   

4. Sağ alt ağaçtaki işlevi yinelemeli olarak çağırın.

   
   

 function preorderRecursive(tree) { const result = []; function preorderTraverse(node) { if (!node) return; result.push(node.val); preorderTraverse(node.left); preorderTraverse(node.right); } preorderTraverse(tree); return result; }

Tekrarlanmayan Ön Sipariş Geçişi

1. Boş bir yığınla başlayın ve kök düğümü yığının üzerine itin.

   
   

2. Ön sipariş geçiş sonucunu depolamak için boş bir dizi başlatın.

   
   

3. Yığın boşalana kadar çalışacak bir while döngüsü girin.

   
   

4. Yığından bir düğüm açın ve değerini sonuç dizisine ekleyerek onu ziyaret edin.

   
   

5. Düğümün sağ çocuğu varsa sağ çocuğu yığına itin.

   
   

6. Düğümün bir sol çocuğu varsa, sol çocuğu yığının üzerine itin.

   
   

7. Yığın boşalana kadar 3-6 arasındaki adımları tekrarlayın.

 function preorderTraversal(root) { if (!root) return []; const stack = [root]; const result = []; while (stack.length) { const node = stack.pop(); result.push(node.val); if (node.right) stack.push(node.right); if (node.left) stack.push(node.left); } return result; }

Sipariş Sonrası Geçiş

Bu geçişte, algoritma önce sol alt ağacı, ardından sağ alt ağacı geçer ve son olarak mevcut düğümü ziyaret eder. Bu sıralama, düğümlerin yapraklardan başlayıp köke doğru "aşağıdan yukarıya" bir şekilde ziyaret edilmesini sağlar.

 A / \ BC / \ / \ DEFG // Postorder traversal result: D -> E -> B -> F -> G -> C -> A

Özyinelemeli Postorder Geçişi

1. Geçerli düğümün boş olup olmadığını kontrol edin. Eğer öyleyse geri dönün.

   
   

2. Sol alt ağaçtaki işlevi yinelemeli olarak çağırın.

   
   

3. Sağ alt ağaçtaki işlevi yinelemeli olarak çağırın.

   
   

4. Geçerli düğümü ziyaret edin.

 function postorderRecursive(tree) { const result = []; function postorderTraverse(node) { if (!node) return; postorderTraverse(node.left); postorderTraverse(node.right); result.push(node.val); } postorderTraverse(tree); return result; }

Tekrarlı Olmayan Sipariş Sonrası Geçiş

1. Boş bir yığınla başlayın ve kök düğümü yığının üzerine itin.

   
   

2. Sipariş sonrası geçiş sonucunu depolamak için boş bir dizi başlatın.

   
   

3. Yığın boşalana kadar çalışacak bir while döngüsü girin.

   
   

4. Yığından en üstteki düğümü alın (çıkarmadan).

   
   

5. Düğümün sol çocuğu varsa, sol çocuğu yığına itin ve geçerli düğümün sol çocuğunu null olarak ayarlayın.

   
   

6. Düğümün sağ çocuğu varsa, sağ çocuğu yığına itin ve geçerli düğümün sağ çocuğunu null olarak ayarlayın.

   
   

7. Düğümün ne sağ ne de sol çocuğu varsa bu bir yaprak düğümdür. Düğümü yığından çıkarın ve değerini sonuç dizisine ekleyin.

   
   

8. Yığın boşalana kadar 4-7 arasındaki adımları tekrarlayın.

 function postorderTraversal(root) { if (!root) return []; const stack = [root]; const result = []; while (stack.length) { const node = stack[stack.length - 1]; if (node.left) { stack.push(node.left); node.left = null; } else if (node.right) { stack.push(node.right); node.right = null; } else { result.push(stack.pop().val); } } return result; }

Çözüm

Umarım artık JavaScript'te inorder, preorder ve postorder geçişi arasındaki farkları net bir şekilde anlamışsınızdır. Sağlanan bilgi ve örneklerle artık bu teknikleri kendi görev ve projelerinize etkili bir şekilde uygulayabilecek donanıma sahipsiniz.