Metody Programowania - Lista 5

Zadanie 1

Węzły drzewa mają całkowitoliczbowe pola `klucz' i `wartosc'. Drzewo jest uporządkowane względem wartości pola `klucz'. Napisać funkcję która:

• Obliczy ilość elementów drzewa
• Obliczy sumę pól `wartosc'
• Obliczy wysokość drzewa (tzn. ilość poziomów, formalnie wysokość drzewa pustego to 0, zaś niepustego to 1 plus maksimum wysokości poddzrzew)
• W polu `wartosc' wpisze ilość elementów poddrzewa którego korzeniem jest dany element
• W polu `wartosc' wpisze wysokść poddrzewa którego korzeniem jest dany element
  Podać zarówno rozwiązanie bezpośrednie jak i korzystające z funkcji przechodzenia po drzewie (funkcja `po_drzewie' z programu przykładowego).

  Zadanie 2

  Napisać funkcję, która mając daną posortowaną tablicę liczb całkowitych zbuduje maksymalnie zrównoważone drzewo, którego kluczami są liczby z tej tablicy.

  Zadanie 3

  Rozdzielić zadane drzewo binarne którego elementy mają całkowite pola `klucz' i `licznik' (uporządkowane względem wartości klucza) na dwa zależnie od tego czy licznik jest większy od zadanej wartości czy nie. Utworzone drzewa mają być uporządkowane względem wartości klucza.

  Zadanie 4

  Węzły drzewa mają całkowitoliczbowe pola `klucz' i `wartosc'. Podobnie węzły listy mają całkowitoliczbowe pola `klucz' i `wartosc'. Napisać funkcję, która mając mając dane drzewo utworzy listę której węzły mają te same wartości `klucz' i `wartosc'. Zakładamy że drzewo jest uporządkowane względem wartości klucza, chcemy żeby klucze na liście wynikowej były uporządkowane. Podobnie, napisać funkcję, która mając mając daną listę utworzy drzewo którego węzły mają te same wartości `klucz' i `wartosc'. Nic nie zakładamy o porządku elementów listy, wynikowe drzewo ma być uporządkowane względem wartości klucza (łącznie te dwie funkcje mogą posortować drzewo).