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