Bináris fa tárolása?

"Biráris fa adatait szeretném eltárolni a lehető leggazdaságosabban"

Csinálsz egy bináris fát, nem sok opció van benne...

Hol akadtál el? Vagy mi a kérdés?

Olvasd át ezt az anyagot, szerintem választ ad a kérdésedre:

[link]

Eltárolod az inorder és a preoder listáját a fának.

Visszafejtés: végigmész a preorder listán, megkeresed ezt az elemet az inorderben. Ilyenkor bal és jobb részre oszlik az inorder lista. A bal oldali elemek a preorderből kiválasztott csúcs bal, a jobb oldaliak a jobb oldalon fognak elhelyezkedni. Veszed a preoder következő elemét, szintén megkeresed az inroder listában, de a lista itt már csak az a szakasz, amelyikbe beleesett az előző keresés eredményeként. Ezt addig folytatod, amíg megkapod a triviális esetet: az inorderben megkapott elem a 3 elemű szakasz középső eleme (aminek a két oldala a két gyereke). Így rekurzívan, alulról építed a fát.

A csúszok száma * 2 byte az nagyon sok? Ha nem, akkor csak szépen mentsd le sorban a csomópontokat és a részfákat. A csomópontonkénti +1 byteban pedig megadhatod, hogy melyik részfa létezik, ez igazából csak 2 bit, szóval csomóponton * 10 bit is elég az egyszerű sorosításhoz, de ekkor bitekkel kell "bűvészkedni".

Szóval mennyire gazdaságos tárolás kell? Lehet tudni valamit a fáról? Pl teljes bináris fa? Mert ekkor elég csomópont * 1 byte is.

Tényleg ennyire gond a csomópont * 2 byte, amivel egy faék egyszerű mentést és visszaálltást lehet csinálni?

A #3-as valamit rohadtul túlkomplikál.

Simán a preorder bejárást ments le kiegészítve azzal, hogy van-e bal/jobb oldali érték. Nyilván ha a tárolandó érték nem vehet fel valamilyen értéket, pl 0-t vagy 255-őt, akkor ez jelentheti azt, hogy az adott oldali gyerek nem létezik. Ha nincs ilyen nem használt érték, akkor erre kell egy plusz 2 bit csúcsonként.

Szöveges állományban akarod tárolni? Mert akkor én is azt javaslom, mint az 5-ös, preorder lista placeholderekkel.

Pl. ha 5 a root, nincs bal gyerek és 3 a jobb, akkor mondjuk "5,-,3"-ként tárolod.

#9: Ez működik bináris fájlban is úgy, ha van egy olyan érték amit használhatsz annak a jelzésére, hogy az adott érték nem létezik... mint fentebb írtam.

Ekkor ezek a byteok lesznek: 5,255,3

Visztont így csúcsok száma + (levelek száma *2) byte kell, ahol a levelek száma ideális esetben csúcsok száma +1.. tehát gyakorlatilag ez is 2*csúcsok száma byteot foglal, szóval ha ennyire számít, akkor a #4-es 10bit/csúcs megoldása jobb, bár nehézkesebb beolvasni.

Arra a kérdésre a válasz, hogy hogy olvasod be, pszeudókóddal:

treenode read_tree()

{

  gyoker = new treenode;

  gyoker.value = stream.read8;

  flag_left = stream.readbit;

  flag_right = stream.readbit;

  if (flag_left) gyoker.left = read_tree;

  if (flag_right) gyoker.right = read_tree;

  return gyoker;

}

Bár ez utóbbiban nem értem mi okoz nehézséget, pofonegyszerű kód attól eltekintve, hgoy biteket kell olvasni a streamből és így az adat byteok sem pont egész byteoknál lesznek mindig.