Struktura drzewa - Tree structure

Struktura drzewa przedstawiająca możliwą hierarchiczną organizację encyklopedii
Oryginalna Encyklopedia użyła diagramu drzewa, aby pokazać, w jaki sposób uporządkowano przedmioty.

Struktury drzewa , schemat drzewa lub drzewa modelu jest sposób reprezentującą hierarchiczną naturę konstrukcji w formie graficznej. Nazywa się ją „strukturą drzewa”, ponieważ klasyczna reprezentacja przypomina drzewo , chociaż wykres jest zazwyczaj odwrócony do góry nogami w porównaniu z drzewem biologicznym, z „łodygiem” na górze i „liście” na dole.

Struktura drzewa ma charakter koncepcyjny i występuje w kilku formach. Aby zapoznać się z omówieniem struktur drzewiastych w określonych dziedzinach, zobacz Drzewo (struktura danych) dla informatyki; o ile odnosi się to do teorii grafów, patrz drzewo (teoria grafów) lub drzewo (teoria mnogości) . Inne powiązane artykuły są wymienione poniżej.

Terminologia i właściwości

Elementy drzewa nazywane są „ węzłami ”. Linie łączące elementy nazywane są „gałęziami”. Węzły bez dzieci nazywane są węzłami liści , „węzłami końcowymi” lub „liśćmi”.

Każda skończona struktura drzewa ma członka, który nie ma nadrzędnego . Ten element członkowski nazywa się „root” lub root node . Korzeń jest węzłem początkowym. Ale odwrotnie nie jest prawdą: nieskończone struktury drzewiaste mogą mieć węzeł główny lub nie.

Nazwy relacji między węzłami modelują terminologię pokrewieństwa relacji rodzinnych. Neutralne pod względem płci imiona „rodzic” i „dziecko” w dużej mierze wyparły starszą terminologię „ojciec” i „syn”. Termin „wujek” jest nadal powszechnie używany dla innych węzłów na tym samym poziomie co rodzic, chociaż czasami jest zastępowany terminami neutralnymi pod względem płci, takimi jak „ommer”.

  • „Rodzic” węzła to węzeł o jeden stopień wyżej w hierarchii (tj. bliżej węzła głównego) i leżący w tej samej gałęzi.
  • Węzły „rodzeństwo” („brat” lub „siostra”) współdzielą ten sam węzeł nadrzędny.
  • „Wujkowie” węzła (czasami „omerzy”) są rodzeństwem rodzica tego węzła.
  • Węzeł, który jest połączony ze wszystkimi węzłami niższego poziomu, nazywany jest „przodkiem”. Połączone węzły niższego poziomu są „potomkami” węzła przodka.

W tym przykładzie „encyklopedia” jest rodzicem „nauki” i „kultury”, jej dzieci. „Sztuka” i „rzemiosło” to rodzeństwo i dzieci „kultury”, która jest ich rodzicem, a tym samym jednym z ich przodków. Również „encyklopedia”, jako korzeń drzewa, jest przodkiem „nauki”, „kultury”, „sztuki” i „rzemiosła”. Wreszcie „nauka”, „sztuka” i „rzemiosło”, jak liście, nie są przodkami żadnego innego węzła.

Struktury drzewiaste mogą przedstawiać wszystkie rodzaje wiedzy taksonomicznej , takie jak drzewa genealogiczne , biologiczne drzewo ewolucyjne, drzewo ewolucyjne rodziny językowej , struktura gramatyczna języka (kluczowym przykładem jest S → NP VP, co oznacza, że ​​zdanie jest rzeczownikiem fraza i fraza czasownika, z których każda ma inne składniki, które mają inne składniki), sposób logicznego uporządkowania stron internetowych na stronie internetowej, drzewa matematyczne zbiorów liczb całkowitych i tak dalej.

The Oxford English Dictionary rekordy użyć zarówno określenia „struktury drzewa” i „drzewa wykresie” z 1965 roku w Noam Chomsky „s aspektów teorii składni .

W strukturze drzewa istnieje jedna i tylko jedna ścieżka z dowolnego punktu do dowolnego innego punktu.

Informatyka intensywnie wykorzystuje struktury drzewiaste ( patrz Drzewo (struktura danych) i telekomunikacja ).

Aby uzyskać formalną definicję, zobacz teorię mnogości , a dla uogólnienia, w którym dzieci niekoniecznie są następcami, zobacz kolejność prefiksów .

Przykłady struktur drzewiastych

Mapa drzewa używana do reprezentowania struktury katalogów jako zestawu zagnieżdżonego
diagram informacyjny w kształcie drzewa ilustrujący „ewolucję” lamp termionowych (rodzaj lampy próżniowej) w latach 1883-1934

Reprezentowanie drzew

Istnieje wiele sposobów wizualnego przedstawiania struktur drzewiastych. Niemal zawsze sprowadzają się one do wariacji lub kombinacji kilku podstawowych stylów:

Klasyczne diagramy węzeł-łącze

Klasyczne diagramy węzłowo-łączowe, łączące węzły za pomocą odcinków liniowych:

encyklopedia
/
kultura
\
nauka
/
sztuka
\
rzemiosło

Zestawy zagnieżdżone

Zestawy zagnieżdżone, które używają obudowy/zamknięcia do pokazania rodzicielstwa, przykłady obejmują TreeMaps i mapy fraktalne :

Pusty.png encyklopedia
Pusty.png Pusty.png
Pusty.png kultura
Pusty.png Pusty.png
rzemiosło artystyczne
nauki ścisłe 

Warstwowe diagramy „sopel”

Warstwowe diagramy „sopli”, które wykorzystują wyrównanie/sąsiedztwo.

encyklopedia
kultura nauki ścisłe
Sztuka rękodzieło

Kontury i widoki drzew

Listy lub diagramy z wcięciami, czasami nazywane „ konturami ” lub „ widokami drzewa ”.

Zarys:

encyklopedia
kultura
Sztuka
rękodzieło
nauki ścisłe

Widok drzewa:

  • encyklopedia
    • kultura
      • Sztuka
      • rękodzieło
    • nauki ścisłe

Zagnieżdżone nawiasy

Korespondencję z zagnieżdżonymi nawiasami po raz pierwszy zauważył Sir Arthur Cayley :

((sztuka, rzemiosło)kultura,nauka)encyklopedia
lub
encyklopedia(kultura(sztuka,rzemiosło),nauka)

Drzewa promieniste

Drzewa mogą być również reprezentowane promieniście :

sztuka
      \
rzemiosło
/    
kultura
|
encyklopedia
|
nauki ścisłe

Zobacz też

Rodzaje drzew
Powiązane artykuły

Bibliografia

  1. ^ „Słownik Ethereum” . GitHub . Źródło 17 kwietnia 2019 .
  2. ^ "drzewo" . Oxford English Dictionary (red. online). Oxford University Press.  ( Wymagana subskrypcja lub członkostwo instytucji uczestniczącej ).
  3. ^ „Co to jest obiektowy model dokumentu?” . Domena architektury W3C . Źródło 2006-12-05 .

Dalsza lektura

Identyfikację niektórych podstawowych stylów struktur drzewiastych można znaleźć w:

Zewnętrzne linki