Hlavní navigace

GLib: Mnohonásobné stromy (2)

Michal Burda 25. 9. 2000

Dnešní díl je zaměřen na rozsáhlé možnosti a způsoby procházení rozvětvenými stromy.

Napříč stromem

void g_node_traverse(GNode *root,
                     GTraverseType order,
                     GTraverseFlags flags,
                     gint max_depth,
                     GNodeTraverseFunc func,
                     gpointer data);

typedef enum
{
  G_IN_ORDER,
  G_PRE_ORDER,
  G_POST_ORDER,
  G_LEVEL_ORDER
} GTraverseType;

typedef enum
{
  G_TRAVERSE_LEAFS     = 1 << 0,
  G_TRAVERSE_NON_LEAFS = 1 << 1,
  G_TRAVERSE_ALL       = G_TRAVERSE_LEAFS | G_TRAVERSE_NON_LEAFS,
  G_TRAVERSE_MASK      = 0x03
} GTraverseFlags;

gboolean(*GNodeTraverseFunc)(GNode *node, gpointer data);

S funkcí „traverse“ jsme se setkali už předminule při binárních stromech. Řekli jsme si, že je to funkce implementující jakési „procházení“ stromem a spouštění určité uživatelské funkce na každý navštívený uzel. Ovšem „traverse“ funkce binárních stromů byl jen slabý odvar toho, co lze dělat s mnohonásobnými stromy.

Zavoláte-li ve svých programech funkci g_node_traver­se(), musíte jí jako první parametr ( root) předat pointer na kořen stromu, který chcete procházet. Pokud uzel root není kořenem stromu, bude se procházet pouze podstrom, jehož kořen je root.

Druhým argumentem ( order) je způsob procházení stromem. Podrobněji jsme si je popsali v předminulém díle. Dnes jen v rychlosti zopakuji:

  • G_PRE_ORDER  – g_tree_traverse() navštíví nejprve uzel a potom jeho následovníky v pořadí od prvního k poslednímu („navštívením uzlu“ se myslí spuštění uživatelské funkce na tento uzel).
  • G_IN_ORDER  – v mnohonásobných stromech ztrácí svůj kouzelný význam, jaký měl u binárních stromů. Způsob procházení však zůstává stejný: nejprve se navštíví první potomek, pak samotný uzel a nakonec ostatní potomci.
  • G_POST_ORDER  – navštíví nejprve následovníky a pak teprve samotný uzel (něco jako procházení „zdola“).
  • G_LEVEL_ORDER  – uživatelskou funkci zavolá na každého potomka uzlu a teprve potom rekurzivně uvedeným způsobem ony potomky zpracovává.

Ukázka mnohonásobného stromu

Obrázek 1 – Ukázka mnohonásobného stro­mu

Poslední způsob si zaslouží trochu více pozornosti. Mějme například strom jako na obrázku 1. Použijete-li na něj G_LEVEL_ORDER procházení, navštíví se uzly v tomto pořadí: nejprve otec, pak syn1, syn2 a syn3. Následuje rekurzivní zpracování synů: syn1 má potomky vnuk1.1, vnuk1.2 a vnuk1.3, na které se v tento moment zavolá uživatelská funkce. Rekurze pokračuje dále na vnuka1.1, ten však už nemá žádné následovníky, proto se nestane nic. Zpracuje se vnuk1.2 a tím se navštíví jeho potomek pravnuk1.2.1 (ten je listem, proto rekurze nemá kam pokračovat). Vnuk1.3 také nemá potomky, takže tady rekurze končí a pokračuje rekurzivní zpracování synů: syn2 je bez následovníků, takže se přeskočí a pozornost se přesune na uzel syn3. Ten má potomka vnuk3.1, na kterého se zavolá uživatelská funkce. Následně se rekurzivně zpracují i jeho potomci pravnuk3.1.1 a pravnuk3.1.2 – dojde i k jejich navštívení. Výsledná posloupnost navštívených uzlů tedy bude: otec, syn1, syn2, syn3, vnuk1.1, vnuk1.2, vnuk1.3, pravnuk1.2.1, vnuk3.1, pravnuk3.1.1 a pravnuk3.1.2.

