İkili ağaç, düğümün en fazla iki çocuğa sahip olabileceği anlamına gelir. Burada ikili ismin kendisi 'iki'yi akla getiriyor; bu nedenle her düğümün 0, 1 veya 2 çocuğu olabilir.

İkili ağacı bir örnek üzerinden anlayalım.

Yukarıdaki ağaç bir ikili ağaçtır çünkü her düğüm en fazla iki çocuğu içerir. Yukarıdaki ağacın mantıksal gösterimi aşağıda verilmiştir:

Yukarıdaki ağaçta, düğüm 1 iki işaretçi içerir; yani sırasıyla sol ve sağ düğümü işaret eden sol ve sağ işaretçi. Düğüm 2, her iki düğümü de (sol ve sağ düğüm) içerir; bu nedenle iki işaretçisi vardır (sol ve sağ). 3, 5 ve 6 numaralı düğümler yaprak düğümlerdir, dolayısıyla tüm bu düğümler şunları içerir: HÜKÜMSÜZ işaretçiyi hem sol hem de sağ kısımlarda kullanın.

İkili Ağacın Özellikleri

• Her i düzeyinde maksimum düğüm sayısı 2'dir^Ben.
• Ağacın yüksekliği kök düğümden yaprak düğüme kadar olan en uzun yol olarak tanımlanır. Yukarıda gösterilen ağacın yüksekliği 3'tür. Dolayısıyla 3 yüksekliğindeki maksimum düğüm sayısı (1+2+4+8) = 15'e eşittir. Genel olarak h yüksekliğinde mümkün olan maksimum düğüm sayısı (2)⁰+ 2¹+ 2²+….2^H) = 2^sa+1-1.
• H yüksekliğinde mümkün olan minimum düğüm sayısı şuna eşittir: sa+1 .
• Düğüm sayısı minimum ise ağacın yüksekliği maksimum olacaktır. Tersine, düğüm sayısı maksimumsa ağacın yüksekliği minimum olacaktır.

İkili ağaçta 'n' sayıda düğüm varsa.

polis komiseri yardımcısı

Minimum yükseklik şu şekilde hesaplanabilir:

Bunu bildiğimize göre,

n = 2^sa+1-1

n+1 = 2^sa+1

Her iki taraftan da kütük alınarak,

kayıt₂(n+1) = log2(2^sa+1)

kayıt₂(n+1) = h+1

h = günlük₂(n+1) - 1

Maksimum yükseklik şu şekilde hesaplanabilir:

java while döngüsü

Bunu bildiğimize göre,

n = sa+1

h= n-1

İkili Ağaç Türleri

Dört tür İkili ağaç vardır:

Tam/uygun/kesin İkili ağaç Tam İkili ağaç Mükemmel İkili ağaç Dejenere İkili ağaç Dengeli İkili ağaç

1. Tam/uygun/kesin İkili ağaç

Tam ikili ağaç aynı zamanda katı ikili ağaç olarak da bilinir. Ağaç yalnızca her düğümün 0 veya 2 çocuk içermesi gerekiyorsa tam ikili ağaç olarak kabul edilebilir. Tam ikili ağaç, yaprak düğümler hariç her düğümün 2 çocuk içermesi gereken ağaç olarak da tanımlanabilir.

Tam İkili ağacın basit örneğine bakalım.

Yukarıdaki ağaçta her düğümün ya sıfır ya da iki çocuk içerdiğini görebiliriz; bu nedenle Tam İkili ağaçtır.

Tam İkili Ağacın Özellikleri

• Yaprak düğümlerin sayısı, iç düğümlerin sayısı artı 1'e eşittir. Yukarıdaki örnekte, iç düğümlerin sayısı 5'tir; bu nedenle yaprak düğümlerin sayısı 6'ya eşittir.
• Maksimum düğüm sayısı ikili ağaçtaki düğüm sayısıyla aynıdır, yani 2^sa+1-1.
• Tam ikili ağaçtaki minimum düğüm sayısı 2*h-1'dir.
• Tam ikili ağacın minimum yüksekliği kayıt₂(n+1) - 1.
• Tam ikili ağacın maksimum yüksekliği şu şekilde hesaplanabilir:

n= 2*sa - 1

n+1 = 2*sa

boolean'ı dizeye dönüştür

h = n+1/2

Tam İkili Ağaç

Tam ikili ağaç, son seviye hariç tüm düğümlerin tamamen dolu olduğu bir ağaçtır. Son seviyede tüm düğümlerin mümkün olduğu kadar solda olması gerekir. Tam bir ikili ağaçta düğümler soldan eklenmelidir.

