Overview

tree


Show Summary Details

Quick Reference

1 Most commonly, short for rooted tree, i.e. a finite set of one or more nodes such that firstly there is a single designated node called the root and secondly the remaining nodes are partitioned into n≥0 disjoint sets, T1, T2,…, Tn, where each of these sets is itself a tree. The sets T1, T2,…, Tn are called subtrees of the root. If the order of these subtrees is significant, the tree is called an ordered tree, otherwise it is sometimes called an unordered tree.

A tree corresponds to a graph with the root node matching a vertex connected by (directed) arcs to the vertices, which match the root nodes of each of its subtrees. An alternative definition of a (directed) tree can thus be given in terms from graph theory: a tree is a directed acyclic graph such that firstly there is a unique vertex, which no arcs enter, called the root, secondly every other vertex has exactly one arc entering it, and thirdly there is a unique path from the root to any vertex.

The diagram shows different representations of a tree.

2 Any connected acyclic graph.

3 Any data structure representing a tree (def. 1 or 2). For example, a rooted tree can be represented as a pointer to the representation of the root node. A representation of a node would contain pointers to the subtrees of the node as well as the data associated with the node itself. Because the number of subtrees of a node may vary, it is common practice to use a binary-tree representation.

The terminology associated with trees is either of a botanic nature, as with forest, leaf, root, or is genealogical, as with ancestor, descendant, child, parent, sibling. See also binary tree.

Tree.Sample tree represented as a Venn diagram (top) and as a directed graph

Subjects: Computing.


Reference entries

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content.