Binární pravidelný orientovaný strom

Z hlediska teorie grafů je stromem každý souvislý graf bez kružnic o hranách. Jedná se o hierarchickou strukturu, kde každý má otec 0 až mnoho dětí a každé dítě právě jednoho otce takovým způsobem, že v této struktuře nejsou cykly. Uzel, který je praotcem všech ostatních uzlů nazveme kořenem (z pohledu teorie grafů tím vytvoříme orientovaný strom). Uzel, který nemá žádné potomky nazýváme listem. Být stromem je rekurzívní vlastnost - každý podstrom stromu S je také stromem. Strom je velmi populární pro svoji jednoduchost a použitelnost. Příkladem mohou být vyhledávací stromy nebo haldy.

Vlastnosti stromu

N-arita - Kolik smí mít každý uzel maximálně potomků, z tohoto hlediska patří mezi neoblíbenější binární stromy (každý uzel má 0, 1 nebo 2 potomky).

Hloubka - Hloubkou rozumíme maximální hloubku libovolného uzlu (kořen je v hloubce 0, potomci v hloubce 1, vnuci v hloubce 2...).

Pravidelnost - N-ární strom je pravidelný, pokud má každý uzel 0 nebo N potomků.

Vyváženost - N-ární strom je vyvážený, pokud pro všechny listy platí, že jsou nejsou o nic více hlouběji, než kterýkoliv jiný list. Definice „o nic více hlouběji“ se liší v závislosti na konkrétní implementaci.

Úplná pravidelnost - Úplným N-árním pravidelným stromem hloubky k je strom, jehož každý uzel má 0 nebo N potomků a všechny uzly jsou ve hloubce k.

Průchody binárním stromem

Preorder - zpracuje se napřed kořen, poté levý podstrom a nakonec pravý podstrom.

Inorder - zpracuje se napřed levý podstrom, poté kořen a nakonec pravý podstrom.

Postorder - zpracuje se napřed levý podstrom, poté pravý podstrom a nakonec kořen.

Kód

/**
 * N-arni strom
 * @author Pavel Micka
 */
public class Tree {
    /**
     * Kolekce potomku
     */
    private ArrayList<Tree> children;
    /**
     * Hodnota uchovavana v uzlu
     */
    private Object value;
    /**
     * Prida podstrom jako potomka tohoto korene
     * @param t strom k pridani
     * @param index poradi potomka
     */
    public void addChild(Tree t, int index){
        children.add(index, t);
    }
    /**
     * Odstrani potomka na danem indexu
     * @param index index potomka k odstraneni
     */
    public void removeChild(int index){
        children.remove(index);
    }
    /**
     * Vrati potomka na danem indexu
     * @param index poradi potomka
     * @return potomek na zadanem indexu
     */
    public Tree get(int index){
        return children.get(index);
    }
    /**
     * @return the value
     */
    public Object getValue() {
        return value;
    }
    /**
     * @param value the value to set
     */
    public void setValue(Object value) {
        this.value = value;
    }
}