Düğüm ve kenar

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.

Örnek çözümü göster

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))

Kendini test et

Kenar sayısı

n düğüm, ____ kenar

Cevabı göster

n düğüm, n - 1 kenar

Düğüm ve kenar: kavramları eşleştir

Düzey

Kök 0
Derinlik

Kökten düğüme
Yükseklik

En derin yol
Boş ağaç

-1
Tek düğümlü ağacın yüksekliği?
- -1
- 1
- 0
- 2
Cevabı göster

0 — 0

Sıradaki ders: İkili ağaç

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler