Tam İkili Ağaç ve Tam İkili Ağaç
İkili ağaç, her düğümün bir veya iki çocuğu olan bir ağaçtır. İkili bir ağaçta, bir düğümün ikiden fazla çocuğu olamaz. İkili bir ağaçta, çocuklar “sol” ve “sağ” çocuklar olarak adlandırılır. Alt düğümler, üstlerine bir başvuru içerir. Tam bir ikili ağaç, ikili ağacın her seviyesinin son seviye hariç tamamen doldurulduğu bir ikili ağaçtır. Doldurulmamış düzeyde, düğümler en soldaki konumdan başlayarak eklenir. Tam ikili ağaç, ağaçtaki her düğümün, ağacın yaprakları dışında iki çocuğu olan bir ağaçtır.
Tam İkili Ağaç nedir?
Tam ikili ağaç, ağaçtaki her düğümün tam olarak sıfır veya iki çocuğu olduğu bir ikili ağaçtır. Başka bir deyişle, yapraklar hariç ağaçtaki her düğümün tam olarak iki çocuğu vardır. Aşağıdaki Şekil 1, tam bir ikili ağacı göstermektedir. Tam bir ikili ağaçta, düğüm sayısı (n), döngü sayısı (l) ve dahili düğüm sayısı (i) özel bir şekilde ilişkilidir, öyle ki bunlardan herhangi birini biliyorsanız diğer ikisini de belirleyebilirsiniz. değerler aşağıdaki gibidir:
1. Tam bir ikili ağacın i dahili düğümleri varsa:
– Yaprak sayısı l=i+1
– Toplam düğüm sayısı n=2i+1
2. Tam ikili ağaçta n düğüm varsa:
– Dahili düğüm sayısı i=(n-1)/2
– Yaprak sayısı l=(n+1)/2
3. Tam bir ikili ağaçta l yaprakları varsa:
– Toplam Düğüm Sayısı n=2l-1
– Dahili düğüm sayısı i=l-1
Tam İkili Ağaç nedir?
Şekil 2'de gösterildiği gibi, tam bir ikili ağaç, son seviye hariç ağacın her seviyesinin tamamen doldurulduğu bir ikili ağaçtır. Ayrıca son seviyede düğümler en soldan başlayarak eklenmelidir. Yüksekliği h olan tam bir ikili ağaç aşağıdaki koşulları karşılar:
– Kök düğümden, son seviyenin üzerindeki seviye, h-1 yüksekliğinde tam bir ikili ağacı temsil eder
– Son seviyedeki bir veya daha fazla düğüm 0 veya 1 çocuğa sahip olabilir
– Eğer a, b, son seviyenin üzerindeki seviyedeki iki düğüm ise, o zaman ve sadece a, b'nin solunda yer alıyorsa, a'nın b'den daha fazla çocuğu vardır.
Tam İkili Ağaç ile Tam İkili Ağaç arasındaki fark nedir?
Tam ikili ağaçlar ve tam ikili ağaçlar arasında net bir fark vardır. Tam ikili ağaç, her düğümün sıfır veya iki çocuğu olan bir ikili ağaç iken, tam bir ikili ağaç, ikili ağacın son seviye hariç her seviyesinin tamamen doldurulduğu bir ikili ağaçtır. Yığınlar gibi bazı özel veri yapılarının tam ikili ağaç olmaları gerekirken tam ikili ağaç olmaları gerekmez. Tam bir ikili ağaçta, toplam düğüm sayısını veya lav sayısını veya dahili düğüm sayısını biliyorsanız, diğer ikisini çok kolay bulabilirsiniz. Ancak tam bir ikili ağaç, bu üç özniteliği ilişkilendiren özel bir özelliğe sahip değildir.
