Lab05 - Binární strom

Implementujte dodané interface Tree a Node třídami TreeImpl a NodeImpl. Třída TreeImpl musí obsahovat defaultní konstruktor (bez parametrů). Metody a proměnné pojmenovávejte anglicky. Nepoužívejte javovské kolekce; potřebujete pouze pole, které dostanete jako parametr setTree.

Tree reprezentuje binární strom, který ve všech uzlech obsahuje celočíselná data. Každý uzel stromu je reprezentován třídou implementující interface Node. Tree obsahuje následující metody:

• void setTree(int[] values)
  • nastaví strom, tak aby obsahoval hodnoty z pole values
  • pokud je délka pole lichá, kořen obsahuje prostřední číslo, jinak obsahuje první číslo za polovinou posloupnosti
  • levá část podstromu pak obsahuje prvky pole před tím prostředním prvkem a pravé prvky za ním
  • obdobně to platí i pro podstromy
• Node getRoot()
  • vrátí kořen stromu
• String toString()
  • vrátí řetězcovou reprezentaci stromu vhodnou k výpisu v následujícím formátu
    • každá hodnota je na jednom řádku, předchází ji počet mezer odpovídající hloubce uzlu (0 pro kořen) a '- '
    • na prvním řádku je hodnota kořenu
    • hodnotu uzlu následuje výpis levého podstromu a pak pravého podstromu
    • každý řádek (vč. posledního) je ukončen novým řádkem ('\n')
  • Příklad pro strom vytvořený pro pole [1, 2, 3, 4, 5, 6, 7]:

- 4
 - 2
  - 1
  - 3
 - 6
  - 5
  - 7

Ukázka výstupu metody toString pro stromy vytvořené z posloupností [1], [1, 2], … , [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

- 1

- 2
 - 1

- 2
 - 1
 - 3

- 3
 - 2
  - 1
 - 4

- 3
 - 2
  - 1
 - 5
  - 4

- 4
 - 2
  - 1
  - 3
 - 6
  - 5

- 4
 - 2
  - 1
  - 3
 - 6
  - 5
  - 7

- 5
 - 3
  - 2
   - 1
  - 4
 - 7
  - 6
  - 8

- 5
 - 3
  - 2
   - 1
  - 4
 - 8
  - 7
   - 6
  - 9

- 6
 - 3
  - 2
   - 1
  - 5
   - 4
 - 9
  - 8
   - 7
  - 10