Menü

C ++ 'da İkili Ağaç Veri Yapısı

  • Ana
  • Diğer
  • C ++ 'da İkili Ağaç Veri Yapısı

binary tree data structure c

Sorunları Ortadan Kaldırmak Için Enstrümanımızı Deneyin

C ++ 'da İkili Ağaç Üzerine Bu Derinlemesine Eğitim, C ++' da İkili Ağaçların Türlerini, Temsilini, Geçişini, Uygulamalarını ve Uygulamasını Açıklar:

İkili ağaç, yaygın olarak kullanılan bir ağaç veri yapısıdır. Bir ağacın her düğümü en fazla iki alt düğüme sahip olduğunda, ağaca İkili ağaç denir.

Dolayısıyla, tipik bir ikili ağaç aşağıdaki bileşenlere sahip olacaktır:

  • Bir sol alt ağaç
  • Bir kök düğüm
  • Sağ alt ağaç

=> Bu Serideki C ++ Öğreticilerinin Tam Listesine Dikkat Edin.

C ++

Ne öğreneceksin:

C ++ 'da İkili Ağaç

Bir ikili ağacın resimli bir temsili aşağıda gösterilmiştir:

Bir İkili Ağacın resimsel gösterimi

Verilen bir ikili ağaçta, herhangi bir seviyedeki maksimum düğüm sayısı 2'dir.l-1burada 'l' seviye numarasıdır.

Dolayısıyla, 1. seviyede kök düğüm olması durumunda, maksimum düğüm sayısı = 21-1= 20= 1

İkili ağaçtaki her düğümün en fazla iki düğümü olduğundan, bir sonraki düzeydeki maksimum düğüm 2 * 2 olacaktır.l-1.

android için en iyi ücretsiz müzik indirici

Derinliği veya yüksekliği olan bir ikili ağaç verildiğinde, yüksekliği h = 2 olan bir ikili ağaçtaki maksimum düğüm sayısıh- 1.

Dolayısıyla, yüksekliği 3 olan ikili ağaçta (yukarıda gösterilmiştir), maksimum düğüm sayısı = 23-1 = 7.

Şimdi çeşitli ikili ağaç türlerini tartışalım.

İkili Ağaç Türleri

Aşağıdakiler en yaygın ikili ağaç türleridir.

# 1) Tam İkili Ağaç

Her düğümün 0 veya 2 çocuğa sahip olduğu bir ikili ağaç, tam bir ikili ağaç olarak adlandırılır.

Tam ikili ağaç

Yukarıda, yaprak düğümleri dışındaki tüm düğümlerinin iki çocuğu olduğunu görebildiğimiz tam bir ikili ağaç gösterilmektedir. L, yaprak düğümlerin sayısı ve 'l', dahili veya yaprak olmayan düğümlerin sayısı ise, o zaman tam bir ikili ağaç için, L = l + 1.

# 2) İkili Ağacı Tamamla

Tam bir ikili ağaç, son seviye haricinde doldurulmuş tüm seviyelere sahiptir ve son seviye, soldaki kadar tüm düğümlerine sahiptir.

İkili ağacı tamamla

Yukarıda gösterilen ağaç tam bir ikili ağaçtır. Tam bir ikili ağacın tipik bir örneği, sonraki öğreticilerde tartışacağımız ikili bir yığındır.

# 3) Mükemmel İkili Ağaç

İkili ağaç, tüm iç düğümlerinin iki çocuğu olduğunda ve tüm yaprak düğümleri aynı seviyede olduğunda mükemmel olarak adlandırılır.

Mükemmel ikili ağaç

Yukarıda gösterilen ikili ağaç örneği, her bir düğümünün iki çocuğu olduğu ve tüm yaprak düğümleri aynı seviyede olduğu için mükemmel bir ikili ağaçtır.

H yüksekliğine sahip mükemmel bir ikili ağaçta 2h- 1 düğüm sayısı.

# 4) Bozulmuş Bir Ağaç

Her iç düğümün yalnızca bir çocuğa sahip olduğu bir ikili ağaca dejenere ağaç denir.

Yozlaşmış bir ağaç

Yukarıda gösterilen ağaç, dejenere bir ağaçtır. Bu ağacın performansı söz konusu olduğunda, yozlaşmış ağaçlar bağlantılı listelerle aynıdır.

# 5) Dengeli İkili Ağaç

Her düğümün iki alt ağacının derinliğinin hiçbir zaman 1'den fazla farklılık göstermediği bir ikili ağaca dengeli ikili ağaç denir.

Dengeli ikili ağaç

