İkili ağaç
- Algoritmalar kursu
- Orta seviye
- Ders 27/80
- 4 dk
Her düğümün en fazla iki çocuklu olduğu ikili ağacı öğrenirsin.
İkili ağaç
İkili ağaçta her düğüm en fazla iki çocuğa sahiptir: left ve right. Tam ikili ağaçta her düzey tamamen doludur.
Düğüm sayısı count(node): None ise 0, değilse 1 + count(left) + count(right). Bu, tüm ağacı dolaşır.
Soldan sağa dolaşım (inorder): sol → kök → sağ. SıralıBST için artan sıra verir.
Dolaşım türleri
Üç temel dolaşım türü vardır: inorder (sol-kök-sağ), preorder (kök-sol-sağ), postorder (sol-sağ-kök). Her biri farklı bir sıra üretir.
Inorder, BST'lerde sıralı çıktı verir. Preorder, ağacı kopyalamak için kullanılır. Postorder, çocukları önce işler ve silme için idealdir.
Hepsi O(n) çalışır ve recursion ile doğal biçimde yazılır; kod kısa ve okunaklıdır.
Uygulama Düğüm say
count(node) yaz. None ise 0, değilse 1 + sol + sağ. root = Node(1); root.left = Node(2); root.right = Node(3); print(count(root)) ile 3 yazdır.
Başlangıç kodu
def count(node):
# Düğüm sayÖrnek çözüm
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def count(node):
# Düğüm say
if node is None:
return 0
return 1 + count(node.left) + count(node.right)
root = Node(1)
root.left = Node(2)
root.right = Node(3)
print(count(root))Beklenen çıktı
3
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 İkili ağaç: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
İkili ağaç |
En fazla 2 çocuk |
Tam |
Her düzey dolu |
Inorder |
Sol-kök-sağ |
Count |
1+sol+sağ |
2 Inorder dolaşım sırası nedir?
- Kök-sol-sağ
- Sağ-kök-sol
- Sol-sağ-kök
- Sol-kök-sağ Doğru cevap
Açıklama: Sol-kök-sağ
3 Düğüm sayımı
return 1 + count(node.left) + count(node.____)return 1 + count(node.left) + count(node.right)Açıklama: right doğru.