tree traversal

tree traversal (tsz. tree traversals)

1. (informatika, mesterséges intelligencia) fabejárás

Egy bináris vagy általános fán a bejárás (traversal) során valamennyi csomópontot sorra felkeresünk és valamilyen műveletet végzünk az adatokon. A bejárási algoritmusoknak több típusa van, amelyek különféle sorrendet biztosítanak. Három alapvető, rekurzív bináris­fa-bejárási stratégia létezik:

Minta:

Preorder(node):
    if node == nullptr: return
    visit(node)
    Preorder(node->left)
    Preorder(node->right)

1. Látogatjuk (feldolgozzuk) a gyökeret
2. Rekurzívan bejárjuk a bal al­fát
3. Rekurzívan bejárjuk a jobb al­fát

Tulajdonságok:

• Először látjuk a gyökért.
• Hasznos, ha először akarjuk kiírni vagy másolni a fa szerkezetét (például klónozáskor).

C++ példa:

void preorder(Node* node) {
    if (!node) return;
    std::cout << node->value << " ";
    preorder(node->left);
    preorder(node->right);
}

Minta:

Inorder(node):
    if node == nullptr: return
    Inorder(node->left)
    visit(node)
    Inorder(node->right)

1. Rekurzívan bejárjuk a bal al­fát
2. Látogatjuk a gyökeret
3. Rekurzívan bejárjuk a jobb al­fát

Tulajdonságok:

• Bináris keresőfán (BST) alkalmazva a csomópontok növekvő sorrendben kerülnek feldolgozásra.
• Ezért az inorder az egyik legegyszerűbb módja a fában tárolt elemek sorba rendezett kinyerésének.

C++ példa:

void inorder(Node* node) {
    if (!node) return;
    inorder(node->left);
    std::cout << node->value << " ";
    inorder(node->right);
}

Minta:

Postorder(node):
    if node == nullptr: return
    Postorder(node->left)
    Postorder(node->right)
    visit(node)

1. Rekurzívan bejárjuk a bal al­fát
2. Rekurzívan bejárjuk a jobb al­fát
3. Látogatjuk a gyökeret

Tulajdonságok:

• A csomópontot csak miután annak gyerekeit már feldolgoztuk.
• Hasznos lebontó műveletekhez: például fákat felszabadító (delete) algoritmusában, mert előbb a gyermekek törlődnek, aztán a gyökér.

C++ példa:

void postorder(Node* node) {
    if (!node) return;
    postorder(node->left);
    postorder(node->right);
    std::cout << node->value << " ";
}

Ez nem rekurzív, hanem szélességi keresés (Breadth-First Search, BFS) alkalmazása:

1. Egy sor (queue) adatszerkezetben tartjuk a még be nem járt csomópontokat.
2. Kezdjük a gyökérnél: betesszük a sortürelébe.
3. A sorból kiveszünk egy csomópontot, feldolgozzuk, majd sorba tesszük az ő gyermekeit (bal, majd jobb).
4. Amíg a sor nem üres, ismételjük.

#include <queue>
void levelOrder(Node* root) {
    if (!root) return;
    std::queue<Node*> q;
    q.push(root);
    while (!q.empty()) {
        Node* u = q.front(); q.pop();
        std::cout << u->value << " ";
        if (u->left)  q.push(u->left);
        if (u->right) q.push(u->right);
    }
}

Tulajdonságok:

• Szintenkénti sorrendben látogatja a csomópontokat.
• Hasznos, ha a gyökér-közeli elemeket előbb kell feldolgozni (pl. gráfokban a legrövidebb út keresésénél).

A fenti {pre,in,post}order mind rekurzív definíció. Iteratív megoldást is adhatunk verem használatával:

• Preorder:
  1. Verembe betesszük a gyökért.
  2. Amíg a verem nem üres: pop, látogat, majd először jobb, aztán bal gyereket tolunk a verembe.
• Inorder:
  1. Csomóponttól balra lemegyünk, toljuk a verembe, amíg bal gyerek van.
  2. Verem tetejét pop, látogat, ezután jobbra lépünk, onnan megint balra le…
• Postorder: Bonyolultabb veremes módszerek vagy két verem használata, vagy jelölők alkalmazása, mert a gyerekek feldolgozása előbb kell történjen.

• Idő: mind a négy fő módszer ${\textstyle O(n)}$, ahol ${\textstyle n}$ a csomópontok száma, mert minden csomópontot pontosan egyszer dolgozunk fel.
• Tér: rekurzív megoldásnak a rekurziós verem mélysége a fa magasságával arányos ${\textstyle O(h)}$. BSF‐nek van egy teljes szinttároló sorigénye ${\textstyle O(\max \_{\text{szint}}\#)}$.

Egy aritmetikai kifejezés bináris fává alakítható, ahol a belső csomópontok operátorok, levelek operandusok.

• Preorder ⇒ prefix (pl. + * A B C)
• Inorder ⇒ infix (pl. A * B + C)
• Postorder ⇒ postfix (pl. A B * C +)

Postfix formából veremmel gyorsan értékelhető a kifejezés, prefixből pedig rekurzív kiértékelés indul.

Összefoglalva, a fa bejárása a faalkalmazások alapképessége:

• pre/in/post: DFS‐szerű, rekurzívan egyszerű, konkrét sorrendek
• level: BFS‐szerű, sorral, szintek feldolgozása

Ezeket a mintákat mindenfa‐ vagy gráf‐algoritmus építi, és elengedhetetlenek a hatékony adatstruktúra‐kezeléshez.

• tree traversal - Szótár.net (en-hu)
• tree traversal - Sztaki (en-hu)
• tree traversal - Merriam–Webster
• tree traversal - Cambridge
• tree traversal - WordNet
• tree traversal - Яндекс (en-ru)
• tree traversal - Google (en-hu)
• tree traversal - Wikidata
• tree traversal - Wikipédia (angol)