![ENC SYSTEME FIGURE](https://upload.wikimedia.org/wikipedia/commons/5/58/ENC_SYSTEME_FIGURE.jpeg)
A tree structure, tree diagram, or tree model is a way of representing the
hierarchical nature of a
structure in a graphical form. It is named a "tree structure" because the classic
representation resembles a
tree
In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are ...
, 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, see
Tree (data structure)
In computer science, a tree is a widely used abstract data type that represents a hierarchical tree structure with a set of connected nodes. Each node in the tree can be connected to many children (depending on the type of tree), but must be conn ...
for computer science; insofar as it relates to graph theory, see
tree (graph theory)
In graph theory, a tree is an undirected graph in which any two vertices are connected by ''exactly one'' path, or equivalently a connected acyclic undirected graph. A forest is an undirected graph in which any two vertices are connected by '' ...
or
tree (set theory)
In set theory, a tree is a partially ordered set (''T'', <) such that for each ''t'' ∈ ''T'', the set is well-ordered by the relation <. Frequently tre ...
. Other related articles are listed below.
Terminology and properties
The tree elements are called "
node
In general, a node is a localized swelling (a "knot") or a point of intersection (a vertex).
Node may refer to:
In mathematics
* Vertex (graph theory), a vertex in a mathematical graph
*Vertex (geometry), a point where two or more curves, lines ...
s".
The lines connecting elements are called "branches".
Nodes without children are called
leaf node
In computer science, a tree is a widely used abstract data type that represents a hierarchical tree structure with a set of connected nodes. Each node in the tree can be connected to many children (depending on the type of tree), but must be con ...
s, "end-nodes", or "leaves".
Every
finite
Finite is the opposite of infinite. It may refer to:
* Finite number (disambiguation)
* Finite set, a set whose cardinality (number of elements) is some natural number
* Finite verb, a verb form that has a subject, usually being inflected or marke ...
tree structure has a member that has no
superior. This member is called the "root" or
root node
In computer science, a tree is a widely used abstract data type that represents a hierarchical tree structure with a set of connected nodes. Each node in the tree can be connected to many children (depending on the type of tree), but must be con ...
. 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".
* 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.
* "Sibling" ("brother" or "sister") nodes share the same parent node.
* A node's "uncles" (sometimes "ommers") are siblings of that node's parent.
* A node that is connected to all lower-level nodes is called an "ancestor". The connected lower-level nodes are "descendants" of the ancestor node.
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 of
taxonomic knowledge, such as
family tree
A family tree, also called a genealogy or a pedigree chart, is a chart representing family relationships in a conventional tree structure. More detailed family trees, used in medicine and social work, are known as genograms.
Representations of ...
s, the biological
evolutionary tree
A phylogenetic tree (also phylogeny or evolutionary tree Felsenstein J. (2004). ''Inferring Phylogenies'' Sinauer Associates: Sunderland, MA.) is a branching diagram or a tree showing the evolutionary relationships among various biological spec ...
, the
evolutionary tree of a language family, the
grammatical structure
In linguistics, the grammar of a natural language is its set of structural constraints on speakers' or writers' composition of clauses, phrases, and words. The term can also refer to the study of such constraints, a field that includes domain ...
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.
The
Oxford English Dictionary
The ''Oxford English Dictionary'' (''OED'') is the first and foundational historical dictionary of the English language, published by Oxford University Press (OUP). It traces the historical development of the English language, providing a com ...
records use of both the terms "tree structure" and "tree-diagram" from 1965 in
Noam Chomsky
Avram Noam Chomsky (born December 7, 1928) is an American public intellectual: a linguist, philosopher, cognitive scientist, historian, social critic, and political activist. Sometimes called "the father of modern linguistics", Chomsky is ...
's ''
Aspects of the Theory of Syntax''.
In a tree structure there is one and only one
path
A path is a route for physical travel – see Trail.
Path or PATH may also refer to:
Physical paths of different types
* Bicycle path
* Bridle path, used by people on horseback
* Course (navigation), the intended path of a vehicle
* Desire p ...
from any point to any other point.
Computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
uses tree structures extensively (''see''
Tree (data structure)
In computer science, a tree is a widely used abstract data type that represents a hierarchical tree structure with a set of connected nodes. Each node in the tree can be connected to many children (depending on the type of tree), but must be conn ...
and
telecommunications
Telecommunication is the transmission of information by various types of technologies over wire, radio, optical, or other electromagnetic systems. It has its origin in the desire of humans for communication over a distance greater than that fe ...
.)
For a formal definition see
set theory
Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, is mostly conce ...
, and for a generalization in which children are not necessarily successors, see
prefix order In mathematics, especially order theory, a prefix ordered set generalizes the intuitive concept of a tree by introducing the possibility of continuous progress and continuous branching. Natural prefix orders often occur when considering dynamical sy ...
.
Examples of tree structures
![1934-Thermionic-Tube-Chart](https://upload.wikimedia.org/wikipedia/commons/9/90/1934-Thermionic-Tube-Chart.jpg)
* Internet:
**
usenet hierarchy
A Usenet newsgroup is a repository usually within the Usenet system, for messages posted from users in different locations using the Internet. They are discussion groups and are not devoted to publishing news. Newsgroups are technically distinc ...
* Vacuum tubes
**
Document Object Model
The Document Object Model (DOM) is a cross-platform and language-independent interface that treats an XML or HTML document as a tree structure wherein each node is an object representing a part of the document. The DOM represents a document wi ...
's logical structure,
Yahoo!
Yahoo! (, styled yahoo''!'' in its logo) is an American web services provider. It is headquartered in Sunnyvale, California and operated by the namesake company Yahoo Inc., which is 90% owned by investment funds managed by Apollo Global Manage ...
subject index,
Curlie
DMOZ (from ''directory.mozilla.org'', an earlier domain name, stylized in lowercase in its logo) was a multilingual open-content directory of World Wide Web links. The site and community who maintained it were also known as the Open Directory ...
*
Operating system
An operating system (OS) is system software that manages computer hardware, software resources, and provides common services for computer programs.
Time-sharing operating systems schedule tasks for efficient use of the system and may also in ...
:
directory structure
In computing, a directory structure is the way an operating system arranges files that are accessible to the user. Files are typically displayed in a hierarchical tree structure.
File names and extensions
A filename is a string used to uniquely ...
* Information management:
Dewey Decimal System,
PSH, this hierarchical bulleted list
* Management: hierarchical
organization
An organization or organisation (English in the Commonwealth of Nations, Commonwealth English; American and British English spelling differences#-ise, -ize (-isation, -ization), see spelling differences), is an legal entity, entity—such as ...
al structures
* Computer Science:
**
binary search tree
In computer science, a binary search tree (BST), also called an ordered or sorted binary tree, is a rooted binary tree data structure with the key of each internal node being greater than all the keys in the respective node's left subtree and ...
**
red–black tree
**
AVL tree
In computer science, an AVL tree (named after inventors Adelson-Velsky and Landis) is a self-balancing binary search tree. It was the first such data structure to be invented. In an AVL tree, the heights of the two child subtrees of any nod ...
**
R-tree
* Biology:
evolutionary tree
A phylogenetic tree (also phylogeny or evolutionary tree Felsenstein J. (2004). ''Inferring Phylogenies'' Sinauer Associates: Sunderland, MA.) is a branching diagram or a tree showing the evolutionary relationships among various biological spec ...
* Business:
pyramid selling scheme
A pyramid scheme is a business model that recruits members via a promise of payments or services for enrolling others into the scheme, rather than supplying investments or sale of product (business), products. As recruiting multiplies, recruitin ...
* Project management:
work breakdown structure
A work-breakdown structure (WBS) in project management and systems engineering is a deliverable-oriented breakdown of a project into smaller components. A work breakdown structure is a key project deliverable that organizes the team's work into ...
* Linguistics:
** (Syntax)
Phrase structure trees
** (Historical Linguistics)
Tree model
In historical linguistics, the tree model (also Stammbaum, genetic, or cladistic model) is a model of the evolution of languages analogous to the concept of a family tree, particularly a phylogenetic tree in the biological evolution of species. ...
of language change
* Sports:
business chess,
playoffs brackets
* Mathematics:
Von Neumann universe
In set theory and related branches of mathematics, the von Neumann universe, or von Neumann hierarchy of sets, denoted by ''V'', is the class of hereditary well-founded sets. This collection, which is formalized by Zermelo–Fraenkel set theory (ZF ...
* Group theory:
descendant trees
Representing trees
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
Classical node-link diagrams, that connect nodes together with line segments:
Nested sets
Nested sets that use enclosure/containment to show parenthood, examples include
TreeMaps,
fractal maps, and
Euler diagrams:
Layered "icicle" diagrams
Layered "icicle" diagrams that use alignment/adjacency.
Outlines and tree views
Lists or diagrams that use indentation, sometimes called "
outline
Outline or outlining may refer to:
* Outline (list), a document summary, in hierarchical list format
* Code folding, a method of hiding or collapsing code or text to see content in outline form
* Outline drawing, a sketch depicting the outer edge ...
s" or "
tree view
In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are u ...
s".
An outline:
:encyclopedia
::culture
:::art
:::craft
::science
A tree view:
*encyclopedia
**culture
***art
***craft
**science
Nested parentheses
A correspondence to nested parentheses was first noticed by Sir
Arthur Cayley:
((art,craft)culture,science)encyclopedia
or
encyclopedia(culture(art,craft),science)
Radial trees
Trees can also be
represented radially:
See also
;Kinds of trees:
*
B-tree
In computer science, a B-tree is a self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time. The B-tree generalizes the binary search tree, allowing for ...
*
Dancing tree
In computer science, a dancing tree is a tree data structure similar to B+ trees. It was invented by Hans Reiser, for use by the Reiser4 file system. As opposed to self-balancing binary search tree
In computer science, a self-balancing bina ...
*
Decision tree
*
Left-child right-sibling binary tree
Every multi-way or k-ary tree structure studied in computer science admits a representation as a binary tree, which goes by various names including child-sibling representation, left-child, right-sibling binary tree, doubly chained tree or filial ...
*
Porphyrian tree
The Tree of Porphyry (also known as ''scala praedicamentalis'') is a classic device for illustrating what is also called a "scale of being". It was suggested—if not first, then most famously in the European philosophical tradition—by the 3rd ...
*
Tree (data structure)
In computer science, a tree is a widely used abstract data type that represents a hierarchical tree structure with a set of connected nodes. Each node in the tree can be connected to many children (depending on the type of tree), but must be conn ...
*
Tree (graph theory)
In graph theory, a tree is an undirected graph in which any two vertices are connected by ''exactly one'' path, or equivalently a connected acyclic undirected graph. A forest is an undirected graph in which any two vertices are connected by '' ...
*
Tree (set theory)
In set theory, a tree is a partially ordered set (''T'', <) such that for each ''t'' ∈ ''T'', the set is well-ordered by the relation <. Frequently tre ...
;Related articles:
*
Data drilling
Data drilling (also drilldown) refers to any of various operations and transformations on tabular, relational, and multidimensional data. The term has widespread use in various contexts, but is primarily associated with specialized software design ...
*
Hierarchical model
A hierarchical database model is a data model in which the data are organized into a tree-like structure. The data are stored as records which are connected to one another through links. A record is a collection of fields, with each field containin ...
:
clustering and
query
*
Tree testing
Tree testing is a usability technique for evaluating the findability of topics in a website. It is also known as reverse card sorting or card-based classification.
A large website is typically organized into a hierarchy (a "tree") of topics and ...
References
Further reading
Identification of some of the basic styles of tree structures can be found in:
*
Jacques Bertin
Jacques Bertin (27 July 1918 – 3 May 2010) was a French cartographer and theorist, known from his book ''Semiologie Graphique'' (''Semiology of Graphics''), published in 1967. This monumental work, based on his experience as a cartographer and ...
, ''Semiology of Graphics'', 1983, University of Wisconsin Press (2nd edition 1973, ;
*
*Brian Johnson and
Ben Shneiderman
Ben Shneiderman (born August 21, 1947) is an American computer scientist, a Distinguished University Professor in the University of Maryland Department of Computer Science, which is part of the University of Maryland College of Computer, Mathem ...
,
Tree-maps: A space-filling approach to the visualization of hierarchical information structures, in ''Proceedings of IEEE Visualization (VIS)'', 1991, pp. 284–291, ;
*
Peter Eades
Peter D. Eades (born 8 January 1952) is an Australian computer scientist, an emeritus professor in the School of Information Technologies at the University of Sydney, known for his expertise in graph drawing.
Eades received his bachelor's deg ...
, Tao Lin, and Xuemin Lin, "Two Tree Drawing Conventions", ''International Journal of Computational Geometry and Applications'', 1993, volume 3, number 2, pp. 133–153.
*
External links
Visualization of phylogenetic trees on the T-REX serverUsing a tree structure to design a business process- from the
Society for Technical Communication
The Society for Technical Communication (STC) is a professional association dedicated to the advancement of the theory and practice of technical communication with more than 4,500 members in the United States, Canada, and the world. The society pu ...
{{DEFAULTSORT:Tree Structure
Trees (data structures)
de:Baum (Datenstruktur)
pl:Struktura drzewiasta