Informatyka dla klas III - Ćwiczenia w programowaniu - badanie drzew binarnych

Dane jest drzewo binarne:

34 62 1 2 34 3 4 89 5 6 50 7 8 8 9 10 70 11 12 17 13 14 28 15 0 55 16 17 32 0 18 91 19 20 44 21 22 49 0 23 19 24 0 36 25 0 12 26 27 33 0 0 33 0 28 5 29 0 5 0 0 8 0 0 62 30 0 18 0 0 62 0 31 15 0 32 99 0 33 14 0 0 77 0 0 8 0 0 16 0 0 25 0 0 42 0 0 3 0 0 51 0 0

 

Dane zdefiniowane są w sposób następujący:

Najpierw pojawia się liczba n, która określa liczbę węzłów drzewa. Następnie mamy n trójek liczb dla kolejnych węzłów drzewa binarnego. Każda trójka określa: zawartość węzła, numer lewego syna i numer prawego syna. Jeśli numer potomka wynosi zero, to potomek ten nie istnieje (numer zero oznacza korzeń drzewa, a korzeń nie jest potomkiem żadnego węzła w drzewie).

Napisać program, który odczyta i utworzy drzewo binarne w pamięci komputera, a następnie wyznaczy:

1. Sumę zawartości węzłów w lewej i prawej gałęzi drzewa. Przez gałąź lewą rozumiemy poddrzewo, którego korzeniem jest lewy syn korzenia. Gałąź prawa jest poddrzewem, którego korzeniem jest prawy syn korzenia.
2. Węzeł o największej zawartości w lewej gałęzi drzewa oraz węzeł o najmniejszej zawartości w prawej gałęzi drzewa.
3. Sumę zawartości węzłów, których ojciec ma od nich większą wartość.
4. Sumę zawartości węzłów, których dzieci mają od nich większą wartość.
5. Sumę zawartości węzłów, które są liśćmi lub posiadają tylko jednego potomka.
6. Sumę zawartości węzłów na poszczególnych poziomach drzewa.
7. Sumę zawartości węzłów wzdłuż ścieżek od korzenia do poszczególnych liści. Przy każdej z tych sum należy podać numer liścia, do którego suma się odnosi.
8. Na każdym poziomie drzewa węzeł o największej i najmniejszej zawartości.

 

---

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe