Ağaçlar: terminoloji, ikili ağaçlar ve gezinmeler

Listeler, yığınlar ve kuyruklar (SEN2211) doğrusal yapılardı: her elemanın en fazla bir “sonraki”si vardı. Ağaç (tree) hiyerarşik bir yapı: bir elemanın birden çok “çocuğu” olabilir. Dosya sistemleri, HTML belgesi, derleyicinin ifade ağaçları, veritabanı indeksleri hep ağaç. Bu dersin sonraki altı haftası (BST, AVL, red-black, heap) bu sayfadaki terimlerin üzerine kurulu.

Sınavda bu haftadan gelenler: terim sorusu (verilen ağaçta derinlik, yükseklik, yaprak sayısı), gezinme izi (preorder, inorder, postorder, level-order), ifade ağacı (postfix’ten kur, değerlendir) ve iki gezinmeden ağaç kur.

Terminoloji

Bu genel ağacı (general tree) örnek alalım:

            A
         /  |  \
        B   C   D
       / \     / \
      E   F   G   H
              |
              I

İki temel gerçek: n düğümlü ağaçta n - 1 kenar vardır (kök hariç her düğümün tek bir ebeveyn kenarı var). Kökten her düğüme tek bir yol vardır.

TUZAK · derinlik ve yükseklik ters yönlerde ölçülür. Derinlik yukarıdan aşağı (kökün derinliği 0), yükseklik aşağıdan yukarı (yaprağın yüksekliği 0). Bazı kaynaklar düğüm sayar, kenar değil. Bu derste ve Weiss’te kenar sayılır; boş ağacın yüksekliği -1.

Genel ağacı saklamak: first-child, next-sibling

Bir düğümün kaç çocuğu olacağı belli değilse her düğüme sabit sayıda referans koyamazsın. Çözüm: her düğümde iki referans tut, ilk çocuk ve sağdaki kardeş.

class TreeNode {
    String element;
    TreeNode firstChild;   // en soldaki çocuk
    TreeNode nextSibling;  // sağındaki kardeş
}

Yukarıdaki ağaçta A.firstChild = B, B.nextSibling = C, C.nextSibling = D, D.firstChild = G. Bu gösterim aslında her genel ağacı bir ikili ağaca çevirir.

Genel ağaçta preorder (önce düğüm, sonra çocuklar soldan sağa) ve postorder (önce çocuklar, sonra düğüm) tanımlıdır:

preorder : A B E F C D G I H
postorder: E F B C I G H D A

Dosya sistemi örneği: dizin listesini girintili basmak preorder, bir dizinin toplam boyutunu hesaplamak postorder (önce alt dizinlerin boyutu lazım).

İkili ağaçlar

İkili ağaçta (binary tree) her düğümün en fazla iki çocuğu var ve çocuklar sol ve sağ diye ayrılır. Sadece sağ çocuğu olan bir düğüm, sadece sol çocuğu olandan farklı bir ağaçtır.

class Node {
    int element;
    Node left, right;
    Node(int e) { element = e; }
}

Özel ikili ağaç türleri

Complete ağaç 7. haftada heap’in şekli olacak. Önemli sayılar:

$\text{yükseklik } h \text{ için en çok } 2^{h+1} - 1 \text{ düğüm}, \qquad n \text{ düğüm için } h \ge \lfloor \log_2 n \rfloor$

En kötü durumda (her düğümün tek çocuğu) yükseklik $n - 1$ olur ve ağaç bağlı listeye döner. Ağaç işlemlerinin süresi yüksekliğe bağlı olduğu için ağacı alçak tutmak sonraki haftaların ana konusu.

Gezinmeler (traversals)

Bu ikili ağaç üzerinde dört gezinmeyi izleyelim:

          A
        /   \
       B     C
      / \     \
     D   E     F
        /     / \
       G     H   I

Kodları üç satır, sadece “ziyaret” satırının yeri değişiyor:

