.svg)
Incomputer science, atree is a widely usedabstract data type that represents a hierarchicaltree structure with a set of connectednodes. Each node in the tree can be connected to many children (depending on the type of tree), but must be connected to exactly one parent,[1][2] except for theroot node, which has no parent (i.e., the root node as the top-most node in the tree hierarchy). These constraints mean there are no cycles or "loops" (no node can be its own ancestor), and also that each child can be treated like the root node of its own subtree, makingrecursion a useful technique fortree traversal. In contrast tolinear data structures, many trees cannot be represented by relationships between neighboring nodes (parent and children nodes of a node under consideration, if they exist) in a single straight line (called edge or link between two adjacent nodes).
Binary trees are a commonly used type, which constrain the number of children for each parent to at most two. When the order of the children is specified, this data structure corresponds to anordered tree ingraph theory. A value or pointer to other data may be associated with every node in the tree, or sometimes only with theleaf nodes, which have no children nodes.
Theabstract data type (ADT) can be represented in a number of ways, including a list of parents with pointers to children, a list of children with pointers to parents, or a list of nodes and a separate list of parent-child relations (a specific type ofadjacency list). Representations might also be more complicated, for example usingindexes or ancestor lists for performance.
Trees as used in computing are similar to but can be different from mathematical constructs oftrees in graph theory,trees in set theory, andtrees in descriptive set theory.
Anode is a structure which may contain data and connections to other nodes, sometimes callededges orlinks. Each node in a tree has zero or morechild nodes, which are below it in the tree (by convention, trees are drawn withdescendants going downwards). A node that has a child is called the child'sparent node (orsuperior). All nodes have exactly one parent, except the topmostroot node, which has none. A node might have manyancestor nodes, such as the parent's parent. Child nodes with the same parent aresibling nodes. Typically siblings have an order, with the first one conventionally drawn on the left. Some definitions allow a tree to have no nodes at all, in which case it is calledempty.
Aninternal node (also known as aninner node,inode for short, orbranch node) is any node of a tree that has child nodes. Similarly, anexternal node (also known as anouter node,leaf node, orterminal node) is any node that does not have child nodes.
Theheight of a node is the length of the longest downward path to a leaf from that node. The height of the root is the height of the tree. Thedepth of a node is the length of the path to its root (i.e., itsroot path). Thus the root node has depth zero, leaf nodes have height zero, and a tree with only a single node (hence both a root and leaf) has depth and height zero. Conventionally, an empty tree (tree with no nodes, if such are allowed) has height −1.
Each non-root node can be treated as the root node of its ownsubtree, which includes that node and all its descendants.[a][3]
Other terms used with trees:
Stepping through the items of a tree, by means of the connections between parents and children, is calledwalking the tree, and the action is awalk of the tree. Often, an operation might be performed when a pointer arrives at a particular node. A walk in which each parent node is traversed before its children is called apre-order walk; a walk in which the children are traversed before their respective parents are traversed is called apost-order walk; a walk in which a node's left subtree, then the node itself, and finally its right subtree are traversed is called anin-order traversal. (This last scenario, referring to exactly two subtrees, a left subtree and a right subtree, assumes specifically abinary tree.) Alevel-order walk effectively performs abreadth-first search over the entirety of a tree; nodes are traversed level by level, where the root node is visited first, followed by its direct child nodes and their siblings, followed by its grandchild nodes and their siblings, etc., until all nodes in the tree have been traversed.
There are many different ways to represent trees. In working memory, nodes are typicallydynamically allocated records with pointers to their children, their parents, or both, as well as any associated data. If of a fixed size, the nodes might be stored in a list. Nodes and relationships between nodes might be stored in a separate special type ofadjacency list. Inrelational databases, nodes are typically represented as table rows, with indexed row IDs facilitating pointers between parents and children.
Nodes can also be stored as items in anarray, with relationships between them determined by their positions in the array (as in abinary heap).
Abinary tree can be implemented as a list of lists: the head of a list (the value of the first term) is the left child (subtree), while the tail (the list of second and subsequent terms) is the right child (subtree). This can be modified to allow values as well, as in LispS-expressions, where the head (value of first term) is the value of the node, the head of the tail (value of second term) is the left child, and the tail of the tail (list of third and subsequent terms) is the right child.
Ordered trees can be naturally encoded by finite sequences, for example with natural numbers.[5]
 | This sectiondoes notcite anysources. Please helpimprove this section byadding citations to reliable sources. Unsourced material may be challenged andremoved.(April 2022) (Learn how and when to remove this message) |
As anabstract data type, the abstract tree typeT with values of some typeE is defined, using the abstract forest typeF (list of trees), by the functions:
with the axioms:
In terms oftype theory, a tree is aninductive type defined by the constructorsnil (empty forest) andnode (tree with root node with given value and children).
| This sectiondoes notcite anysources. Please helpimprove this section byadding citations to reliable sources. Unsourced material may be challenged andremoved.(April 2022) (Learn how and when to remove this message) |
Viewed as a whole, a tree data structure is anordered tree, generally with values attached to each node. Concretely, it is (if required to be non-empty):
Often trees have a fixed (more properly, bounded)branching factor (outdegree), particularly always having two child nodes (possibly empty, henceat most twonon-empty child nodes), hence a "binary tree".
Allowing empty trees makes some definitions simpler, some more complicated: a rooted tree must be non-empty, hence if empty trees are allowed the above definition instead becomes "an empty tree or a rooted tree such that ...". On the other hand, empty trees simplify defining fixed branching factor: with empty trees allowed, a binary tree is a tree such that every node has exactly two children, each of which is a tree (possibly empty).
Trees are commonly used to represent or manipulatehierarchical data in applications such as:
Trees can be used to represent and manipulate various mathematical structures, such as:
Tree structures are often used for mapping the relationships between things, such as:
JSON andYAML documents can be thought of as trees, but are typically represented by nestedlists anddictionaries.
A parent can have multiple child nodes. ... However, a child node cannot have multiple parents. If a child node has multiple parents, then it is what we call a graph.
