In graph theory, a tree is a connected acyclic graph. A rooted tree is such a graph with a vertex singled out as the root. In this case, any two vertices connected by an edge inherit a parentchild relationship. An acyclic graph with multiple connected components or a set of rooted trees is sometimes called a forest.
In a tree data structure, there is no distinction between the various children of a node  none is the "first child" or "last child". A tree in which such distinctions are made is called an ordered tree, and data structures built on them are called ordered tree data structures. Ordered trees are by far the commonest form of tree data structure.
Binary trees are one kind of ordered tree, and there is a onetoone mapping between binary trees and general ordered trees.
There are many different ways to represent trees; common representations represent the nodes as records allocated on the heap with pointers to their children, their parents, or both, or as items in an array, with relationships between them determined by their positions in the array (e.g., binary heap).
See also: binary space partition, heap
Search Encyclopedia

Featured Article
