---
marp: true
theme: kurzus
paginate: true
footer: Adatszerkezetek · 14. hét · Fák, bináris fák, bejárások
---

<!-- _class: cim -->
<!-- _paginate: false -->
<!-- _footer: "" -->

# Adatszerkezetek

## 14. hét – Fák: fogalmak, bináris fák, ábrázolás, bejárások

Dr. Koczka Ferenc · Eszterházy Károly Egyetem · 2026

---

## Ismétlés

- Eddig **lineáris** adatszerkezetek: tömb, lista, verem, sor – minden elemnek legfeljebb **egy** rákövetkezője van
- **Rekurzió** (12. hét): a feladat visszavezetése kisebb példányokra
- **Verem** és **sor**: a bejárások segédeszközei

### A mai óra kérdései

- Hogyan tárolunk **hierarchikus** adatokat?
- Mi a bináris fa, és hogyan ábrázolható a memóriában?
- Hogyan járjuk be egy fa összes csomópontját?

<!--
Időterv: fogalmak 20' · bináris fa, típusok 15' · ábrázolás 20' · bejárások 25' · rekurzív műveletek 10'
A régi kurzus 8. és 11. hetének anyaga; a régi dolgozat tömbös fa-ábrázolási feladata ide tartozik.
-->

---

## Hierarchikus adatok

Sok adat természetes módon **fa szerkezetű**:

- **Fájlrendszer:** mappák, almappák, fájlok
- **Szervezeti ábra:** egyetem → kar → intézet → tanszék
- **Családfa**
- **Weboldal** (HTML DOM): `<html>` → `<body>` → `<div>` → …
- **Kifejezések:** `(3 + 4) * (5 − 2)`
- **Döntések:** sakkprogram lépésfája, döntési fa a gépi tanulásban

<div class="doboz">

A fa **hierarchikus** adatszerkezet: minden elemnek **legfeljebb egy előzője** (szülője), de **több rákövetkezője** (gyereke) lehet (1. hét: osztályozás).

</div>

---

## Fogalmak

![w:1000](kepek/h14_fogalmak.svg)

---

## Fogalmak – összefoglalva

| Fogalom | Jelentés |
|---|---|
| **csomópont** (node), **él** (edge) | az elemek, és a szülő–gyerek kapcsolatok |
| **gyökér** (root) | az egyetlen csomópont, amelynek nincs szülője |
| **levél** (leaf) | gyerek nélküli csomópont |
| **szülő, gyerek, testvér** | közvetlen kapcsolat · azonos szülő gyerekei |
| **ős, leszármazott** | a gyökér felé, illetve lefelé vezető úton lévők |
| **részfa** | egy csomópont és az összes leszármazottja |
| **mélység / szint** | a gyökértől vezető út hossza (a gyökéré 0) |
| **magasság** | a leghosszabb gyökér–levél út hossza |
| **fokszám** | a gyerekek száma · **erdő:** fák halmaza |

**Rekurzív definíció:** a fa vagy **üres**, vagy egy **gyökérből** és annak **részfáiból** áll.

---

<!-- _class: fejezet -->

# Bináris fák

---

## Bináris fa

**Bináris fa:** minden csomópontnak **legfeljebb két** gyereke van: **bal** és **jobb** gyerek.

![w:1000](kepek/h14_tipusok.svg)

---

## A bináris fa tulajdonságai

- Az *i*-edik szinten legfeljebb **2ⁱ** csomópont van
- Egy *h* magasságú bináris fában legfeljebb **2ʰ⁺¹ − 1** csomópont van (tökéletes fa)
- Egy *n* csomópontú bináris fa magassága legalább **⌊log₂ n⌋**, legfeljebb **n − 1** (degenerált)

| Tulajdonság | Bináris fa |
|---|---|
| Elemek | homogén |
| Kapcsolat | **hierarchikus** |
| Méret | dinamikus |
| Tárolás | szétszórt (láncolt) vagy folytonos (tömb) |
| Elérés | **szekvenciális** (a gyökértől indulva, mutatókon át) |

<div class="doboz tipp">

A magasság a fa műveleteinek **lépésszámát** határozza meg – ezért fontos, hogy a fa **kiegyensúlyozott** legyen (15. hét).

</div>

---

<!-- _class: fejezet -->

# A bináris fa ábrázolása

---

<!-- _class: kicsi -->

## Láncolt ábrázolás

![w:760](kepek/h14_lancolt.svg)

<div class="ket-hasab">
<div>

<span class="cimke java">Java</span>

```java
class Node {
    char value;
    Node left, right;
}
Node root;   // null: üres fa
```

</div>
<div>

<span class="cimke go">Go</span>

```go
type Node struct {
    Value       rune
    Left, Right *Node
}
```

</div>
</div>

Pszeudokód: `Elem[P].Érték`, `Elem[P].Bal`, `Elem[P].Jobb`, a gyökérre a **Gyökér** mutató mutat.

---

## Tömbös (folytonos) ábrázolás

![w:1000](kepek/h14_tombos.svg)