Yukarıda gösterilen ikili ağaç, her düğümün iki alt ağacının derinliği 1'den fazla olmadığı için dengeli bir ikili ağaçtır. Sonraki derslerimizde tartışacağımız AVL ağaçları, ortak dengeli bir ağaçtır.

İkili Ağaç Gösterimi

İkili ağaç, hafızaya iki şekilde tahsis edilir.

# 1) Sıralı Temsil

Bu, bir ağaç veri yapısını depolamak için en basit tekniktir. Ağaç düğümlerini saklamak için bir dizi kullanılır. Bir ağaçtaki düğüm sayısı, dizinin boyutunu belirler. Ağacın kök düğümü, dizideki ilk dizinde saklanır.

sql sorguları mülakat soruları ve cevapları pdf

Genel olarak, bir düğüm i adresinde saklanıyorsaincikonum ise sol ve sağ çocuk sırasıyla 2i ve 2i + 1 konumunda saklanır.

Aşağıdaki İkili Ağacı düşünün.

Örnek İkili Ağaç

Yukarıdaki ikili ağacın sıralı temsili aşağıdaki gibidir:

ikili ağacın sıralı gösterimi

Yukarıdaki gösterimde, her bir düğümün sol ve sağ çocuklarının sırasıyla 2 * (düğüm_konumu) ve 2 * (düğüm_konumu) +1 konumlarında saklandığını görüyoruz.

Örneğin, dizideki 3. düğümün konumu 3'tür. Yani sol çocuğu 2 * 3 = 6'ya yerleştirilecektir. Sağ çocuğu 2 * 3 +1 = 7 konumunda olacaktır. Dizide de görebileceğimiz gibi çocuklar 6 ve 7 olan 3, dizide 6 ve 7 konumuna yerleştirilir.

Ağaç düğümlerini saklamak için kullanılan dizi bellekte çok yer kapladığından ağacın sıralı gösterimi verimsizdir. Ağaç büyüdükçe, bu temsil verimsiz hale gelir ve yönetilmesi zorlaşır.

Bu dezavantaj, ağaç düğümlerinin bağlantılı bir listede depolanmasıyla aşılır. Ağaç boşsa, kök düğümü depolayan ilk konumun 0 olarak ayarlanacağını unutmayın.

# 2) Bağlantılı Liste Temsili

Bu tür bir temsilde, ağaç düğümlerini saklamak için bağlantılı bir liste kullanılır. Birkaç düğüm bellekte bitişik olmayan konumlara dağılmıştır ve düğümler bir ağaç gibi ebeveyn-çocuk ilişkisi kullanılarak bağlanır.

Aşağıdaki diyagram, bir ağaç için bağlantılı bir liste temsilini göstermektedir.

Bağlantılı liste gösterimi

Yukarıdaki gösterimde gösterildiği gibi, her bağlantılı liste düğümünün üç bileşeni vardır:

  • Sol işaretçi
  • Veri bölümü
  • Sağ işaretçi

Sol işaretçinin düğümün sol çocuğuna bir işaretçisi vardır; Sağ işaretçi, düğümün sağ çocuğuna bir göstericiye sahipken, veri bölümü düğümün gerçek verilerini içerir. Belirli bir düğüm (yaprak düğüm) için çocuk yoksa, o düğüm için sol ve sağ işaretçiler yukarıdaki şekilde gösterildiği gibi boş olarak ayarlanır.

C ++ 'da İkili Ağaç Uygulaması

Daha sonra, C ++ 'da bağlantılı bir liste gösterimi kullanarak bir ikili ağaç programı geliştiriyoruz. Tek bir düğümü bildirmek için bir yapı kullanırız ve ardından bir sınıf kullanarak bağlantılı bir düğüm listesi geliştiririz.

#include using namespace std; struct bintree_node{ bintree_node *left; bintree_node *right; int data; } ; class bst{ bintree_node *root; public: bst(){ root=NULL; } int isempty() { return(root==NULL); } void insert(int item); void displayBinTree(); void printBinTree(bintree_node *); }; void bst::insert(int item){ bintree_node *p=new bintree_node; bintree_node *parent; p->data=item; p->left=NULL; p->right=NULL; parent=NULL; if(isempty()) root=p; else{ bintree_node *ptr; ptr=root; while(ptr!=NULL){ parent=ptr; if(item>ptr->data) ptr=ptr->right; else ptr=ptr->left; } if(itemdata) parent->left=p; else parent->right=p; } } void bst::displayBinTree(){ printBinTree(root); } void bst::printBinTree(bintree_node *ptr){ if(ptr!=NULL){ printBinTree(ptr->left); cout<<' '<data<<' '; printBinTree(ptr->right); } } int main(){ bst b; b.insert(20); b.insert(10); b.insert(5); b.insert(15); b.insert(40); b.insert(45); b.insert(30); cout<<'Binary tree created: '<

