Düğüm ve kenar
- Algoritmalar kursu
- Orta seviye
- Ders 26/80
- 4 dk
Düğüm, kenar, yaprak ve derinlik terimlerini öğrenirsin.
Düğüm ve kenar
Ağaçta n düğüm varsa n-1 kenar vardır. Her düğüm (kök hariç) tam bir ebeveyne bağlanır; bu yüzden bir kenar eksik kalır.
Düzey (level): kök 0. düzeydir, çocukları 1. düzey, vb. Derinlik (depth): kökten düğüme kadar olan kenar sayısı.
Yükseklik (height): kökten en derin yaprağa kadar olan kenar sayısı. Boş ağacın yüksekliği -1, tek düğümlü ağacın 0.
Yükseklik hesabı
Ağacın yüksekliği, en uzun kök-yaprak yoludur. Boş ağaç için -1, tek kök için 0.
Recursive tanım: height(node) = -1 eğer node None ise; değilse 1 + max(height(left), height(right)).
Bu, her alt ağacın yüksekliğinden ana ağacın yüksekliğini türetir. O(n) işle çalışır.
Uygulama Ağaç yüksekliği
height(node) yaz. Boşsa -1, değilse 1 + max(sol, sağ). root = Node(1); root.left = Node(2); print(height(root)) ile 1 yazdır.
Başlangıç kodu
def height(node):
# Yükseklik hesaplaÖrnek çözüm
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def height(node):
# Yükseklik hesapla
if node is None:
return -1
return 1 + max(height(node.left), height(node.right))
root = Node(1)
root.left = Node(2)
print(height(root))Beklenen çıktı
1
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Kenar sayısı
n düğüm, ____ kenarn düğüm, n - 1 kenarAçıklama: n - 1 doğru.
2 Düğüm ve kenar: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
Düzey |
Kök 0 |
Derinlik |
Kökten düğüme |
Yükseklik |
En derin yol |
Boş ağaç |
-1 |
3 Tek düğümlü ağacın yüksekliği?
- -1
- 1
- 0 Doğru cevap
- 2
Açıklama: 0