Veri Yapısı ve Algoritmalar - Ağaç

Ağaç, kenarlarla bağlanan düğümleri temsil eder. Özellikle ikili ağaç veya ikili arama ağacını tartışacağız.

Binary Tree, veri depolama amacıyla kullanılan özel bir veri yapısıdır. İkili ağacın, her düğümün en fazla iki çocuğa sahip olabileceği özel bir koşulu vardır. Arama sıralı bir dizide olduğu kadar hızlı olduğundan ve ekleme veya silme işlemi bağlantılı listedeki kadar hızlı olduğundan, ikili ağaç hem sıralı bir dizinin hem de bağlantılı bir listenin avantajlarına sahiptir.

Önemli Terimler

Ağaçla ilgili önemli terimler aşağıdadır.

Path - Yol, bir ağacın kenarları boyunca düğüm dizisini ifade eder.
Root- Ağacın tepesindeki düğüme kök denir. Ağaç başına yalnızca bir kök ve kök düğümden herhangi bir düğüme giden bir yol vardır.
Parent - Kök düğüm dışındaki herhangi bir düğümün üst adı verilen düğüme yukarı doğru bir kenarı vardır.
Child - Belirli bir düğümün altındaki düğüme, kenarı aşağı doğru bağlanan düğüm, alt düğümü olarak adlandırılır.
Leaf - Herhangi bir alt düğüme sahip olmayan düğüme yaprak düğüm denir.
Subtree - Alt ağaç, bir düğümün soyundan gelenleri temsil eder.
Visiting - Ziyaret, kontrol düğüm üzerindeyken bir düğümün değerinin kontrol edilmesidir.
Traversing - Geçiş, belirli bir sırayla düğümlerden geçmek anlamına gelir.
Levels- Bir düğümün seviyesi, bir düğümün oluşumunu temsil eder. Kök düğüm 0 düzeyindeyse, sonraki alt düğümü düzey 1, torunu düzey 2, vb.
keys - Anahtar, bir düğüm için bir arama işleminin gerçekleştirileceği bir düğümün değerini temsil eder.

İkili Arama Ağacı Gösterimi

İkili Arama ağacı özel bir davranış sergiler. Bir düğümün sol çocuğu, ebeveyninin değerinden daha küçük bir değere sahip olmalı ve düğümün sağ çocuğu, ebeveyn değerinden daha büyük bir değere sahip olmalıdır.

Düğüm nesnesini kullanarak ve bunları referanslar yoluyla birbirine bağlayarak ağacı gerçekleştireceğiz.

Ağaç Düğümü

Bir ağaç düğümü yazma kodu aşağıda verilene benzer olacaktır. Bir veri bölümüne ve sol ve sağ alt düğümlerine referanslara sahiptir.

struct node {
   int data;   
   struct node *leftChild;
   struct node *rightChild;
};

Bir ağaçta, tüm düğümler ortak bir yapı paylaşır.

BST Temel İşlemleri

İkili arama ağacı veri yapısında gerçekleştirilebilecek temel işlemler şunlardır -

Insert - Ağaca bir öğe ekler / bir ağaç oluşturur.
Search - Ağaçtaki bir öğeyi arar.
Preorder Traversal - Bir ağacı önceden sırayla gezer.
Inorder Traversal - Bir ağacı sırayla gezer.
Postorder Traversal - Sipariş sonrası bir şekilde bir ağaçtan geçer.

Bu bölümde bir ağaç yapısı oluşturmayı (içine eklemeyi) ve ağaçtaki bir veri öğesini aramayı öğreneceğiz. İlerleyen bölümde ağaç dolaşma yöntemlerini öğreneceğiz.

İşlem Ekle

İlk yerleştirme ağacı oluşturur. Daha sonra, bir eleman ne zaman eklenecekse, önce uygun yerini bulun. Kök düğümden aramaya başlayın, ardından veri anahtar değerinden düşükse, sol alt ağaçta boş konumu arayın ve verileri ekleyin. Aksi takdirde, sağ alt ağaçta boş konumu arayın ve verileri ekleyin.

Algoritma

If root is NULL 
   then create root node
return

If root exists then
   compare the data with node.data
   
   while until insertion position is located

      If data is greater than node.data
         goto right subtree
      else
         goto left subtree

   endwhile 
   
   insert data
	
end If

Uygulama

Ekleme işlevinin uygulanması şu şekilde görünmelidir -

void insert(int data) {
   struct node *tempNode = (struct node*) malloc(sizeof(struct node));
   struct node *current;
   struct node *parent;

   tempNode->data = data;
   tempNode->leftChild = NULL;
   tempNode->rightChild = NULL;

   //if tree is empty, create root node
   if(root == NULL) {
      root = tempNode;
   } else {
      current = root;
      parent  = NULL;

      while(1) {                
         parent = current;

         //go to left of the tree
         if(data < parent->data) {
            current = current->leftChild;                
            
            //insert to the left
            if(current == NULL) {
               parent->leftChild = tempNode;
               return;
            }
         }
			
         //go to right of the tree
         else {
            current = current->rightChild;
            
            //insert to the right
            if(current == NULL) {
               parent->rightChild = tempNode;
               return;
            }
         }
      }            
   }
}

Arama İşlemi

Bir eleman aranacağı zaman, kök düğümden aramaya başlayın, ardından veri anahtar değerinden düşükse, sol alt ağaçta elemanı arayın. Aksi takdirde, sağ alt ağaçta öğeyi arayın. Her düğüm için aynı algoritmayı izleyin.

Algoritma

If root.data is equal to search.data
   return root
else
   while data not found

      If data is greater than node.data
         goto right subtree
      else
         goto left subtree
         
      If data found
         return node
   endwhile 
   
   return data not found
   
end if

Bu algoritmanın uygulaması şöyle görünmelidir.

struct node* search(int data) {
   struct node *current = root;
   printf("Visiting elements: ");

   while(current->data != data) {
      if(current != NULL)
      printf("%d ",current->data); 
      
      //go to left tree

      if(current->data > data) {
         current = current->leftChild;
      }
      //else go to right tree
      else {                
         current = current->rightChild;
      }

      //not found
      if(current == NULL) {
         return NULL;
      }

      return current;
   }  
}

İkili arama ağacı veri yapısının uygulanmasını öğrenmek için lütfen buraya tıklayın .