Třetím parametrem funkce g_node_traverse() jsou příznaky flags. Všechny možnosti, kterých tento argument může nabývat, ukazuje výčtový typ  GTraverseFlags:

  • G_TRAVERSE_LEAFS  – specifikuje, že jedinými „navštívenými“ uzly mohou být pouze listy stromu.
  • G_TRAVERSE_NON_LEAFS  – z navštívených uzlů vylučuje listy. Tedy uživatelská funkce bude zavolána pouze na uzly, které mají nějaké potomky.
  • G_TRAVERSE_ALL  – navštěvovat se budou všechny uzly.
  • G_TRAVERSE_MASK  – tuto volbu používají programátoři knihovny GLib ke zjišťování korektnosti parametru flags. Pro flags, když jsou nastaveny správně, musí totiž platit: (flags <= G_TRAVERSE_MASK). Pokud nebudete vytvářet nějaké další knihovny pracující s příznaky stromů, je vám tento argument k ničemu. :-)

Čtvrtým parametrem ( max_depth) se udává maximální hloubka, do které až má algoritmus jít. Uzly, které budou hlouběji než tato hodnota, už navštíveny nebudou. Jinými slovy, je-li max_depth rovna 1, bude navštíven pouze kořen root. Zadáte-li hloubku 2, bude navštíven kořen a jeho potomci. A tak dále a tak podobně. Je-li max_depth rovna -1, nebude se na hloubku zanoření pohlížet.

Předposlední parametr funkce g_node_traverse() je samotná uživatelská funkce func typu GNodeTraverseFunc. Tato funkce bude zavolána na každý navštívený uzel a jako argumenty dostane node, což je pointer na onen uzel a uživatelská data, což je pointer, který funkce g_node_traverse() získá jako poslední parametr.

Procházení stromem probíhá tak dlouho, dokud uživatelská funkce func vrací FALSE. Jakmile vrátí TRUE (nebo se navštíví všechny uzly), procházení stromem se zastaví.

Pokračování příště.

Našli jste v článku chybu?
Podnikatel.cz: Přehledná titulka, průvodci, responzivita

Přehledná titulka, průvodci, responzivita

Lupa.cz: Co se dá měřit přes Internet věcí

Co se dá měřit přes Internet věcí

Podnikatel.cz: Podnikatelům dorazí varování od BSA

Podnikatelům dorazí varování od BSA

Měšec.cz: Zdravotní a sociální pojištění 2017: Připlatíte

Zdravotní a sociální pojištění 2017: Připlatíte

Root.cz: Pinebook: linuxový notebook za 89 dolarů

Pinebook: linuxový notebook za 89 dolarů

Podnikatel.cz: 1. den EET? Problémy s pokladnami

1. den EET? Problémy s pokladnami

Měšec.cz: Kdy vám stát dá na stěhování 50 000 Kč?

Kdy vám stát dá na stěhování 50 000 Kč?

DigiZone.cz: Flix TV má set-top box s HEVC

Flix TV má set-top box s HEVC

Měšec.cz: Air Bank zruší TOP3 garanci a zdražuje kurzy

Air Bank zruší TOP3 garanci a zdražuje kurzy

Vitalia.cz: Co pomáhá dítěti při zácpě?

Co pomáhá dítěti při zácpě?

Měšec.cz: Jak vymáhat výživné zadarmo?

Jak vymáhat výživné zadarmo?

Podnikatel.cz: Udávání kvůli EET začalo

Udávání kvůli EET začalo

120na80.cz: Pánové, pečujte o svoje přirození a prostatu

Pánové, pečujte o svoje přirození a prostatu

Podnikatel.cz: Zavře krám u #EET Malá pokladna a Teeta?

Zavře krám u #EET Malá pokladna a Teeta?

Vitalia.cz: Jmenuje se Janina a žije bez cukru

Jmenuje se Janina a žije bez cukru

DigiZone.cz: Rádio Šlágr má licenci pro digi vysílání

Rádio Šlágr má licenci pro digi vysílání

Vitalia.cz: Láska na vozíku: Přitažliví jsme pro tzv. pečovatelky

Láska na vozíku: Přitažliví jsme pro tzv. pečovatelky

120na80.cz: Jak oddálit Alzheimera?

Jak oddálit Alzheimera?

Lupa.cz: Insolvenční řízení kvůli cookies? Vítejte v ČR

Insolvenční řízení kvůli cookies? Vítejte v ČR

DigiZone.cz: ČT má dalšího zástupce v EBU

ČT má dalšího zástupce v EBU