En trädstruktur är ett sätt att representera en hierarkisk struktur på ett grafiskt sätt.
Det kallas en trädstruktur på grund av att grafen ser ut som ett inverterat träd . Av samma anledning säger de att rotnoden (roten) är längst upp, och bladen är längst ner.
I grafteorin är ett träd en sammankopplad acyklisk graf (för oriktade grafer) eller en sammankopplad acyklisk graf där högst en nod inte har några inkommande kanter, och de återstående noderna har exakt en inkommande nod (för riktade grafer).
En acyklisk riktad graf utan ett strikt länkvillkor kallas ett nätverk, en oansluten graf av flera träd kallas en skog .
Heterogena semantiska nätverk består av en uppsättning trädliknande strukturer .
Varje lövträd innehåller ett element som inte har någon förälder . Detta element kallas "root" eller "root node" . Det kan betraktas som den första (eller start) noden.
Det omvända är inte sant i allmänhet: oändliga trädstrukturer kan ha rotnoder eller inte.
Linjerna som förbinder elementen kallas "grenar", och själva elementen kallas noder . Noder utan barn kallas "bladnoder" eller "löv".
Namnen på länkar mellan noder är namngivna enligt principen om familjerelationer.
I väst, inom datavetenskap, används huvudsakligen endast namnen på maskulina familjemedlemmar; på ryska, för att beteckna en nod som är direkt relaterad till föräldernoden och är lägre i hierarkin, kallas det ofta "barn ".
Inom lingvistik (t.ex. engelska) används tvärtom namnen på kvinnliga familjemedlemmar. Detta indikerar en återgång till den vanliga namnkonventionen, sponsrad av studenter till den berömda amerikanske lingvisten Noam Chomsky . Trots detta, inom datavetenskap ersätts ofta de neutrala namnen "förälder" och "barn" med orden "far" och "son", dessutom används termen "farbror" inte mindre aktivt för att referera till andra noder som är på samma nivå som föräldern. .
I exemplet ovan är "uppslagsverk" föräldern till "vetenskap" och "kultur", som är respektive "barn". "Konst" och "hantverk" är bröder i förhållande till varandra och barn i förhållande till "kultur".
Trädstrukturer används för att visa all slags information från taxonomiområdet , såsom släktträdet , fylogenetiskt träd , språkets grammatiska struktur (till exempel på engelska, ett bra exempel är schemat S → NP VP, vilket betyder att meningen (satsen) är en substantivfras (substantivfras) och en verbgrupp (verbfras), ett sätt att logiskt ordna webbsidor på en webbplats, och så vidare.
I en trädstruktur kan det finnas en och endast en väg från en punkt till en annan punkt.
Trädstrukturer används flitigt inom datavetenskap (se Träd (datastruktur) och Kommunikation (teknik) ).
Det kan finnas olika semantiska relationer mellan noderna i en trädstruktur .
I verkliga uppslagsverk ( Wikipedia ), finns alla sådana DS i antagonism, om systemet för deras presentation inte är genomtänkt separat och som en helhet.
Olika typer av länkar används i strukturen av tematiskt homogena grupper av Wikipedia-artiklar . Inledningsvis identifieras sektioner som skiljer sig åt när det gäller tidpunkten för uppkomsten av föremålen för artiklar (Inanimate nature, Wildlife, Humanity, Technosphere), sedan länkar mellan strukturella nivåer inom sektioner, länkar mellan homogena artiklar (genus-arter) används, den sista i hierarkin används antalet artiklar i gruppen.
Det finns många sätt att grafiskt representera trädstrukturer. I de allra flesta fall kommer de ner till olika varianter eller kombinationer av flera grundläggande stilar:
Beskrivningar av några grundläggande metoder finns i:
| Träd (datastruktur) | |
|---|---|
| Binära träd | |
| Självbalanserande binära träd |
|
| B-träd | |
| prefix träd |
|
| Binär uppdelning av utrymme | |
| Icke-binära träd |
|
| Bryter upp utrymmet |
|
| Andra träd |
|
| Algoritmer | |