java'da yığın nedir

Tam bir ikili ağaç oluşturalım.

Yukarıdaki ağaç tam bir ikili ağaçtır çünkü tüm düğümler tamamen doludur ve son seviyedeki tüm düğümler önce sol tarafa eklenir.

Tam İkili Ağacın Özellikleri

• Tam ikili ağaçtaki maksimum düğüm sayısı 2'dir^sa+1- 1.
• Tam ikili ağaçtaki minimum düğüm sayısı 2'dir^H.
• Tam bir ikili ağacın minimum yüksekliği kayıt₂(n+1) - 1.
• Tam bir ikili ağacın maksimum yüksekliği

Mükemmel İkili Ağaç

Bir ağaç, tüm iç düğümlerin 2 çocuğu varsa ve tüm yaprak düğümleri aynı seviyedeyse mükemmel bir ikili ağaçtır.

Mükemmel bir ikili ağacın basit bir örneğine bakalım.

Aşağıdaki ağaç mükemmel bir ikili ağaç değildir çünkü tüm yaprak düğümleri aynı seviyede değildir.

Not: Tüm mükemmel ikili ağaçlar, tam ikili ağaçların yanı sıra tam ikili ağaçlardır, ancak bunun tersi doğru değildir, yani tüm tam ikili ağaçlar ve tam ikili ağaçlar mükemmel ikili ağaçlardır.

Dejenere İkili Ağaç

Dejenere ikili ağaç, tüm iç düğümlerin yalnızca bir çocuğa sahip olduğu bir ağaçtır.

Dejenere ikili ağacı örneklerle anlayalım.

Yukarıdaki ağaç dejenere bir ikili ağaçtır çünkü tüm düğümlerin yalnızca bir çocuğu vardır. Tüm düğümlerin yalnızca sağ çocuğu olduğundan sağa çarpık ağaç olarak da bilinir.

Yukarıdaki ağaç aynı zamanda dejenere bir ikili ağaçtır çünkü tüm düğümlerin yalnızca bir çocuğu vardır. Tüm düğümlerin yalnızca sol çocuğu olduğundan sola çarpık ağaç olarak da bilinir.

Dengeli İkili Ağaç

java tatili

Dengeli ikili ağaç, hem sol hem de sağ ağaçların en fazla 1 farklılık gösterdiği bir ağaçtır. Örneğin, AVL Ve Kırmızı-Siyah ağaçlar dengeli ikili ağaçtır.

Dengeli ikili ağacı örneklerle anlayalım.

Yukarıdaki ağaç dengeli bir ikili ağaçtır çünkü sol alt ağaç ile sağ alt ağaç arasındaki fark sıfırdır.

Yukarıdaki ağaç dengeli bir ikili ağaç değildir çünkü sol alt ağaç ile sağ alt ağaç arasındaki fark 1'den büyüktür.

İkili Ağaç Uygulaması

İşaretçilerin yardımıyla bir İkili ağaç uygulanır. Ağaçtaki ilk düğüm kök işaretçisi ile temsil edilir. Ağaçtaki her düğüm üç bölümden oluşur; yani veri, sol işaretçi ve sağ işaretçi. İkili ağaç oluşturmak için öncelikle düğümü oluşturmamız gerekir. Aşağıda gösterildiği gibi kullanıcı tanımlı düğümü oluşturacağız:

 struct node { int data, struct node *left, *right; } 

Yukarıdaki yapıda, veri değerdir, sol işaretçi sol düğümün adresini içerir ve sağ işaretçi sağ düğümün adresini içerir.

C'de İkili Ağaç programı

 #include struct node { int data; struct node *left, *right; } void main() { struct node *root; root = create(); } struct node *create() { struct node *temp; int data; temp = (struct node *)malloc(sizeof(struct node)); printf('Press 0 to exit'); printf('
Press 1 for new node'); printf('Enter your choice : '); scanf('%d', &choice); if(choice==0) { return 0; } else { printf('Enter the data:'); scanf('%d', &data); temp->data = data; printf('Enter the left child of %d', data); temp->left = create(); printf('Enter the right child of %d', data); temp->right = create(); return temp; } } 

Yukarıdaki kod, create() işlevini yinelemeli olarak çağırıyor ve her yinelemeli çağrıda yeni düğüm yaratıyor. Tüm düğümler oluşturulduğunda ikili ağaç yapısı oluşur. Düğümleri ziyaret etme işlemi ağaç geçişi olarak bilinir. Bir düğümü ziyaret etmek için kullanılan üç tür geçiş vardır:

• Sıralı geçiş
• Ön sipariş geçişi
• Posta siparişi geçişi