Tree structure: Difference between revisions

Revision as of 21:17, 25 June 2021

Latest revision as of 18:17, 5 August 2025

(45 intermediate revisions by 35 users not shown)

Line 2:

{{more footnotes|date=July 2014}}

[[File:Binary tree structure.svg|300px|thumb|A tree structure showing the possible hierarchical organization of an encyclopedia]]

[[File:ENC SYSTEME FIGURE.jpeg|300px|thumb|The original [[Encyclopédie]] (1752) used a tree diagram to show the way in which its subjects were ordered.]]

A '''tree structure''' or, '''tree diagram,''', or '''tree model''' is a way of representing the [[hierarchy|hierarchical]] nature of a [[structure]] in a graphical form. It is named a "tree structure" because the classic [[#Representing trees|representation]] resembles a [[tree]], even thoughalthough the chart is generally upside down compared to a biological tree, with the "stem" at the top and the "leaves" at the bottom.

A tree structure is conceptual, and appears in several forms. For a discussion of tree structures in specific fields, see [[Tree (data structure)]] for computer science:; insofar as it relates to graph theory, see [[tree (graph theory)]], or also [[tree (set theory)]]. Other related articles are listed below.

==Terminology and properties==

Line 14:

Every [[Finite set|finite]] tree structure has a member that has no [[superior (hierarchy)|superior]]. This member is called the "root" or [[root node]]. The root is the starting node. But the converse is not true: infinite tree structures may or may not have a root node.

The names of relationships between nodes model the [[kinship terminology]] of family relations. The gender-neutral names "parent" and "child" have largely displaced the older "father" and "son" terminology. The term "uncle" is still widely used for other nodes at the same level as the parent, although it is sometimes replaced with gender-neutral terms like "ommer".<ref>{{cite web |title=Ethereum Glossary |url=https://github.com/ethereum/wiki/wiki/Glossary |website=GitHub |access-date=17 April 2019 |archive-date=25 April 2019 |archive-url=https://web.archive.org/web/20190425135357/https://github.com/ethereum/wiki/wiki/Glossary |url-status=live }}</ref>

* A node's "parent" is a node one step higher in the hierarchy (i.e. closer to the root node) and lying on the same branch.

Line 37:

== Examples of tree structures ==

[[File:Tree Map.png|thumb|A tree map used to represent a [[directory structure]] as a [[nested set]] ]]

[[File:1934-Thermionic-Tube-Chart.jpg|thumb|informationA diagram in the shape of a tree illustrating the "evolution" of thermionic tubes (a type of vacuum tube) between 1883 and 1934]]

* Internet:

** [[usenet hierarchy]]

** [[Document Object Model]]'s logical structure,<ref>{{cite web |url=http://www.w3.org/TR/DOM-Level-2-Core/introduction.html |title=What is the Document Object Model? |access-date=2006-12-05 |work=W3C Architecture ___domain |archive-date=2012-02-12 |archive-url=https://web.archive.org/web/20120212033934/http://www.w3.org/TR/DOM-Level-2-Core/introduction.html |url-status=live }}</ref> [[Yahoo!]] subject index, [[Curlie]]

* Vacuum tubes

** [[Document Object Model]]'s logical structure,<ref>{{cite web |url=http://www.w3.org/TR/DOM-Level-2-Core/introduction.html |title=What is the Document Object Model? |access-date=2006-12-05 |work=W3C Architecture ___domain }}</ref> [[Yahoo!]] subject index, [[Curlie]]

* [[Operating system]]: [[directory structure]]

* Information management: [[Dewey Decimal Classification|Dewey Decimal System]], [[Polythematic Structured Subject Heading System|PSH]], this hierarchical bulleted list

* Management: hierarchical [[organization]]al structures

* Computer Sciencescience:

** [[binary search tree]]

** [[red–black tree]]

** [[AVL tree]]

** [[R-tree]]

** [[doubly logarithmic tree]]

* Biology: [[evolutionary tree]]

* Business: [[pyramid selling scheme]]

Line 80:

! style="padding:0 0.5em;" | \<br/>craft

|}</div>

{{clear-}}

=== Nested sets ===

[[Nested set modelcollection| Nested sets]] that use enclosure/ or containment to show parenthood,; examples include [[treemapping|TreeMaps]] and, [[fractal space map|fractal maps]], and [[Euler diagram|Euler diagrams]]:

<div style="float:left;clear:right;text-align:center;margin:0.2em 0 0.2em 1em;padding:0.5em 1em 1em 1em;border:1px solid silver;border-radius: 1em;">

Line 189 ⟶ 190:

* [[Decision tree]]

* [[Left-child right-sibling binary tree]]

* [[Porphyrian tree]]

* [[Tree (data structure)]]

* [[Tree (graph theory)]]

Line 204 ⟶ 206:

Identification of some of the basic styles of tree structures can be found in:

*[[Jacques Bertin]], ''Semiology of Graphics'', 1983, University of Wisconsin Press (2nd edition 1973, {{ISBN|978-0299090609}};

*{{cite book |author=[[Donald E. Knuth]], ''|title=[[The Art of Computer Programming]]'', |series=Volume I1: Fundamental Algorithms, |year=1968, |publisher=Addison-Wesley, pp.&nbsp;|pages=309–310;}}

*Brian Johnson and [[Ben Shneiderman]], ''"[httphttps://ieeexplore.ieee.org/document/175815 Tree-maps: A space-filling approach to the visualization of hierarchical information structures]''", in ''Proceedings of [[IEEE]] Visualization (VIS)'', 1991, pp.&nbsp;284–291, {{ISBN|0-8186-2245-8}};

*[[Peter Eades]], Tao Lin, and Xuemin Lin, ''"Two Tree Drawing Conventions''", ''International Journal of Computational Geometry and Applications'', 1993, volume 3, number 2, pp.&nbsp;133–153.

*[[{{cite book |author1=Manuel Lima]], ''|author1-link=Manuel Lima |title=The Book of Trees: Visualizing Branches of Knowledge'' (|date=2014), [[|publisher=Princeton Architectural Press]], {{ISBN|___location=New York |isbn=978-1-616-89218-0 |edition=1st}}

== External links ==

{{Commons|Tree diagram}}

* [http://www.trex.uqam.ca Visualization of phylogenetic trees on the T-REX server]

* [http://www.stcwdc.org/PDF/newsletter_may05.pdf Using a tree structure to design a business process] -– from the [[Society for Technical Communication]]

{{DEFAULTSORT:Tree Structure}}

[[Category:Trees (data structures)]]

[[Category:Conceptual models]]

[[de:Baum (Datenstruktur)]]