Ağaç bilgi modeli

Aile albümündeki soy ağacı, bilgisayardaki klasörler, bir kitabın içindekiler sayfası, bir spor turnuvasının eşleşme tablosu — hepsinin yapısı aynıdır: bir başlangıçtan dallar ayrılır, dallardan yine dallar. Böyle bir yapıya hiyerarşi, onun grafik modeline ise ağaç denir. Ad tesadüf değildir: resim ters çevrilmiş bir ağaca benzer — kökü yukarıda, yaprakları aşağıda.

«Modeller ve modelleme» dersinde ağacı grafik bilgi modelleri arasında gördük, «Tablo bilgi modeli: mantık problemlerinin tabloyla çözümü» dersinde ise tablolarla çalıştık. Tablo nesneleri yan yana dizer; ağaç ise kimin kime bağlı olduğunu ve neyin neyin parçası olduğunu gösterir.

Ağacın öğeleri

• Kök — en üstteki düğüm; ebeveyni yoktur.
• Düğüm — ağacın herhangi bir öğesi; düğümleri birleştiren çizgilere kenar (dal) denir.
• Ebeveyn ve çocuk — bir kenarla doğrudan bağlı üst ve alt düğümler. Çocuk sayısı istenildiği kadar olabilir.
• Yaprak — çocuğu olmayan düğüm; en az bir çocuğu olan düğüm iç düğümdür.
• Seviye — düğümden köke kadar olan kenar sayısı: kök 0. seviyede, çocukları 1. seviyededir vb. En büyük seviye ağacın yüksekliğidir. (Bazı kitaplar kökü 1. seviye sayar — o zaman bütün numaralar bir fazla olur; sorunun koşuluna bak.)

Soy ağaçları ve sınıflandırma ağaçları

Soy ağacı bir kişinin soyunu gösterir: kök ata, her seviye bir kuşaktır (çocuklar, torunlar, torunların çocukları). Dikkat: her çocuğun iki ebeveyni de çizilirse resim artık ağaç olmaz, çünkü bir düğümün iki ebeveyni olur. Ağaç, bir kişinin soyu gösterildiğinde elde edilir.

Sınıflandırma ağacı bir kavramı türlere ayırır: kökte genel kavram, aşağı indikçe daha özel türler bulunur. Ağaç çizilmeden de yazılabilir — iç içe liste olarak: her çocuk ebeveyninden bir adım içeride yazılır. Bir kitabın içindekiler sayfası (1, 1.1, 1.2, 2 …) da böyle bir listedir. Aşağıda yazılımın sınıflandırması iç içe liste olarak verilmiştir.

Yazılım
├── Sistem yazılımı
│   ├── İşletim sistemleri
│   ├── Yardımcı programlar
│   └── Sürücüler
├── Uygulama yazılımı
│   ├── Metin düzenleyiciler
│   ├── Elektronik tablolar
│   ├── Grafik düzenleyiciler
│   ├── Masaüstü yayıncılık sistemleri
│   └── Veri tabanı yönetim sistemleri
└── Programlama araçları

Dosya sistemi ağacı ve dosyanın tam adı

Diskteki dosyalar da ağaç biçiminde yerleşir. Kök, diskin kök klasörüdür (C:\); iç düğümler klasörler, yapraklar ise dosyalar ve boş klasörlerdir. Kökten herhangi bir dosyaya giden yol tektir, çünkü ağaçta her düğümün bir ebeveyni vardır. Bu yola dosyanın yolu, yol ile dosya adının birlikte yazılışına ise dosyanın tam adı denir. Windows’ta klasörler ters eğik çizgi \ ile ayrılır. Dosya ve klasörlerle çalışma için «Yazılım, işletim sistemi ve dosyalar» dersine bak.

Ağaç, döngüsüz bir graftır

Graf dilinde ağaç, bağlantılı ve döngüsüz bir graftır: herhangi iki köşe bir yolla bağlıdır ama kapalı bir halka (döngü) yoktur. Buradan üç yararlı sonuç çıkar: herhangi iki düğüm arasındaki yol tektir; herhangi bir kenar silinirse ağaç iki parçaya ayrılır; yeni bir kenar eklenirse döngü oluşur. Graflar hakkında ayrıntılar bir sonraki derste: «Graf bilgi modeli: komşuluk matrisi ve yol sayısı».

Ağaç parantezlerle de yazılabilir: bir düğümden sonra çocukları parantez içinde, virgülle ayrılarak yazılır. Resimdeki ağaç şöyle yazılır: A(B(E(H, K), F), C, D(G(L, M, N))). Arkasında parantez olmayan harfler yapraklardır.

tree = {
    "A": ["B", "C", "D"],
    "B": ["E", "F"],
    "D": ["G"],
    "E": ["H", "K"],
    "G": ["L", "M", "N"],
}

def show(node, level):
    print("    " * level + node)
    for child in tree.get(node, []):
        show(child, level + 1)

show("A", 0)
nodes = {"A"} | {c for kids in tree.values() for c in kids}
leaves = [n for n in sorted(nodes) if n not in tree]
edges = sum(len(kids) for kids in tree.values())
print("nodes:", len(nodes), "edges:", edges)
print("leaves:", leaves)

A
    B
        E
            H
            K
        F
    C
    D
        G
            L
            M
            N
nodes: 12 edges: 11
leaves: ['C', 'F', 'H', 'K', 'L', 'M', 'N']