Tree Data Structure
Tree is one data structure often used to represent hierarchical data. For example if we want to show employee in the organization and their hierarchical position in organization hierarchy we can represent it as a tree.
The above logical structure is a tree. Tree can be defined as a collection of entities called nodes linked together by edges to simulate hierarchy. It is a nonlinear data structure.
Tree Data Structure Terminologies
Top most node (Node 1 ) is the root of the tree. Each node contains some data of any datatype and may contain a link or reference to some other node called its children.
Nodes that does not have children is called leaf nodes A tree can be considered a recursive data structure. Though having only one root node , all of its nodes serve as root nodes for its subtree.
Number of edges
Since each node contains exactly one incoming link or reference (edges) A tree of N nodes will contain N-1 edges.
Depth of the node X
Depth of the specific node X is the length of the path from root node to X node . Depth of node 5 is 2
Height of the node X
Height of the node is the number of edges in the longest path from Node x to a leaf. Height of the leaf node is Zero For a given tree height and depth may or may not be the same.
Programmatically each node in a tree can be defined as
Class Node {
public int value;
public Node left;
public Node right;
}
Some of the application of Tree data structure
Storing naturally Hierarchical data like organization structure , File system etc. Organizing data for quick search , insertion and deletion.
Some common Tree types are Binary tree , Binary search tree , AVL tree , Red Black tree. Furthermore, there are and can be more types of tree data structures, but these are the most common ones.