The implementations of Stacks and Queues from linear data structures. They cannot represent data items possessing hierarchical relationships such as between the grandfather and his descendants and in turn their descendants and so on.
We need a non-linear data structure to deal with such an application in a real-life situation. Trees and graphs are two examples of non-linear data structures.
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 the 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 a starting node known as the root note.
Learn more: Primitive Data Types and Non-Primitive Data Types
Every node other than the root has a parent node. Nodes may have any number of children.
The above figure is known as a tree that has A as the root node and others as the subtrees or leaf nodes. Simply it has three levels level 0 – root node (A), level 1 – sub-tree or nodes (B, C, D), and level 2 – sub-node (e).
Node: Each data item in a tree is called a node. It is the fundamental structure in a tree. It specifies the data and links (branches) to other data items. Root: It is the first data item (or node) in the hierarchical arrangement of data items. In the above tree, A is the root item. The degree of a node: It is the number of subtrees of a node in a given tree. For example in the above tree,
- 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
The degree of the tree: It is the maximum degree of nodes in a given tree. In the above tree the degree of node A is three In the whole tree, this value is the maximum. So the degree of the above tree is 3.
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 a 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 of the longest path from the root to the terminal nodes. The term height is also used to denote 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 a forest with three trees if we remove the root node. Non-Linear Data Structure and Algorithm