h2. Precizări
Un arbore binar de căutare este un arbore binar ce satisface următoarele condiţii:

* subarborele stâng al unui nod conţine numai noduri cu chei mai mici decât cheia nodului
* subarborele drept al unui nod conţine numai noduri cu chei mai mari decât cheia nodului
* atât subarborele stâng al unui nod, cât şi cel drept sunt arbori binari de căutare
O traversare PREordine (Rădacină-Stânga-Dreapta) a arborelui tipăreşte cheia rădăcinii urmată de traversarea subarborelui stâng şi apoi a celui drept. O traversare INordine (Stânga-Rădacină-Dreapta) a arborelui tipăreşte subarborele stâng, apoi tipăreşte cheia rădăcinii şi la sfârşit subarborele drept. De exemplu traversarea arborelui de mai sus este:

* PREordine: <tex>6 \: 4 \: 2 \: 1 \: 3 \: 5 \: 9 \: 7 \: 8</tex>
* INordine: <tex>1 \: 2 \: 3 \: 4 \: 5 \: 6 \: 7 \: 8 \: 9</tex>
 
 
Două secvenţe de numere <tex>X_1, X_2, \ldots, X_n</tex> şi <tex>Y_1, Y_2, \ldots, Y_n</tex> sunt ordonate lexicographic descrescător dacă:
 
* <tex>X_1 > Y_1</tex> sau
* <tex>X_1 = Y_1</tex> şi <tex>X_2 > Y_2</tex> sau
* <tex>X_1 = Y_1</tex> şi <tex>X_2 >= Y_2</tex> şi <tex>X_3 > Y_3</tex> sau
* <tex>\ldots</tex>
* <tex>X_1 = Y_1</tex> şi <tex>X_2 >= Y_2</tex> şi <tex>\ldots</tex> <tex>X_{n-1} = Y_{n-1}</tex> şi <tex>X_n >= Y_n</tex>
 

== include(page="template/taskfooter" task_id="arbori2") ==