Ağaç Geçişi (Sipariş, Ön Sipariş, Sipariş Sonrası)

Ağaç Geçişi Nedir?

Ağaç veri yapısında, dolaşma (traversal), düğümleri belirli bir şekilde ziyaret etmek anlamına gelir. İki tür dolaşma vardır. Genellikle bu tür dolaşma ikili ağaca dayanır. İkili ağaç, her düğümün en fazla 2 düğüme sahip olabileceği anlamına gelir.

İkili ağaç iyi bilinen bir veri yapısıdır. Ayrıca bir İkili Arama ağacı (BST) vardır. Bu tür geçiş çeşitli amaçlar için kullanılır. Seviye sırası geçişi, iki düğüm arasındaki derinliği hesaplamak için kullanılır. Bir düğümün yüksekliğini hesaplamanın gerekli olduğu "AVL" adı verilen başka bir ağaç türü daha vardır. Dizide bir İkili ağacı temsil edebiliriz, ancak bellek optimizasyonu için bir sonraki düğüme referans vermek üzere yapıyı ve işaretçiyi kullanacağız.

Ağaç Geçişi Türleri

Tartıştığımız gibi ikili ağaçlarŞimdi bireysel geçiş türlerini tartışıyoruz. Türlerine bağlı olarak iki tür geçiş vardır. Daha önce seviye sırasının veya Genişlik-Önce Geçişin gerekliliğinden bahsetmiştik. Şimdi Derinlik-İlk Geçiş Tıpkı post order'ın bir düğümü silmek için kullanılması gibi (bunu daha sonra tartışacağız), preorder'ın bir İkili ağacı kopyalamak için kullanılması gibi ve "inorder" da ağacı azalmayan bir şekilde dolaşacaktır.

• Genişlik-İlk Geçiş
• Derinlik-İlk Geçiş
• Ön sipariş geçişi
• Sipariş sonrası geçiş
• Sıralı geçiş

Genişlik-İlk Geçiş

Ayrıca seviye sırası geçişi olarak da bilinir. Seviye sırası geçişini göstermek için aşağıdaki ağacı ele alalım.

Yani “1” kök düğümünden başlayacağız. Seviye 1 olarak işaretlenecektir. Daha sonra algoritma mevcut düğümün tüm alt öğelerine gidecektir. Şimdi 2. ve 3. düğümleri ziyaret edeceğiz. Seviye 2 olarak işaretlenecekler.

Bundan sonra 2. seviyede 2 düğümümüz olduğu için onların çocuklarını da ziyaret edeceğiz. Yani 5,6,8,7'yi ziyaret edip onları 3. seviye olarak işaretleyeceğiz. Burada bahsetmediğimiz bir şey var,

Düğümün düzeyi = üst düğümün düzeyi + 1

Seviye 1: 1

Seviye 2: 2 3

Seviye 3: 5 6 8 7

BFS için benzer bir algoritma kullanılır (Genişlik-Önce Arama).

İşte seviye sırası geçişi için Sahte kod:

level_order(node)
Q → Queue()
Q.push(node)
while !Q.empty():
    current_node = Q.pop()
    print current_node.value
# Checking if the current node have any child or not
if current_node.left is not NULL:
    Q.push(current_node.left)
if current_node.right is not NULL:
    Q.push(current_node.right)

Sıralı Geçiş İkili Ağacı

Daha önce olduğu gibi aynı örneği verelim. Bu tür geçişte önce sol alt ağacı, sonra kökü ve ardından sağ alt ağacı ziyaret ederiz. Hatırlama kolaylığı açısından sırasıyla sol-kök-sağ şeklinde diyebiliriz.

Ağacın tamamı için kökün 1 olduğunu varsayalım. Şimdi algoritma şu şekilde olacaktır:

• Düğüm 1'in sol alt ağacını ziyaret edin.
• Geçerli düğüm 2'dir (1'in sol alt ağacı olduğu için)

• 2'nin sol alt ağacını ziyaret edin. Mevcut düğüm bu sefer 5 olacaktır.
• 5'e geçildiğinde çocuğu yoktur, bu nedenle 5. düğüm ziyaret edildi olarak işaretlenecektir. Ana düğüme geri dönecektir; hangisi 2.
• 2'nin sol alt ağacı ziyaret edildiğinden artık 2 de ziyaret edilecektir.
• MKS algoritma geçerli düğümü, düğüm 2 olan düğüm 6'nin sağ alt ağacına taşıyacaktır. Düğüm 6'yı ziyaret ettikten sonra, üst düğüm 2'ye taşınacaktır.
• 2. düğüm ziyaret edildiğinden şimdi 2. düğümün ebeveynini ziyaret edeceğiz; bu düğüm 1'dir.
• Bundan sonra sağ alt ağacı ziyaret edeceğiz.

