A tree is a mathematical structure that can be viewed as either a graph or as a data structure. The two views are equivalent, since a tree data structure contains not only a set of elements, but also connections between elements, giving a tree graph.
Trees were first studied by Cayley (1857). McKay maintains a database of trees up to 18 vertices, and Royle maintains one up to 20 vertices.
A tree is a set of straight line segments connected at their ends containing no closed loops (cycles). In other words, it is a simple, undirected, connected, acyclic graph
(or, equivalently, a connected forest). A tree with 
nodes has 
graph edges. Conversely, a
connected graph with 
nodes and 
edges is a tree. All trees are bipartite graphs
(Skiena 1990, p. 213). Trees with no particular node singled out are sometimes
called free trees (or unrooted tree), by way of distinguishing
them from rooted trees (Skiena 1990, Knuth 1997).
The points of connection are known as forks and the segments as branches. Final segments and the nodes at their ends are called tree leaves. A tree with two branches at each fork and with one or two tree leaves at the end of each branch is called a binary tree.
A graph can be tested in the Wolfram Language to see if it is a tree using TreeGraphQ[g].
Trees find applications in many diverse fields, including computer science, the enumeration of saturated hydrocarbons, the study of electrical circuits, etc. (Harary 1994, p. 4). The graphs graphs corresponding to linear hydrocarbons illustrated above are known as (n-)alkane graphs (or sometimes caterpillar graphs).
Trees are block graphs.
A tree 
has either one node that is a graph
center, in which case it is called a centered tree,
or two adjacent nodes that are graph centers, in
which case it is called a bicentered tree (Harary
1994, p. 35).
When a special node is designated to turn a tree into a rooted tree, it is called the root (or sometimes "Eve"). In such a tree, each of the nodes that is one graph edge further away from a given node is called a child, and nodes connected to the same node that are the same distance from the root vertex are called siblings.
Note that two branches placed end-to-end are equivalent to a single branch, which means for example, that there
is only one tree of order 3. The number 
of nonisomorphic trees of order 
, 2, ... (where trees of orders 1, 2, ..., 6 are illustrated
above), are 1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235, 551, 1301, 3159, ... (OEIS A000055).
The generating functions for the number of rooted trees
 |  |  |
(1)
|
 |  | ![xexp[sum_(r=1)^(infty)1/rT(x^r)]](/images/equations/Tree/Inline13.svg) |
(2)
|
is related to the generating function for the number of unrooted trees 
by
 |  |  |
(3)
|
 |  | ![T(x)-1/2[T^2(x)-T(x^2)].](/images/equations/Tree/Inline20.svg) |
(4)
|
Otter showed that
 |
(5)
|
(Otter 1948, Harary and Palmer 1973, Knuth 1997), where 
and 
are two constants. 
is given by
 |  |  |
(6)
|
 |  |  |
(7)
|
(OEIS A051491; Odlyzko 1995; Knuth 1997, p. 396, where Knuth writes 
instead of 
) and also as the unique
positive root of
 |
(8)
|
The constant 
is given by
 |  | ![1/(sqrt(2pi))[1+sum_(k=2)^(infty)T^'(1/(alpha^k))1/(alpha^k)]^(3/2)](/images/equations/Tree/Inline35.svg) |
(9)
|
 |  |  |
(10)
|
(OEIS A086308; Knuth 1997, p. 396).
If 
is the number of nonisomorphic trees
on 
nodes, then an asymptotic
series for 
is given by
 |
(11)
|
where the constants can be computed in terms of partial derivatives of the function
![F(x,y)=xexp[y+sum_(k=2)^infty(T(x^k))/k]-y](/images/equations/Tree/NumberedEquation4.svg) |
(12)
|
(Plotkin and Rosenthal 1994; Finch 2003).
