varrott fák
A bináris fa, amely N csomópontok, minden csomópont a gyökér kivételével meghatározza pontosan egy kapcsolatot. Összesen linkek 2 * N; nem üres - N-1. így, az N + 1 Link üres. Üres kötvények már csak annak jelzésére, hogy tovább ebbe az irányba nincs mód, melyek esetében csak egy kicsit. Felmerül a kérdés: lehet-e használni a helyet foglalja el az üres kapcsolatok hatékonyabban. Tűzött fák használni a helyet foglalja el az üres kapcsolatok tárolására mutatókat egyszerűsítése elhaladó fa. Ezek a további kommunikációs nevezett szálak. ahonnan a kifejezés varrt. Bemutatjuk a jelölés:
- * P - elődje a csomópont P fordított sorrendben,
- P * - P követőelem összeszerelés fordított sorrendben,
- + P - egy prekurzor közvetlen sorrendben,
- P + - utódja közvetlen módon.
A fa is varrt, hogy megkerülje az egyik megrendeléseket. Összehasonlítható a hagyományos fa és a fa, varrott feltérképezni hátra. Ahelyett, hogy üres bal linkek tárolja egy mutatót az elődje fordított sorrendben helyett üres jobb kapcsolatok - egy mutatót a követője. Ezek a kapcsolatok az úgynevezett „szálakat” ellentétben az alapvető kapcsolatokat, amelyek megegyeznek a normál fa. Annak érdekében, hogy megkülönböztessük az alapvető kommunikációs fonalak minden csomópont kezeli két mezőt L és R, amely értékek fognak téma. ha a kapcsolat - szál és MAINLINK. ha a kapcsolat - alap (cérna és MainLink - állandó). Így, a csomópont faszerkezetben tűnemezelt jelentése:
25. ábra tűzött a fán. A szaggatott vonal mutatja a menet.
25. ábra. varrott fa
Az előnye, hogy a varrott fák, hogy az egyszerűsített bejárási algoritmusok. Az alábbiakban egy olyan funkció, hogy visszaad egy pointert p követő fordított sorrendben.
ha (p-> R == menet) visszatérési q; //, ha ez a téma, akkor q-eredmény
// egyébként lemenni egészen a bal Relations
Jelenlétében az algoritmus meghatározására követője nem kell verem (vagy kifejezetten generáló mechanizmus végrehajtása rekurzió). Által elvégzett feladatok megkerülve a fa fejjel lefelé formájában:
void InverseBypass (NODE * Root)
// megtalálja az első fordított egység
// ez a végén a süllyedés a fő bal Relations
// végig az összes csomópontot használva NextUzel funkció