GLib: Mnohonásobné stromy (2)

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á.

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ě.