Relation: explicitly defined hierarchical order

Note: the Abstract Tree describes storage techniques for hierarchical orderings: this is fundamentally different from a search-tree data structure or a heap-based data structure used to store implicitly defined linear orders.

The Abstract Tree is defined for objects on which a hierarchical ordering is placed. Convention has it that the objects within a tree are referred to as nodes.

The children of a particular node may or may not be linearly ordered. If the children can be linearly ordered, certain operations may be easier to implement efficiently.

Operations Relevant for Abstract Trees

• Access the root node,
• Given a reference to a node:
• Access the parent if it is not the root node,
• Determine the depth of the node,
• Iterate through the ancestors back to the root node,
• Determine the number of children,
• Iterate through the children,
• Determine the number of descendants, and
• Iterate through all the descendants in a predictable manner (breadth-first traversal or depth-first traversal); and

Example Data Structures

The most common data structure for the Abstract Tree is a general tree. It is very seldom that a general tree is is actually a binary tree or even an N-ary tree. One such case is the tree of all ancestors of an individual: the individual is the root, the individual's genetic parents are the children of the root, and at each step, the two genetic parents are the children of the node.