Çıktı:

İkili ağaç oluşturuldu:

5 10 15 20 30 40 45

İkili Ağaç Geçişi

Ağaçlarla ilgili temel eğitimimizde geçişleri zaten tartışmıştık. Bu bölümde, ikili ağaca düğümler ekleyen ve ayrıca ikili ağaç için üç geçişi, yani inorder, önsıra ve postorder gösteren bir program uygulayalım.

#include using namespace std; //binary tree node declaration struct bintree_node{ bintree_node *left; bintree_node *right; char data; } ; class bintree_class{ bintree_node *root; public: bintree_class(){ root=NULL; } int isempty() { return(root==NULL); } void insert_node(int item); void inorder_seq(); void inorder(bintree_node *); void postorder_seq(); void postorder(bintree_node *); void preorder_seq(); void preorder(bintree_node *); }; void bintree_class::insert_node(int item){ bintree_node *p=new bintree_node; bintree_node *parent; p->data=item; p->left=NULL; p->right=NULL; parent=NULL; if(isempty()) root=p; else{ bintree_node *ptr; ptr=root; while(ptr!=NULL) { parent=ptr; if(item>ptr->data) ptr=ptr->right; else ptr=ptr->left; } if(itemdata) parent->left=p; else parent->right=p; } } void bintree_class::inorder_seq() { inorder(root); } void bintree_class::inorder(bintree_node *ptr) { if(ptr!=NULL){ inorder(ptr->left); cout<<' '<data<<' '; inorder(ptr->right); } } void bintree_class::postorder_seq() { postorder(root); } void bintree_class::postorder(bintree_node *ptr) { if(ptr!=NULL){ postorder(ptr->left); postorder(ptr->right); cout<<' '<data<<' '; } } void bintree_class::preorder_seq() { preorder(root); } void bintree_class::preorder(bintree_node *ptr) { if(ptr!=NULL){ cout<<' '<data<<' '; preorder(ptr->left); preorder(ptr->right); } } int main() { bintree_class bintree; bintree.insert_node('A'); bintree.insert_node('B'); bintree.insert_node('C'); bintree.insert_node('D'); bintree.insert_node('E'); bintree.insert_node('F'); bintree.insert_node('G'); cout<<'Inorder traversal:'<

Çıktı:

Sıra geçişi:

A B C D E F G

Posta siparişi geçişi:

G F E D C B A

Ön sipariş geçişi:

A B C D E F G

İkili Ağacın Uygulamaları

Veri depolamak için birçok uygulamada ikili ağaç kullanılır.

İkili ağaçların bazı önemli uygulamaları aşağıda listelenmiştir:

  • İkili Arama Ağaçları: İkili ağaçlar, birçok dil kitaplığındaki kümeler ve haritalar gibi birçok arama uygulamasında kullanılan ikili bir arama ağacı oluşturmak için kullanılır.
  • Hash Ağaçları: Karmaları doğrulamak için esas olarak özel görüntü imza uygulamalarında kullanılır.
  • Yığınlar: Yığınlar, yönlendiriciler, işletim sistemindeki zamanlama işlemcileri vb. İçin kullanılan öncelik sıralarını uygulamak için kullanılır.
  • Huffman Kodlaması: Huffman kodlama ağacı, sıkıştırma algoritmalarında (görüntü sıkıştırma gibi) ve kriptografik uygulamalarda kullanılır.
  • Sözdizimi Ağacı: Derleyiciler genellikle programda kullanılan ifadeleri ayrıştırmak için ikili ağaçlardan başka bir şey olmayan sözdizimi ağaçları oluşturur.

Sonuç

İkili ağaçlar, yazılım endüstrisinde yaygın olarak kullanılan veri yapılarıdır. İkili ağaçlar, düğümleri en fazla iki alt düğüme sahip olan ağaçlardır. Tam bir ikili ağaç, tam bir ikili ağaç, mükemmel bir ikili ağaç, dejenere bir ikili ağaç, dengeli bir ikili ağaç vb. Gibi çeşitli ikili ağaç türlerini gördük.

İkili ağaç verileri, önceki eğitimimizde gördüğümüz inorder, ön sipariş ve postorder geçiş teknikleri kullanılarak da taranabilir. Bellekte, bir ikili ağaç, bağlantılı bir liste (bitişik olmayan bellek) veya diziler (sıralı gösterim) kullanılarak temsil edilebilir.

Bağlantılı liste gösterimi, dizilerle karşılaştırıldığında daha verimlidir, çünkü diziler çok yer kaplar.

=> En İyi C ++ Eğitim Öğreticilerine Buradan Göz Atın.

Önerilen Kaynaklar

^