Yani son geçiş şöyle görünecek:

Sırayla: 5 → 2 → 6 → 1 → 8 → 3 → 7

İşte Sıralı geçiş için Sahte kod:

InOrder(node):
  if node is not null:
    InOrder(node.left)
  print node.value
    InOrder(node.right)

Bu, sıralı geçiş için özyinelemeli algoritmadır. İçin İkili Arama Ağacı (BST), Sıralı geçiş değerlerin sıralanmış dizisini verir.

Sipariş Sonrası Geçiş

Bu geçişte, önce en soldaki alt ağacı, ardından kökten sonra en sağdaki alt ağacı geçeceğiz. Tüm geçişler Post-Order'da olacaktır. Bir örnek gösterelim:

Burada kök = 1 için,

• Önce sol alt ağaca gideceğiz. Yani kök 2 olacak.
• Sonra 2'nin alt ağacı kaldı, yani 5. düğüme gideceğiz. Artık kök 5'tir.
• Sol alt ağacı olmadığı gibi sağ alt ağacı da yoktur. Şimdi 5. düğümü ziyaret edildi olarak işaretleyeceğiz ve onun ana düğümüne gideceğiz.

• Artık kök 2'dir ve sol alt ağacı tamamen ziyaret edilmiştir. Şimdi sağ alt ağacına geçeceğiz. Böylece kök 6 olur.
• Düğüm 6'nın sol ve sağ alt ağacı olmadığından, düğüm 6'yı ziyaret ettik ve üst düğüm 2'ye geçeceğiz.
• Şimdi, düğüm 2 için hem sol hem de sağ alt ağaç ziyaret ediliyor. O da ziyaret edildi olarak işaretlenecek.
• Düğüm 2 olan düğüm 1'nin ebeveynine geçeceğiz.
• Kök 1 için sol alt ağaç ziyaret edildi. Şimdi benzer şekilde sağ alt ağacı da ziyaret edeceğiz.

İşaretli daire sağdaki alt ağaçtır. Şimdi sol alt ağacı ziyaret ettiğimiz gibi sağ alt ağacı da ziyaret edeceğiz. Bundan sonra düğümü ziyaret edeceğiz. Yani son geçiş şöyle olacaktır:

Sipariş Sonrası: 5 → 6 → 2 → 8 → 7 → 3 → 1

İşte sipariş sonrası geçiş için Sahte kod:

PostOrder(node):
    if node is not null:
       PostOrder(node.left)
       PostOrder(node.right)
       print node.value

Ön Sipariş Geçişi

Ön sipariş geçişi için algoritma ilk olarak kök düğümü ziyaret edecek, ardından sırasıyla sol ve sağ alt ağaca doğru hareket edecektir. Anlamayı kolaylaştırmak için ön sipariş geçiş ziyaretlerini şöyle düşünebiliriz: kök → sol-sağ.

Öyleyse kök olarak düğüm 1'i seçelim.

• Algoritmaya göre önce kök, sonra sol alt ağaç ve ardından sağ alt ağaç keşfedilecektir.
• Yani kök 1'i ziyaret edeceğiz. Sonra onun sol alt ağacına geçeceğiz. Kök 2 olur.
• 2 numaralı düğümü ziyaret edip sol alt ağacına geçeceğiz. Böylece kök düğüm 3 olacak.
• 3. düğümü ziyaret ediyoruz, ardından ana düğüme geçiyoruz. Şimdi düğüm 2 ve onun sol alt ağacı ziyaret edildi. Sağ alt ağacı ziyaret etme zamanı.
• Sağ alt ağaca gideceğiz, kök 4 olacak. 4'ü ziyaret edeceğiz. 4'ün alt düğümü olmadığı için ebeveynine geçeceğiz.
• Artık kök 2'dir ve sol ve sağ alt ağacıyla birlikte ziyaret edilir. Yani, onun ana düğümüne geçeceğiz. Artık kök 1 olur.
• Benzer şekilde sağ alt ağacı da ziyaret edeceğiz.

Ön Sipariş: 1 → 2 → 3 → 4 → 5 → 6 → 7

İşte öncelikli geçiş için sözde kod:

PreOrder(node):
   if node is not null:
     print node.value
         PreOrder(node.left)
         PreOrder(node.right)

Uygulama Python

class Node:
    def __init__(self, item):
    self.left = None
self.right = None
self.val = item
# creating a tree data structure
def inorder(root):
#checking if the root is null or not
if root:
    inorder(root.left)
# recursively calling left subtree
print(str(root.val) + " ", end = '')
inorder(root.right)
# recursively calling right subtree
def postorder(root):
    if root:
    postorder(root.left)
