Předchozí ukázka převodu stromu na text byla typickým příkladem průchodu stromem, při němž začneme kořenem stromu a postupně procházíme v určitém stanoveném pořadí jeho uzly a v každém provedeme nějakou akci. V principu můžeme u binárního stromu definovat tři typy průchodů v závislosti na tom, ve kterém okamžiku stanovenou akci provedeme:
- preorder - akci provedeme před vstupem do levého podstromu,
- inorder - akci provedeme po zpracování levého podstromu, ale ještě před vstupem do pravého podstromu a
- postorder - akci provedeme až po zpracování levého a pravého podstromu.
Kontrolní otázka: Který z těchto průchodů jsme použili při převodu stromu na text?
Volba typu průchodu vždy závisí na konkrétním algoritmu. Pokud nám nezáleží na pořadí, ve kterém se budou uzly stromu zpracovávat, můžeme v podstatě zvolit libovolný typ průchodu - např. pokud bychom chtěli pouze zjistit počet uzlů stromu, určit jeho výšku nebo sečíst hodnoty ve všech uzlech.
 | Příklad 3.14. |
Doplňte do třídy TreeNode metodu, která vrátí počet uzlů ve stromu, jehož kořenem je aktuální uzel.
public int numNodes() {
int nl = _left == null ? 0 : _left.numNodes();
int nr = _right == null ? 0 : _right.numNodes();
return nl + nr + 1;
}
Použili jsme vlastně průchod typu postorder, neboť výpočet pro aktuální uzel se provádí až poté, co jsme zpracovali oba jeho následníky. |
Pokusíme se nejprve realizovat algoritmus, který pouze vytvoří seznam obsahující všechny hodnoty uložené v jednotlivých uzlech jako data. Vytvoříme tedy metodu traverse(), kterou zavoláme vždy na kořenový uzel stromu a které dodáme jako parametr příznak určující jeden ze tří výše uvedených typů průchodů:
public static final int PREORDER = 1;
public static final int INORDER = 2;
public static final int POSTORDER = 3;
public List traverse(int order)
{
List list = new ArrayList();
traverse(list, order);
return list;
}
private void traverse(List list, int order)
{
if( order == PREORDER ) list.add(_data);
if( _left != null ) _left.traverse(list, order);
if( order == INORDER ) list.add(_data);
if( _right != null ) _right.traverse(list, order);
if( order == POSTORDER ) list.add(_data);
}
Pro označení typu průchodu jsme si zavedli konstanty PREORDER, INORDER a POSTORDER. Jak poznáme, že jde o konstanty? V jazyce Java musí být nepříliš názorně označeny atributy static a final. Seznam, do něhož budeme data postupně ukládat, je instancí třídy ArrayList. Můžeme zde využít implementace seznamu z předchozí kapitoly, ale v praxi budeme spíš využívat tříd, které jsou standardní součástí každé instalace prostředí Java. V tom případě ale nezapomeňte na začátek zdrojového textu doplnit příkazy pro dovoz balíku java.util, v němž jsou třídy Iterator, List a ArrayList definovány:
Import java.util.Iterator; import java.util.List; import java.util.ArrayList;nebo jednodušeji příkazem
import java.util.*;jenž ovšem doveze i všechny další třídy z tohoto balíku.
| Příklad 3.15. |
Vypište na standardní výstup seznam všech hodnot v uzlech zadaného stromu v určeném pořadí. Pro výpis použijeme statickou funkci, která obdrží referenci na kořen stromu a údaj o zvoleném pořadí průchodu uzly:
public static void printTree(TreeNode root, int order)
{
List list = root.traverse(order);
Iterator it = list.iterator();
System.out.print("[ ");
while( it.hasNext() ) {
System.out.print(it.next());
System.out.print(" ");
}
System.out.println("]");
}
Nejprve pomocí metody traverse() získáme seznam všech uzlů stromu v určeném pořadí podle parametru order, a potom pomocí iterátoru projdeme získaný seznam a jednotlivé jeho prvky vypíšeme. |
V odstavci věnovaném kolekcím a iterátorem jsme si ukázali použití rozhraní Command pro zpracování všech prvků v seznamu. Podobným způsobem můžeme řešit i procházení stromem. Stačí do třídy TreeNode doplnit následující metodu forAll():
public void forAll(Command command, int order)
{
if( order == PREORDER ) command.execute(_data);
if( _left != null ) _left.forAll(command, order);
if( order == INORDER ) command.execute (_data);
if( _right != null ) _right. forAll(command, order);
if( order == POSTORDER ) command.execute (_data);
}
Použití si opět ukážeme na příkladu.
| Příklad 3.16. |
Realizujte metodu traverse(), která vrátí seznam všech datových položek stromu, s využitím rozhraní Command. Nejprve vytvoříme třídu implementující rozhraní Command, v jejíž instanční proměnné list si budeme během procházení jednotlivými uzly stromu vytvářet seznam datových položek. Metodou getResult() pak tento seznam vrátíme. Třídu TraverseCommand můžeme definovat jako statickou vnitřní třídu třídy TreeNode.
static class TraverseCommand implements Command {
private List list = new ArrayList();
public List getResult() { return list; }
public void execute(Object obj) {
list.add(obj);
}
}
Metoda traverse() třídy TreeNode pak vytvoří instanci třídy TraverseCommand, zavolá metodu forAll() a nakonec získá vytvořený seznam voláním getResult().
public List traverse(int order) {
TraverseCommand cmd = new TraverseCommand();
forAll(cmd, order);
return cmd.getResult();
}
|