7. gyakorlat

Bináris fák láncolt ábrázolása

Algo 2-ben fontos lesz!

Fogalmak

Gyökér: A kiinduló pont, nincs szülője

Levél: Nincs gyereke

Node

2 pointeres csúcs: jobb gyerek és bal gyerekre hivatkozik

Node3

3 pointeres csúcs: jobb gyerek, bal gyerek és szülőre hivatkozik

Bináris fák bejárása

Jelölések

Bal gyerek: t \(\to\) left vagy left(t)

Jobb gyerek: t \(\to\) right vagy right(t)

Üres fa: \(t = \Omega\) vagy \(t = 0\) (nincs csúcsa)

Láncolt ábrázolású bináris fák esetén a bejáró algoritmusok paramétere lehetne:

• t:Node* vagy
• t:Node3*

Bejárások

• preorder
• inorder
• postorder
• (szintfolytonos)

Fából kiírás

Kiírásból fa

A felíráshoz az inordert mindenképp tudni kell!

Basically, ha preorder akkor elölről, egyébként hátulról kezded beolvasni.

Leírod a gyökeret, és utána megnézed hogy a pre/postorderben a következő elem az inorderben melyik oldalán van a gyökérnek.

Példa

Preorder: D E M Inorder: M E D

Ekkor kikeresed "D"t az inorderben, leírod, utána a következő elem, "E" tőle balra van, ezért bal gyereke. "M" pedig "E"-től szintén balra van, ezért "M" "E" bal gyereke.

Kifejezés fa

Az 1 vagy 2 operandusú műveletekből álló kifejezést ábrázolhatjuk bináris fával.

Postorder bejárással lengyel formát kapunk