- Tree is the Non-Linear data structure, which is actually extended version of Graph Data Structure.
- Tree is something related to the linked list ,But in the ,Any node can be points any number of nodes.
- Tree is used to store the data in hierarchical or Categorical fashion.
- Ordering of Data is not much important in Tree .Ordering of Data is important in the Queue,Stack ,Linked Lists and Array types of Data structure.
1-Buzzword of Tree
There are some fundamentals properties of Tree, we have to know those properties because those will be use a lot at many places :
1.1-Child & Parent Node:
A node which is containing the address of another nodes, then address contained node is called Parent node and second one is called child node.
Node E is pointing to the Node G and H ,means Node E is containing the address of node G and node H. So node E will be Parent Node of node G and H. and Node G and H will be Child node of node E.
1.2-Root Node:
a node which does not have any parent node ,that node is called Root Node.for a tree at most one Root node is possible.Root node is the first node of the Tree.For any operation ,we have to start from the root node.
Node E is the Root node for the above Tree.
1.3-Edge :
Edge is used to connect the nodes to each other,Edge is the graphical representation of Address Linkup among the nodes.
Here node E is containing the addresses of node G and H , So one edge is used for representation.
1.4-Leaf Node :
A node which don’t have any child node is called Leaf node.means if a node which doesn’t contain the addresses of any node,then this types of node is called Leaf Node.
Node G and H are the leaf node ,because these are not pointing to any other node .but node E is not an leaf node,because node E is containing the address of node G and H.
1.5-Sibling of Node :
Children node of same Parent node is called the sibling node.means Addresses of nodes are containing by the another same Node,then those nodes are called the sibling of each other.
Addresses of the node G and H are contained by the Parent Node E,So node G and H will be Sibling of each other.
1.6-Ancestor & descendant of node :
An node X will be ancestor of all node(say P,Q,R and S) ,if there is a connected path from X to all node.all node will be descendant of X.
- For path BD , B is the ancestor of the D. and D is the descendant of the B.
- For path BEG and BEH ,B is the ancestor of the E,G and H, and E is the ancestor of the G and H.
- E,G and H will be the descendant of B.
- G and H are the descendant of E.
1.7-Level/Depth of node :
- Level is the length from root to specific node. Level of root node is always 0. Level is actually a depth of node from the root node.
- The depth of a node is the total number of edges from the specific node to the root node.
- Level of D are 1.
- Level of G and H are 2.
- Level of B(root node) is 0.
1.8-Height of node :
- Height of node is the length of longest path from node to the leaf node.
- Height is the length from the node to the deepest node.
- Height of all leaf node will be 0.
- Height of B is 2 ,because longest path from B to leaf is BEH.
- Height of D,G and H is 0,because D,G and H are the leaf node,and height of leaf node is 0 always.
- Height of E is the 1.
2-Node Representation
- Every node of a tree contains 2 parts :
1 – : pointer variable to store the address of child node.
2 – : one Data variable to store the DataElement which is stored on a node. - Number of pointer variable is depend upon the total number of child node of the specific node.
- See the below Example :
- We can implement Node of Tree using any Programming Language.In C & C++ ,we can use structure or class data structure.
3-Operations on Tree
There are following operations ,we can apply on the Tree Data structure :
- Insertion : Addition of node into an Tree.
- Deletion : Removal of node from the Tree.
- Searching : Finding the required DataElement contained by Node.
- Traversing : Visiting on every node at least once.
- Size : finding the total number of node in a Tree.
4-Applications of Tree
Tree Data structure is broadly used in the field of Software field ,specially in Standard software development field.
- Representation of Expression in Compiler is used Tree data structure.
- Tree data structure id use to design the Data Compression Algorithm like Huffman compression algorithm.
- Tree use to design Abstract Syntax Tree for Programming Language.
- Tree use to design Parse Tree for human language.
- Tree is use to implement the Directory structure of Operating system.