Binární stromy

Vycházejíc z obecné definice stromu a základních pojmů můžeme binární stromy definovat následovně:

Binární strom je prázdný strom anebo vrchol, který má levý a pravý podstrom, které jsou binární stromy.

Model dat, který je binárním stromem můžeme implementovat použitím pole, kterého prvky mají typ klíče prvku. Pozice vrcholů binárního stromu lze očíslovat následujícím způsobem:

Začneme kořenem, kterému přiřadíme 1, dále jeho levému následníku 2, pravému následníku 3, a v číslování pokračujeme na každé úrovni zleva až do jejího konce, kde přejdeme na další úroveň (obr.). Tyto čísla pozic vrcholů jsou pak indexy odpovídajících prvků pole. Obecně platí:

Má-li pozice vrcholu hodnotu indexu i, potom

levý následník má index 2i

pravý následník má index 2i + 1

předchůdce, pokud existuje, má index i/2 (celočíselně).

Poznamenejme, že uvedené vztahy platí, má-li kořen stromu index 1. Pokud by jsme ho umístnili do prvku pole s indexem 0, tyto vztahy nutno upravit.

Pokud se na pozici skutečně nachází vrchol, prvek pole obsahuje klíč. V opačném případě je prvek pole označen jako nepoužit. Například jsou-li hodnoty vrcholů nezáporná celá čísla, může být jeho hodnota -1. Binární strom na obr. , kde ve vrcholech jsou hodnoty klíčů prvků, nemá obsazeny pozice s indexy 5, 8, 10 a všechny další.. Jeho reprezentace polem s klíči prvků by tedy byla

5, 8, 7, 6, -1, 3, 4, -1, 9, -1, ...

Obecně tato implementace není efektivní, protože nejenom musíme vytvořit pole pro předpokládanou maximální velikost stromu, ale navíc musí obsahovat i prvky pro pozice neobsazené vrcholy.

Vrchol binárního stromu můžeme implementovat obdobně jako prvek seznamu, jenomže namísto položky dalsi budou v implementaci vrcholu polozky levy a pravy ukazující na kořen levého a pravého podstromu. Odpovídající třída Vrchol je na obr. . Prázdný strom bude reprezentován hodnotou null.

Průchod stromem

V případě seznamu, když jsme potřebovali projít (navštívit) všechny jeho prvky, například pro jejich vytištění, postupovali jsme od prvního k dalším pomocí ukazatele dalsi. Připomeňme si rekurzivní metody pruchod( ) a pruchodR( ) z článku 4.2, kdy jsme v průchodu pokračovali rekurzivním voláním pruchod(x.dalsi) resp. pruchodR(x.dalsi).

V případě stromu začneme kořenem, ale pro další systematický postup máme tři možnosti

Přímý průchod (preorder)- navštívíme vrchol, potom levý a pravý podstrom

Vnitřní průchod (inorder)- navštívíme levý podstrom, vrchol a pravý podstrom

Zpětný průchod (postorder)- navštívíme levý a pravý podstrom a potom vrchol

Pro strom na obr. potom pro jednotlivé průchody projdeme jeho vrcholy v následujícím pořadí

Přímý průchod: 5, 8, 6, 9, 7, 3, 4

Vnitřní průchod: 6, 9, 8, 5, 3, 7, 4

Zpětný průchod: 9, 6, 8, 3, 4, 7, 5

Průchody binárním stromem vycházejíc z jeho rekurzivní definice můžeme vyjádřit rekurzivní metodou pruchodR( ) na obr..

Uvedená metoda implementuje průchod preorder. Posunutím řádku s tiskem mezi její rekurzivní volání získáme implementaci průchodu inorder a jeho posunutím za obě rekurzivní získáme implementaci průchodu postorder.

Čas průchodu stromem je pro prázdný strom dán vyhodnocením podmínky, tedy

T(0) = c_por

Trvá-li tisk c_tisk a má-li levý podstrom m vrcholů a pravý podstrom n-m-1 vrcholů, potom

T(n) = T(m) + T(n-m-1) + c_por + c_tisk              pro n > 0

Postupem známým z článku 4.2 můžeme ukázat, že její řešení je T(n) = (2c_por + c_tisk)n + c_por a čas průchodu stromem je tedy Θ(n).

Víme již, že rekurzi obecně můžeme odstranit pomocí zásobníku. Použitím abstraktního zásobníku, do kterého můžeme ukládat klíče i stromy, můžeme vytvořit iterační (nerekurzivní) implementace průchodů binárním stromem.

1. Do zásobníku vložíme procházený strom

2. Dokud zásobník není prázdný, v cyklu vybereme prvek ze zásobníku a je-li

    ním klíč vytiskneme ho, jinak do zásobníku vložíme

     pro preorder: pravý podstrom, levý podstrom, klíč vrcholu

     pro inorder: pravý podstrom, klíč vrcholu, levý podstrom

     pro postorder: klíč vrcholu, pravý podstrom, levý podstrom

Prázdné stromy do zásobníku neukládáme.

Pro preorder průchod je při vkládání jako poslední vložen klíč, je tedy vybrán na začátku uvedeného cyklu a vytisknut. Můžeme tedy vytisknout kořen každého stromu, který vybereme ze zásobníku a do zásobníku vložit pravý a levý podstrom. Zásobník tedy bude obsahovat pouze stromy, přesněji reference na jejich kořeny. Iterační preorder průchod je na obr..

Uvedené průchody binárním stromem vycházely z jeho rekurzivní definice. Na druhé straně z pohledu našeho obvyklého procházení textu, tj. shora dolů a zleva doprava, dalším přirozeným průchodem je průchod stromem po úrovních a v rámci nich zleva doprava. Průchod stromem po úrovních dosáhneme záměnou zásobníku v programu na obr. frontou podstromů, které zůstává navštívit (obr.).

Poznamenejme, že jsme ukázali v článku 3.2 zmíněné využití zásobníku a fronty ke konstrukci dalších algoritmů, v našem případě pro procházení binárním stromem.