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_traverse()
, 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 stromu
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 parametruflags
. Proflags
, 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ě.