Tree

A tree is a non linear data structure used to represent the data containing hierarchical relationship between the elements. Tree, a non-linear data structure, is a means to maintain and manipulate data in many applications.

In non-linear data structures, every data element may have more than one predecessor as well as successor. Non-linear data structures are capable of expressing more complex relationships than linear data structures.

A class of graphs that is acyclic is termed as trees.

The common uses of trees include the following:

1. Manipulating hierarchical data

2. Making information easily searchable

3. Manipulating sorted lists of data

Terminology of Trees

Root: A directed tree has one node called its root, with indegree zero.

Terminal node (leaf node): In a directed tree, any node that has an outdegree zero is a terminal node. The terminal node is also called as leaf node (or external node).

Branch node (internal node): All other nodes whose outdegree is not zero are called as branch nodes.

Level of node:  The level of any node is its path length from the root. The level of the root of a directed tree is zero, whereas the level of any node is equal to its distance from the root. Distance from the root is the number of edges to be traversed to reach the root.

 

1. A set of zero items is a tree, called the empty tree (or null tree).

2. The nodes with no subtrees are called terminal nodes or more commonly, leaves.

3. The degree of a node is the number of subtrees the node has.

4. The degree of a tree is the maximum degree of a node in the tree.

5. The length of a path is the number of edges it contains (which is one less than the number of nodes on the path).

6. The height of a tree is the length of the path from the root to a node at the lowest level. In other words, the height of a tree is the maximum path length in the tree.