postorder(root.right)
print(str(root.val) + " ", end = '')
def preorder(root):
    if root:
    print(str(root.val) + " ", end = '')
preorder(root.left)
preorder(root.right)
def levelOrder(root):
    queue = list()
queue.append(root)
while len(queue) >
0:
    current = queue[0]
queue = queue[1: ]
print(str(current.val) + " ", end = "")
if current.left:
    queue.append(current.left)
if current.right:
   queue.append(current.right)
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
print("\nLevelOrder traversal:\t", end = " ")
levelOrder(root)
print("\nInorder traversal:\t", end = " ")
inorder(root)
print("\nPreorder traversal:\t", end = " ")
preorder(root)
print("\nPostorder traversal:\t", end = " ")
postorder(root)

Çıktı:

LevelOrder traversal:  1 2 3 4 5 6 7
Inorder traversal:     4 2 5 1 6 3 7
Preorder traversal:    1 2 4 5 3 6 7
Postorder traversal:   4 5 2 6 7 3 1

C'de Uygulama

#include <stdio.h>
#include <stdlib.h>
struct node {
   int value;
   struct node* left;
   struct node* right;
};
// Inorder traversal
void InOrder(struct node* root) {
   if (root == NULL) return;
   InOrder(root->left);
   printf("%d ", root->value);
   InOrder(root->right);
}
// PreOrder traversal
void PreOrder(struct node* root) {
  if (root == NULL) return;
  printf("%d ", root->value);
  PreOrder(root->left);
  PreOrder(root->right);
}
// PostOrder traversal
void PostOrder(struct node* root) {
  if (root == NULL) return;
  PostOrder(root->left);
  PostOrder(root->right);
  printf("%d ", root->value);
}
// Create a new Node
struct node* createNode(int value) {
  struct node* newNode = malloc(sizeof(struct node));
  newNode->value = value;
  newNode->left = NULL;
  newNode->right = NULL;
  return newNode;
}
int main() {
  struct node* root = createNode(1);
  root->left = createNode(2);
  root->right = createNode(3);
  root->left->left = createNode(4);
  root->left->right = createNode(5);
  root->right->left = createNode(6);
  root->right->right = createNode(7);
  printf("Inorder traversal:\t");
  InOrder(root);
  printf("\PreOrder traversal:\t");
  PreOrder(root);
  printf("\nPostOrder traversal:\t");
  PostOrder(root);
}

Çıktı:

Inorder traversal: 4 2 5 1 6 3 7
Preorder traversal: 1 2 4 5 3 6 7
Postorder traversal: 4 5 2 6 7 3 1

Uygulanması C++ (Seviye sıralaması için std::queue kullanılıyor)

#include <stdio.h>
#include <stdlib.h>
#include<queue>
typedef struct node {
  int value;
  struct node* left;
  struct node* right;
}node;
// Inorder traversal
void InOrder(struct node* root) {
  if (root == NULL) return;
  InOrder(root->left);
  printf("%d ", root->value);
  InOrder(root->right);
}
// PreOrder traversal
void PreOrder(struct node* root) {
  if (root == NULL) return;
  printf("%d ", root->value);
  PreOrder(root->left);
  PreOrder(root->right);
}
// PostOrder traversal
void PostOrder(struct node* root) {
  if (root == NULL) return;
  PostOrder(root->left);
  PostOrder(root->right);
  printf("%d ", root->value);
}
void LevelOrder(struct node* root){
   std::queue<struct node*> Q;
   Q.push(root);
   while(!Q.empty()){
   struct node* current = Q.front();
   Q.pop();
   printf("%d ",current->value);
 if(current->left)
   Q.push(current->left);
 if(current->right)
   Q.push(current->right);
  }
}
// Create a new Node
struct node* createNode(int value) {
  struct node* newNode = new node();
  newNode->value = value;
  newNode->left = NULL;
  newNode->right = NULL;
  return newNode;
}
int main() {
  struct node* root = createNode(1);
  root->left = createNode(2);
  root->right = createNode(3);
  root->left->left = createNode(4);
  root->left->right = createNode(5);
  root->right->left = createNode(6);
  root->right->right = createNode(7);
  printf("Level Order traversal:\t");
  LevelOrder(root);
  printf("\nInorder traversal:\t");
  InOrder(root);
  printf("\nPreOrder traversal:\t");
  PreOrder(root);
  printf("\nPostOrder traversal:\t");
  PostOrder(root);
}

LevelOrder traversal:  1 2 3 4 5 6 7
Inorder traversal:     4 2 5 1 6 3 7
Preorder traversal:    1 2 4 5 3 6 7
Postorder traversal:   4 5 2 6 7 3 1

SSS