Stromová struktura - Tree structure
![]() | Tento článek obsahuje seznam obecných Reference, ale zůstává z velké části neověřený, protože postrádá dostatečné odpovídající vložené citace.Červenec 2014) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) ( |


A stromová struktura nebo stromový diagram je způsob reprezentace hierarchický povaha a struktura v grafické podobě. Je pojmenován jako „stromová struktura“, protože je klasický zastoupení připomíná a strom, i když je graf obecně ve srovnání s biologickým stromem vzhůru nohama, s „stonkem“ nahoře a „listy“ dole.
Stromová struktura je koncepční a objevuje se v několika formách. Diskuse o stromových strukturách v konkrétních polích viz Strom (datová struktura) pro informatiku: pokud jde o teorii grafů, viz strom (teorie grafů), nebo také strom (teorie množin). Jsou uvedeny další související články.
Terminologie a vlastnosti
Prvky stromu se nazývají „uzly ". Spojovací prvky vedení se nazývají" větve ". Nazývají se uzly bez dětí listové uzly, „koncové uzly“ nebo „listy“.
Každý konečný stromová struktura má člena, který nemá žádné nadřízený. Tento člen se nazývá „root“ nebo kořenový uzel. Kořen je počáteční uzel. Ale obrácení není pravdivé: nekonečné stromové struktury mohou nebo nemusí mít kořenový uzel.
Názvy vztahů mezi uzly modelují příbuzenství terminologie rodinných vztahů. Rodově neutrální názvy „rodič“ a „dítě“ do značné míry vytlačily starší terminologii „otec“ a „syn“. Termín „strýc“ je stále široce používán pro jiné uzly na stejné úrovni jako rodič, ačkoli je někdy nahrazen genderově neutrálními termíny jako „ommer“.[1]
- „Rodič“ uzlu je uzel o jeden stupeň výše v hierarchii (tj. Blíže ke kořenovému uzlu) a ležící na stejné větvi.
- Uzly „sourozenec“ („bratr“ nebo „sestra“) sdílejí stejný nadřazený uzel.
- „Strýcové“ uzlu (někdy „ommers“) jsou sourozenci rodiče tohoto uzlu.
- Uzel, který je připojen ke všem uzlům nižší úrovně, se nazývá „předek“. Připojené uzly nižší úrovně jsou „potomky“ uzlu předka.
V tomto příkladu je „encyklopedie“ rodičem „vědy“ a „kultury“, jejích dětí. „Umění“ a „řemeslo“ jsou sourozenci a děti „kultury“, která je jejich rodičem, a tedy jedním z jejich předků. „Encyklopedie“ jako kořen stromu je také předkem „vědy“, „kultury“, „umění“ a „řemesla“. A konečně, „věda“, „umění“ a „řemeslo“, jako listy, nejsou předky žádného jiného uzlu.
Stromové struktury mohou zobrazovat všechny druhy taxonomické znalosti, jako např rodokmeny biologické evoluční strom, evoluční strom jazykové rodiny, gramatická struktura jazyka (klíčovým příkladem je S → NP VP, což znamená, že věta je jmenná fráze a slovesná fráze, přičemž každá z nich má další komponenty, které mají další komponenty), způsob, jakým jsou webové stránky logicky seřazeny na webové stránce, matematické stromy celočíselných množin atd.
The Oxfordský anglický slovník zaznamenává použití výrazů „stromová struktura“ a „stromový diagram“ od roku 1965 v roce Noam Chomsky je Aspekty teorie syntaxe.[2]
Ve stromové struktuře je jedna a pouze jedna cesta z jakéhokoli bodu do jiného bodu.
Počítačová věda značně využívá stromové struktury (vidět Strom (datová struktura) a telekomunikace.)
Formální definice viz teorie množin, a pro zobecnění, ve kterém děti nemusí být nutně nástupci, viz pořadí prefixů.
Příklady stromových struktur


- Internet:
- Vakuové trubky
- Model objektu dokumentu logická struktura,[3] Yahoo! předmětový index, Curlie
- Operační systém: adresářová struktura
- Správa informací: Deweyův desetinný systém, PSH, tento hierarchický seznam s odrážkami
- Řízení: hierarchické organizační struktur
- Počítačová věda:
- Biologie: evoluční strom
- Podnikání: pyramidový prodejní režim
- Projektový management: struktura rozpisu práce
- Lingvistika:
- (Syntax) Stromy frázové struktury
- (Historická lingvistika) Stromový model jazykové změny
- Sportovní: obchodní šachy, závorky play-off
- Matematika: Von Neumannův vesmír
- Teorie skupin: potomci stromů
Představující stromy
Existuje mnoho způsobů, jak vizuálně znázornit stromové struktury. Téměř vždy se tyto scvrkávají na variace nebo kombinace několika základních stylů:
Klasické diagramy uzlů a spojů
Klasické diagramy uzlů a spojů, které spojují uzly s úsečkami:
encyklopedie | ||
---|---|---|
/ kultura | \ Věda | |
/ umění | \ řemeslo |
Vnořené sady
Vnořené sady mezi příklady patří uzavření / zadržení k prokázání rodičovství TreeMaps a fraktální mapy:
![]() | encyklopedie | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
![]() | ![]() | ||||||||||
|
Vrstvené diagramy „rampouchu“
Vrstvené diagramy „rampouchů“, které používají zarovnání / sousednost.
encyklopedie | ||
---|---|---|
kultura | Věda | |
umění | řemeslo |
Obrysy a zobrazení stromů
Seznamy nebo diagramy, které používají odsazení, někdy nazývané „obrysy „nebo“zobrazení stromů ".
Osnova:
- encyklopedie
- kultura
- umění
- řemeslo
- Věda
- kultura
Pohled na strom:
- encyklopedie
- kultura
- umění
- řemeslo
- Věda
- kultura
Vnořené závorky
Nejprve si Sir všiml korespondence se vnořenými závorkami Arthur Cayley:
encyklopedie ((umění, řemeslo) kultura, věda)
nebo
encyklopedie (kultura (umění, řemeslo), věda)
Radiální stromy
Stromy také mohou být reprezentován radiálně:
umění \ | řemeslo / |
---|---|
kultura | | |
encyklopedie | |
| Věda |
Viz také
- Druhy stromů
- B-strom
- Tančící strom
- Rozhodovací strom
- Binární strom levého a pravého sourozence
- Strom (datová struktura)
- Strom (teorie grafů)
- Strom (teorie množin)
- Související články
Reference
- ^ „Slovník Etherea“. GitHub. Citováno 17. dubna 2019.
- ^ "strom". Oxfordský anglický slovník (Online ed.). Oxford University Press. (Předplatné nebo členství v zúčastněné instituci Požadované.)
- ^ „Co je to Object Object Model?“. Doména W3C Architecture. Citováno 2006-12-05.
Další čtení
Identifikaci některých základních stylů stromových struktur najdete v:
- Jacques Bertin, Semiologie grafiky1983, University of Wisconsin Press (2. vydání 1973, ISBN 978-0299090609;
- Donald E. Knuth, Umění počítačového programování, Volume I: Fundamental Algorithms, 1968, Addison-Wesley, str. 309–310;
- Brian Johnson a Ben Shneiderman, Stromové mapy: Přístup vyplňující prostor k vizualizaci hierarchických informačních struktur, ve sborníku ze dne IEEE Vizualizace (VIS), 1991, s. 284–291, ISBN 0-8186-2245-8;
- Peter Eades, Tao Lin a Xuemin Lin, Dvě konvence kreslení stromů, International Journal of Computational Geometry and Applications, 1993, svazek 3, číslo 2, str. 133–153.
- Manuel Lima, Kniha stromů: Vizualizace větví znalostí (2014), Princeton Architectural Press, ISBN 978-1-616-89218-0