Tree - abstract data type (ADT)

TREE

a tree is a widely used abstract data type (ADT) or data structure implementing this ADT that simulates a hierarchical tree structure, with a root value and subtrees of children, represented as a set of linked nodes. A tree data structure can be defined recursively (locally) as a collection of nodes (starting at a root node), where each node is a data structure consisting of a value, together with a list of references to nodes (the "children"), with the constraints that no reference is duplicated, and none points to the root. Alternatively, a tree can be defined abstractly as a whole (globally) as an ordered tree, with a value assigned to each node. Both these perspectives are useful: while a tree can be analyzed mathematically as a whole, when actually represented as a data structure it is usually represented and worked with separately by node (rather than as a list of nodes and an adjacency list of edges between nodes, as one may represent a digraph, for instance). For example, looking at a tree as a whole, one can talk about "the parent node" of a given node, but in general as a data structure a given node only contains the list of its children, but does not contain a reference to its parent (if any). A simple unordered tree; in this diagram, the node labeled 7 has two children, labeled 2 and 6, and one parent, labeled 2. The root node, at the top, has no parent.

Definition

A tree is a non-linear data structure that consists of a root node and potentially many levels of additional nodes that form a hierarchy. A tree can be empty with no nodes called the null or empty tree or a tree is a structure consisting of one node called the root and one or more subtrees.

Terminologies used in Trees

•     Root - the top most node in a tree.

•     Parent - the converse notion of child.

•     Siblings - nodes with the same parent.

•     Descendant - a node reachable by repeated proceeding from parent to child.

•     Leaf - a node with no children.

•     Internal node - a node with at least one child.

•     Degree - number of sub trees of a node.

•     Edge - connection between one node to another.

•     Path - a sequence of nodes and edges connecting a node with a descendant.

•      Level - The level of a node is defined by 1 + the number of connections between the node and the root.

•     Height - The height of a node is the length of the longest downward path between the

node and a leaf.

•  Forest - A forest is a set of n ≥ 0 disjoint trees.