Tam ikili ağaç nedir?
Tam bir ikili ağaç şu şekilde tanımlanabilir: ikili ağaç tüm düğümlerin 0 veya iki çocuğu olduğu. Başka bir deyişle tam ikili ağaç, yaprak düğümler dışındaki tüm düğümlerin iki çocuğa sahip olduğu bir ikili ağaç olarak tanımlanabilir.
Aşağıdaki ağaç tam bir ikili ağaçtır:
Yaprak düğümler dışındaki tüm düğümlerin iki çocuğu olduğundan yukarıdaki ağaç tam bir ikili ağaçtır.
Tam İkili ağaç teoremi:
vlc medya oynatıcı indir youtube
O halde T İkili ağacının boş olmayan bir ağaç olduğunu düşünün:
- I bir ağaçtaki iç düğümler ve L de bir ağaçtaki yaprak düğümü olsun, o zaman yaprak düğümlerinin sayısı şuna eşit olacaktır:
L = ben + 1 - Eğer T, I dahili düğüm sayısı ve N toplam düğüm sayısı ise, o zaman toplam düğüm sayısı şuna eşit olacaktır:
N = 2I + 1 - T, 'N' toplam düğüm sayısını ve dahili düğümlerin sayısını gösteren 'I'yi içeriyorsa, dahili düğümlerin sayısı şuna eşit olacaktır:
ben = (N-1)/2 - 'T', 'N' toplam düğüm sayısına sahipse ve 'L', yaprak düğümlerin sayısı ise, o zaman yaprak düğümlerin sayısı şuna eşit olacaktır:
L = (N+1)/2 - 'T', 'L' sayıda yaprak düğüm içeriyorsa, toplam düğüm sayısı şuna eşit olacaktır:
N = 2L - 1 - 'T', 'L' sayıda yaprak düğüme sahipse ve 'I', bir dizi dahili düğümse, o zaman dahili düğümlerin sayısı şuna eşit olacaktır:
ben = L - 1
Tam ikili ağaç nedir?
Soldan doldurulan son düzey dışında tüm düzeyler tamamen dolduğunda, ikili ağacın tam ikili ağaç olduğu söylenir.
Aşağıdaki ağaç tam bir ikili ağaçtır:
Tam ikili ağaç, aşağıda verilen iki fark dışında tam ikili ağaca benzer:
- Yaprak düğümünün doldurulması en sol taraftan başlamalıdır.
- Son yaprak düğümün doğru kardeşe sahip olması zorunlu değildir.
Yukarıdaki noktaları bir örnek üzerinden anlayalım:
tat tam formu
Aşağıdaki ağacı düşünün:
Yukarıdaki ağaç tam bir ikili ağaçtır, ancak 6. düğümün sağ kardeşi olmadığından tam bir ikili ağaç değildir.
java operatörleri
Tam İkili Ağacın Oluşturulması
Aşağıda gösterilen 6 öğeden oluşan bir dizimiz olduğunu varsayalım:
Yukarıdaki dizi 6 öğe içerir, yani 1, 2, 3, 4, 5, 6. Tam bir ikili ağaç oluşturmak için kullanılacak adımlar aşağıdadır:
Aşama 1: Öncelikle dizinin ilk elemanını (1) seçeceğiz ve ağacın kök düğümünü oluşturacağız. Birinci seviyede mevcut olan eleman sayısı 1'dir.
Adım 2: Şimdi dizinin ikinci ve üçüncü elemanlarını seçeceğiz. Dizinin ikinci ve üçüncü öğesini aşağıda gösterildiği gibi sırasıyla kök düğümün sol ve sağ çocuğu olarak tutun:
Yukarıda gördüğümüz gibi ikinci seviyede bulunan eleman sayısı 2'dir.
Aşama 3: Şimdi diziden sonraki iki öğeyi, yani 4 ve 5'i seçeceğiz. Bu iki öğeyi, aşağıda gösterildiği gibi düğüm 2'nin solunda ve sağında tutun:
Yukarıda görebildiğimiz gibi 4 ve 5 numaralı düğümler sırasıyla 2 numaralı düğümün sol ve sağ çocuğudur.
Adım 4: Şimdi dizinin son elemanını, yani 6'yı seçeceğiz ve onu 3. düğümün sol çocuğu olarak tutacağız çünkü tam bir ikili ağaçta düğümlerin aşağıda gösterildiği gibi sol taraftan doldurulduğunu biliyoruz:
excel'de ilk karakter nasıl kaldırılır
Gördüğünüz gibi ikinci seviye 3 element içeriyor.
Tam ve tam ikili ağaç arasındaki farkları görüntüler aracılığıyla anlayalım.
- Aşağıda gösterilen ikili ağaç ne tam ne de tam bir ikili ağaçtır. Tam bir ikili ağaç değildir çünkü düğüm 3'ün yalnızca bir çocuğu vardır. Ayrıca düğümlerin sol taraftan doldurulması gerektiğinden tam bir ikili ağaç değildir, ancak düğüm 3'ün sağ çocuğu vardır ve sol çocuğu yoktur.
- Aşağıda gösterilen ikili ağaç tam bir ikili ağaçtır ancak tam bir ikili ağaç değildir. Tam bir ikili ağaçtır çünkü tüm düğümlerin 0 veya 2 çocuğu vardır. Tam bir ikili ağaç değildir çünkü düğüm 3'ün çocuğu yoktur, düğüm 2'nin ise çocukları vardır ve tam bir ikili ağaçta düğümlerin sol taraftan doldurulması gerektiğini biliyoruz.
- Aşağıda gösterilen ikili ağaç tam bir ikili ağaçtır ancak tam bir ikili ağaç değildir. Tüm düğümler dolu bırakıldığı için bu tam bir ikili ağaçtır. Düğüm 2'nin yalnızca bir çocuğu olduğundan tam bir ikili ağaç değildir.
- Aşağıda gösterilen ikili ağaç hem tam hem de tam bir ikili ağaçtır. Tüm düğümler dolu bırakıldığı için bu tam bir ikili ağaçtır. Tüm düğümlerin 0 veya 2 çocuğu olduğundan bu tam bir ikili ağaçtır.