static void preorder(Node n) {
    if (n == null) return;
    visit(n);              // önce
    preorder(n.left);
    preorder(n.right);
}
static void inorder(Node n) {
    if (n == null) return;
    inorder(n.left);
    visit(n);              // ortada
    inorder(n.right);
}
static void postorder(Node n) {
    if (n == null) return;
    postorder(n.left);
    postorder(n.right);
    visit(n);              // sonda
}

Level-order özyinelemeli değil, kuyruk (queue) ile yapılır: kökü kuyruğa koy, her adımda baştan çıkar, ziyaret et, çocuklarını (önce sol) sona ekle.

static void levelOrder(Node root) {
    Queue<Node> q = new ArrayDeque<>();
    if (root != null) q.add(root);
    while (!q.isEmpty()) {
        Node n = q.poll();
        visit(n);
        if (n.left != null) q.add(n.left);
        if (n.right != null) q.add(n.right);
    }
}

Dördü de her düğümü bir kez ziyaret eder: $O(n)$ süre. Özyinelemeli olanlar $O(h)$ yığın belleği, level-order en geniş seviye kadar kuyruk belleği kullanır.

İPUCU · elle gezinme hilesi. Ağacın çevresinde soldan başlayıp saat yönünün tersine dolaşan bir çizgi düşün. Her düğümün soluna değdiğinde yazarsan preorder, altına değdiğinde inorder, sağına değdiğinde postorder çıkar.

İfade ağaçları

İfade ağacında (expression tree) yapraklar işlenen (sayı ya da değişken), iç düğümler operatördür. (3 + 4) * (5 - 2):

          *
        /   \
       +     -
      / \   / \
     3   4 5   2

• postorder → postfix: 3 4 + 5 2 - *
• preorder → prefix: * + 3 4 - 5 2
• inorder + parantez → infix: ((3 + 4) * (5 - 2))
• değer: postorder ile değerlendir: önce iki alt ağaç, sonra operatör → 7 * 3 = 21

Postfix’ten ağaç kurmak

SEN2211’deki postfix değerlendirme algoritmasının aynısı, sayılar yerine düğüm itiyorsun:

1. İşlenen gelirse tek düğümlü ağaç yap, yığına it.
2. Operatör gelirse yığından önce sağ, sonra sol alt ağacı çek, operatör düğümü yap, it.
3. Sonunda yığında tek ağaç kalır.

6 2 / 1 + 4 * için yığının durumu:

6        -> [6]
2        -> [6, 2]
/        -> [(6/2)]
1        -> [(6/2), 1]
+        -> [((6/2)+1)]
4        -> [((6/2)+1), 4]
*        -> [(((6/2)+1)*4)]     değer 16

İki gezinmeden ağaç kurmak

Preorder (ya da postorder) kökü söyler, inorder solu sağdan ayırır. Algoritma:

1. Preorder’ın ilk elemanı kök.
2. Kökü inorder’da bul. Solundakiler sol alt ağaç, sağındakiler sağ alt ağaç.
3. Preorder’da kökten sonraki aynı sayıda eleman sol alt ağacın preorder’ı, kalanı sağın.
4. Her alt ağaç için tekrarla.

Örnek: preorder A B D E C F, inorder D B E A F C.

kök A      inorder: [D B E] A [F C]
sol: pre B D E, in D B E -> kök B, sol D, sağ E
sağ: pre C F,   in F C   -> kök C, sol F

        A
       / \
      B   C
     / \  /
    D  E F
postorder: D E B F C A

Postorder + inorder ile de aynı şey yapılır; bu sefer kök postorder’ın son elemanı.

Sık yapılan hatalar

          K
       /  |  \
      L   M   N
     / \      |
    O   P     Q
            / | \
           S  T  U

        1
       / \
      2   3
     /   / \
    4   5   6
     \     /
      7   8

        1
       / \
      2   3
     /   / \
    4   5   6
     \     /
      7   8

static int countLeaves(Node n) {
    if (n == null) return 0;
    if (n.left == null && n.right == null) return 1;
    return countLeaves(n.left) + countLeaves(n.right);
}

static int height(Node n) {
    if (n == null) return -1;
    return 1 + Math.max(height(n.left), height(n.right));
}