We need a non-linear data structure to deal with such application in real life situation. Trees and graphs are two examples of the non-linear data structure.
A tree is simply known as the non-linear data structure in which items are arranged in a sorted sequence. It is used to represent hierarchical relationship existing amongst several data items.
A tree is an abstract model of a hierarchical structure that consists of nodes with a parent-child relationship.
The tree is a sequence of nodes. There is starting node known as the root note. Every node other than the root has a parent node. Nodes may have any number of children.
- The degree of node A is 3
- The degree of node B is 2
- The degree of node C is 1
- The degree of node D is 0
- The degree of node E is 0
Terminal node: A node with degree zero is called a terminal node or leaf. In the above tree there are two terminal nodes E and D.
Non-terminal nodes: Any node except the root node whose degree is not zero is called non-terminal node. Non-terminal nodes are the intermediate nodes in traversing the given tree from its root node to the terminal nodes. In the above tree, there are two non-terminal nodes (B,C).
Siblings: the children nodes of a given parent node are called siblings. They are also called brothers.
Level: The entire tree structure is leveled in such a way that the root node is always at level 0. Then its immediate children are at level 1 and their immediate children are at level 2 and so on up to the terminal nodes. The level starts from 0 and children are at level n+1.
Edge: It is a connecting line of two nodes. That is the line drawn from one node to another is called an edge.
Path: It is a sequence of consecutive edges from the source to the destination node.
Depth: It is the maximum level of any leaf in a given tree. This equals the length o f the longest path from root to the terminal nodes. The term height is also used to denote the depth. The depth of the above tree is 2.
Forest: It is a set of disjoint trees. In a given tree, if we remove its root, then it becomes a forest. In the above tree there is forest with three trees if we remove the root node.