 | This article includes a list ofgeneral references, butit lacks sufficient correspondinginline citations. Please help toimprove this article byintroducing more precise citations.(July 2014) (Learn how and when to remove this message) |
Atree structure,tree diagram, ortree model is a way of representing thehierarchical nature of astructure in a graphical form. It is named a "tree structure" because the classicrepresentation resembles atree, although 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, seeTree (data structure) for computer science; insofar as it relates to graph theory, seetree (graph theory) ortree (set theory). Other related articles are listed below.
The tree elements are called "nodes".The lines connecting elements are called "branches". Nodes without children are calledleaf nodes, "end-nodes", or "leaves".
Everyfinite tree structure has a member that has nosuperior. This member is called the "root" orroot 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 thekinship 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".[1]
In the example, "encyclopedia" is the parent of "science" and "culture", its children. "Art" and "craft" are siblings, and children of "culture", which is their parent and thus one of their ancestors. Also, "encyclopedia", as the root of the tree, is the ancestor of "science", "culture", "art" and "craft". Finally, "science", "art" and "craft", as leaves, are ancestors of no other node.
Tree structures can depict all kinds oftaxonomic knowledge, such asfamily trees, the biologicalevolutionary tree, theevolutionary tree of a language family, thegrammatical structure of a language (a key example being S → NP VP, meaning a sentence is a noun phrase and a verb phrase, with each in turn having other components which have other components), the way web pages are logically ordered in a web site,mathematical trees of integer sets, et cetera.
TheOxford English Dictionary records use of both the terms "tree structure" and "tree-diagram" from 1965 inNoam Chomsky'sAspects of the Theory of Syntax.[2]
In a tree structure there is one and only onepath from any point to any other point.
Computer science uses tree structures extensively (seeTree (data structure) andtelecommunications.)
For a formal definition seeset theory, and for a generalization in which children are not necessarily successors, seeprefix order.
There are many ways of visually representing tree structures.Almost always, these boil down to variations, or combinations,of a few basic styles:
Classical node-link diagrams, that connect nodes together with line segments:
| encyclopedia | ||
|---|---|---|
| / culture | \ science | |
| / art | \ craft | |
Nested sets that use enclosure or containment to show parenthood; examples includeTreeMaps,fractal maps, andEuler diagrams:
 | encyclopedia | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| | ||||||||||
| |||||||||||
Layered "icicle" diagrams that use alignment/adjacency.
| encyclopedia | ||
|---|---|---|
| culture | science | |
| art | craft | |
Lists or diagrams that use indentation, sometimes called "outlines" or "tree views".
An outline:
A tree view:
A correspondence to nested parentheses was first noticed by SirArthur Cayley:
((art,craft)culture,science)encyclopedia
or
encyclopedia(culture(art,craft),science)
Trees can also berepresented radially:
| art \ | craft / |
|---|---|
| culture | | |
| encyclopedia | |
| | science | |
Identification of some of the basic styles of tree structures can be found in:
