Ocena brak

Jak jest zorganizowana struktura danych zwana drzewem?

Autor /Barnim7777 Dodano /29.12.2011

Drzewo składa się z odpowiedniej mnogości identycznych elementów - zwanych węzłami. Każdy węzeł zawiera:

pole kluczowe (zawiera dane)

pola dodatkowe (zawierają dane)

pola wskaźnikowe na potomstwo (zawierają adresy potomstwa – elementów następnych)

pole wskaźnikowe na rodzica (zawiera adres rodzica – elementu poprzedniego)

Opis biologiczny drzewa:

  1. wskazanie na korzeńelement wskaźnikowy (na grafie często pomijany), zawierającym adres pierwszego węzła drzewa.

  2. korzeń – pierwszy węzeł drzewa (zazwyczaj w grafie umieszczony na górze), nie posiadający rodzica.

  3. węzły – wszystkie elementy struktury leżące pomiędzy korzeniem a liśćmi.

  4. liście – elementy leżące na najniższym poziomie drzewa i nie posiadające potomstwa (ich pola wskaźnikowe przechowują wartość NIL).

Połączenia pomiędzy poszczególnymi węzłami określa się mianem gałęzi drzewa.

W celu ustanowienia hierarchii w strukturze drzewiastej przyjęto iż elementy leżące na gałęziach danego węzła określa się mianem potomstwa danego węzła. Wskazany element jest zatem rodzicem elementów jemu podległych.

W drzewie wyróżnia się także poziomy, przy czym ich odliczanie zaczyna się od góry: korzeń stanowi poziom pierwszy, a poziom ostatni tworzą liście.

Wszystkie drzewa dzieli się na:

BST – drzewo, którego rząd wyjściowy potomków ograniczony jest przez 2.

PEŁNE – drzewo, w którym wszystkie wierzchołki poza liśćmi mają jednakową liczbę potomków i wszystkie liście są na tym samym poziomie.

Podobne prace

Do góry