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.

 

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

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