- Mutatók nélkül: a gyerekek és a szülő **indexe kiszámítható**
- **Teljes** fánál tökéletes (nincs üres hely) – ezt használja a **kupac** (15. hét)
- Degenerált fánál rengeteg üres hely: *h* magasságú lánchoz 2ʰ⁺¹ − 1 elemű tömb kell!

---

## Általános fa ábrázolása bináris fával

Ha egy csomópontnak **tetszőleges** számú gyereke lehet: **bal gyerek – jobb testvér** ábrázolás

- **Bal** mutató → az **első gyerek**
- **Jobb** mutató → a **következő testvér**

<div class="ket-hasab">
<div>

```text
        A
      / | \
     B  C  D
    / \     \
   E   F     G
```

</div>
<div>

```text
   A
  /
 B ———— C ———— D
 |             |
 E ——— F       G
```

</div>
</div>

Így minden általános fa (és erdő) **bináris fával** tárolható – például egy fájlrendszer mappaszerkezete.

---

<!-- _class: fejezet -->

# Bejárások

---

## A fa bejárása

**Bejárás:** minden csomópont **pontosan egyszeri** feldolgozása, meghatározott sorrendben.

![w:1000](kepek/h14_bejaras.svg)

---

<!-- _class: kicsi tomor -->

## Mélységi bejárások – rekurzívan

<div class="ket-hasab">
<div>

<span class="cimke pszeudo">Pszeudokód</span>

```text
Eljárás Preorder(P)
  Ha P ≠ Nil akkor
    Feldolgoz(Elem[P].Érték)
    Preorder(Elem[P].Bal)
    Preorder(Elem[P].Jobb)
  Elágazás vége
Eljárás vége

Eljárás Inorder(P)
  Ha P ≠ Nil akkor
    Inorder(Elem[P].Bal)
    Feldolgoz(Elem[P].Érték)
    Inorder(Elem[P].Jobb)
  Elágazás vége
Eljárás vége

Eljárás Postorder(P)
  Ha P ≠ Nil akkor
    Postorder(Elem[P].Bal)
    Postorder(Elem[P].Jobb)
    Feldolgoz(Elem[P].Érték)
  Elágazás vége
Eljárás vége
```

</div>
<div>

<span class="cimke java">Java</span>

```java
static void inorder(Node p) {
    if (p == null) return;
    inorder(p.left);
    System.out.print(p.value + " ");
    inorder(p.right);
}
```

<span class="cimke go">Go</span>

```go
func inorder(p *Node) {
    if p == nil {
        return
    }
    inorder(p.Left)
    fmt.Printf("%c ", p.Value)
    inorder(p.Right)
}
```

A három bejárás **csak abban különbözik**, hogy a gyökeret **mikor** dolgozzuk fel. Lépésszám: **O(n)**, tárigény: O(h).

</div>
</div>

---

## Szintenkénti (szélességi) bejárás

A gyökértől indulva **szintenként**, balról jobbra – **sorral** (8. hét):

```text
Eljárás SzintenkéntBejár(Gyökér)
  Ha Gyökér = Nil akkor kilépés
  Sorba(Gyökér)
  Ciklus amíg nem Üres
    P ← Sorból
    Feldolgoz(Elem[P].Érték)
    Ha Elem[P].Bal ≠ Nil akkor Sorba(Elem[P].Bal)
    Ha Elem[P].Jobb ≠ Nil akkor Sorba(Elem[P].Jobb)
  Ciklus vége
Eljárás vége
```

Példa: **F B G A D I C E H** · Ha a sort **veremre** cseréljük (és előbb a jobb gyereket tesszük be), **preorder** bejárást kapunk!

---

## Alkalmazás: kifejezésfa

![w:1000](kepek/h14_kifejezesfa.svg)

- A belső csomópontok **operátorok**, a levelek **operandusok**
- A **postorder** bejárás éppen a **postfix** alakot adja – a fa veremmel építhető fel a postfix alakból
- **Kiértékelés:** `Érték(P) = Érték(bal) op Érték(jobb)` – rekurzívan

---

<!-- _class: kicsi -->

## Rekurzív műveletek fákon

Minta: **„kezeld a gyökeret, és hívd meg önmagad a két részfára”**

<div class="ket-hasab">
<div>

```text
Függvény Elemszám(P)
  Ha P = Nil akkor Vissza: 0
  Vissza: 1 + Elemszám(Elem[P].Bal)
            + Elemszám(Elem[P].Jobb)
Függvény vége

Függvény Magasság(P)
  Ha P = Nil akkor Vissza: −1
  Vissza: 1 + max(Magasság(Elem[P].Bal),
                  Magasság(Elem[P].Jobb))
Függvény vége
```

</div>
<div>

```text
Függvény Levelek(P)
  Ha P = Nil akkor Vissza: 0
  Ha Elem[P].Bal = Nil és Elem[P].Jobb = Nil
    akkor Vissza: 1
  Vissza: Levelek(Elem[P].Bal)
        + Levelek(Elem[P].Jobb)
Függvény vége
```

További példák: összeg, maximum, keresés (O(n)), tükrözés, másolás, két fa összehasonlítása

</div>
</div>

<span class="halvany">A példafára: elemszám 9, levelek 4 (A, C, E, H), magasság 3.</span>

---

## Összefoglalás

- **Fa:** hierarchikus adatszerkezet; gyökér, levél, szülő, gyerek, részfa, mélység, magasság
- **Bináris fa:** legfeljebb két gyerek; szigorú, teljes, tökéletes, degenerált
- **Láncolt ábrázolás:** Bal és Jobb mutató · **tömbös:** gyerekek 2i és 2i + 1, szülő i div 2
- **Bejárások:** preorder (G-B-J), inorder (B-G-J), postorder (B-J-G) – rekurzívan, O(n); szintenként – sorral
- A fákon a műveletek **természetes módon rekurzívak**

**Következő hét:** bináris keresőfa – keresés, beszúrás, törlés; kiegyensúlyozottság; kupac.

---

## Ellenőrző kérdések

1. Igaz vagy hamis: a bináris fa hierarchikus adatszerkezet.
2. Add meg a bejárási sorrendeket: gyökér 1; 1 bal gyereke 2, jobb gyereke 3; 2 gyerekei 4 és 5; 3 jobb gyereke 6.
3. A bináris fa elemeit egy A tömbben tároljuk (A[1] a gyökér, az *i*-edik elem gyerekei A[2i] és A[2i + 1]). A = [K, F, R, B, H, –, T]. Rajzold le a fát, és add meg az inorder bejárást!
4. Hány csomópontja lehet legfeljebb egy 4 magasságú bináris fának?
5. Melyik bejárás adja egy kifejezésfából a postfix alakot?
6. Mi lesz `Magasság(P)` értéke egyetlen csomópontból álló fára?

<!--
Megoldás: 1. I
2. preorder: 1 2 4 5 3 6 · inorder: 4 2 5 1 3 6 · postorder: 4 5 2 6 3 1 · szintenként: 1 2 3 4 5 6
3. K gyökér; F (bal), R (jobb); F gyerekei B, H; R jobb gyereke T. Inorder: B F H K R T
4. 2^5 − 1 = 31   5. postorder   6. 0
-->

---

<!-- _class: fejezet -->
<!-- _footer: "" -->

# Gyakorlat

---

<!-- _class: gyak -->

## Bemutató programok

| Program | Java | Go | Mit mutat? |
|---|---|---|---|
| Bináris fa | `BinaryTree.java` | `h14/binarytree` | négyféle bejárás, elemszám, levelek, magasság, oldalra döntött kiírás |
| Tömbös fa | `ArrayTree.java` | `h14/arraytree` | indexképletek, bejárás indexekkel |
| Kifejezésfa | `ExpressionTree.java` | `h14/expressiontree` | felépítés postfixből, kiértékelés, infix/prefix |
| Bejárás veremmel | `IterativeTraversal.java` | `h14/iterative` | preorder és inorder rekurzió nélkül |

---

<!-- _class: gyak -->

## Feladatok

1. **Összeg és maximum:** számítsd ki egy egész számokat tároló bináris fa elemeinek összegét és legnagyobb elemét!
2. **Egygyerekes csomópontok:** hány csomópontnak van pontosan egy gyereke?
3. **Szigorú fa:** döntsd el, hogy minden csomópontnak 0 vagy 2 gyereke van-e!
4. **k-adik szint:** írd ki a *k*-adik szinten lévő elemeket!
5. **Utak:** írd ki az összes gyökér–levél utat!
6. **Azonos fák:** döntsd el, hogy két bináris fa szerkezetre és értékekre is azonos-e!

Megoldások: `Exercises14.java`, `h14/exercises`

---

<!-- _class: gyak -->

## Házi feladat

1. Írj függvényt, amely egy láncolt ábrázolású bináris fát **tömbös** ábrázolásúvá alakít (és fordítva)! Mekkora tömb kell?
2. Építsd fel a bináris fát a **preorder** és az **inorder** bejárásából! (Pl. preorder: F B A D C E G I H, inorder: A B C D E F G H I)
3. Írd ki a fát **szintenként, soronként** (minden szint új sorba kerüljön)!
4. Írj programot, amely egy mappa tartalmát **fa** formában írja ki (mint a `tree` parancs)! (Java: `File.listFiles()`, Go: `os.ReadDir`)

<!--
Megoldás-vázlat:
1. Tömbméret: 2^(h+1) − 1 (h a magasság); a gyökér az 1-es indexre, a bal gyerek 2i, a jobb 2i+1 – rekurzív bejárással.
2. A preorder első eleme a gyökér; az inorderben ettől balra a bal részfa, jobbra a jobb részfa elemei; rekurzívan.
3. Szélességi bejárás, a sor méretét minden szint elején megjegyezzük, annyi elemet veszünk ki.
4. Rekurzív bejárás, a mélységnek megfelelő behúzással (preorder).
-->