Nyní bychom měli implementovat standardní metodu toString(), kterou třída TreeNode zdědila z bázové třídy Object (ta je společným předkem všech ostatních tříd, a tedy i třídy TreeNode). Metoda toString() by měla převést každý objekt na jeho textovou reprezentaci.

Ale jak můžeme popsat nelineární strukturu stromu jedním lineárním řetězcem? Stačí, když si pomůžeme závorkami a každý uzel zapíšeme jako trojici obsahující uvnitř páru závorek hodnotu datové složky a řetězce reprezentující levý a pravý podstrom. Pokud je některý z následníků prázdný (má hodnotu null), uvedeme místo něj třeba hvězdičku. Tato forma reprezentace se dá zobecnit i na obecné n-ární stromy. Například strom z Obr. 3.9 můžeme popsat řetězcem (1 (2 * *) (3 (5 * *) (6 * *)) (4 (7 * *) *)). Metodu toString() můžeme implementovat výhodně s využitím rekurze:

public String toString() { 
  	return "(" + _data + " " 
  	    +  (_left == null ? "*" : _left.toString()) + " " 
  	    +  (_right == null ? "*" : _right.toString()) + ")"; 
}

U obou referencí na následníky musíme speciálně ošetřit případ, kdy jsou rovny null; volání metody toString() na null by vedlo k chybě. Operátor + v tomto případě představuje spojování (konkatenaci) řetězců typu String. Zamyslíte-li se nad uvedeným výrazem pozorněji, pak zjistíte, že ale proměnná _data není typu String, ale Object. Po nahlédnutí do specifikace jazyka však můžete zjistit, že operátor + je schopen podle potřeby zařídit automatický převod operandů na typ String. Jak to provede? Přece opět voláním metody toString().

Vraťme se však ale k uvedené metodě převodu stromu na text. Takto kompaktně zapsaná metoda toString() není příliš efektivní, neboť pro spojování jednotlivých řetězců se vždy musí vyhradit pomocná vyrovnávací paměť, do níž se oba řetězce za sebe nakopírují, výsledek se převede zpět na řetězec a vyrovnávací paměť se zruší. Mnohem efektivnějšího řešení dosáhneme tím, že vyrovnávací paměť si zřídíme sami jako objekt typu StringBuffer (je součástí základního balíku java.lang), metodou append() do ní budeme připojovat části výsledného řetězce a teprve nakonec obsah paměti převedeme najednou zpět na řetězec:

public String toString() { 
  StringBuffer sb = new StringBuffer(); 
  sb.append("("); 
  sb.append(_data.toString()); 
  sb.append(" "); 
  sb.append( _left == null ? "*" : _left.toString() ); 
  sb.append(" " ); 
  sb.append( _right == null ? "*" : _right.toString() ); 
  sb.append(")"); 
  return sb.toString(); 
}

Tento zápis již není příliš elegantní, ale umožní podstatné zlepšení efektivity celého algoritmu. Vzhledem k tomu, že naším cílem v tomto kurzu je především zvládnutí pokročilejších programátorských technik, nezastavíme se ani u tohoto řešení. Pokuste se nejprve sami v této variantě objevit ještě další zbytečný zdroj časových i prostorových ztrát!

Procházíme-li postupně všemi uzly stromu, pak v každém uzlu vytvoříme a zase zrušíme objekt StringBuffer. Celý převod ale můžeme zvládnout s jedinou vyrovnávací pamětí - stačí ji na začátku vytvořit a pak jen předávat mezi jednotlivými uzly a postupně plnit výsledným textem. K tomu ale budeme potřebovat jednu pomocnou rekurzivní funkci navíc, hlavní metoda toString() pouze vytvoří vyrovnávací paměť, zavolá metodu pro její naplnění textovou reprezentací stromu a nakonec z jejího obsahu vyrobí řetězec, jenž vrátí:

public String toString() { 
  StringBuffer sb = new StringBuffer(); 
  toString(sb); 
  return sb.toString(); 
} 
 
private void toString(StringBuffer sb) { 
  sb.append("("); 
  sb.append(_data.toString()); 
  sb.append(" "); 
  if( _left == null ) 
    sb.append("*"); 
  else 
    _left.toString(sb); 
  sb.append(" "); 
  if( _right == null ) 
    sb.append("*"); 
  else 
    _right.toString(sb); 
  sb.append(")"); 
}