TREE DATA STRUCTURE
A tree is also one of the non-linear Data structure that represent hierarchical data.
The above image shows Tree Data structure where 18 is the root element of tree structure which contain two child 15 and 25. 15 is the left child of root node 18 and 25 is the right child of parent node 18. these child node are connected to their parent node through branches.
Let’s understand some key points of the Tree data structure.
A Tree DS is collection of objects or entities called nodes and are linked together through edges called branch . It is non- Linear Data Structure as it does not form any sequence.In Tree DS the topmost level is known as root node.Each node contain some data and each data can be of any type.each node contain some Data and Each Data has some links or refrence of other nodes that can be called children.
Terms used in Tree Data Structure
. Root node- Top Most node in tree hierarchy. It is the one which does not have any parent node. It is also called the unique node .In the above diagram 10 is the root node . If any node is directly connected to any other node then it is called Parent-child Relationship.
. Child Node- if the node is descendant (successor) of any node, then the node is known as child of that node.In other words, the node which is immediate successor of that node.
. Parent Node- If the node contains any sub-node, then that node is called the parent node of that sub-node. Eg:- 15 is the parent node of 2 , 7 and 6. In other words, the node, which is predecessor of a node is called parent node.
. Siblings- The node that have same parents. Eg- 2, 7 and 6 are callled siblings.
.Leaf Node- The node of the tree which does not have any child node.These nodes are also called External Nodes. Eg- 5, 12, 9 are called leaf nodes.A leaf node is the bottom-most node of the tree. There can be any number of leaf node in general tree.
.Internal Node- A node with atleast one child is called Internal node.
.Anchestor node- any predecessor node the path of the root to that node are called anchestor of that node. 7,15,10 are anchestor of root of node 5.
.Descendant node- The immediate successor of given node is known as descendant of a node.Eg- 5 and 12 is the descendant of 7.
.SubTree- any node of a tree alog with its descendant.
Forest-If we remove root node of a tree it will become a forest. collection of disjoint trees is called a forest.you can create a forest of a tree by cutting the root of the tree.
Properties of Tree Data Structure
1>Recursive Data Structure:- The tree is knwon as recursive data ‘:”structure.A tree can be defined recursively because the distinguished node in a tree is known as root node.the root node of a tree contain link of all its subtrees. Recursion means reducing something in a self-similar manner.So this recursive property of tree data structure can be appied in various applications.
2> Number of Edges:-if there are n nodes there will be n-1 edges.Each arrow in the structure represent path or the link.Each node except the root will have atleast one incoming link known as edge. this would be one link for parent child relationship.
3>Depth of the node X:- Number of edges present in a path from a root node of a tree to that node X.one edge contribute 1 unit length in the path.In other words total no of edges between root node and node x is depth of node X.the root node has 0 edges.
4> Height of node X:- the longest path from node X to leaf node.it is the number of edges from node X to the deepest leaf( longest path from node X to leaf node).
Height of Tree:- height of root node or depth of the deepest node.
Degree of a Node:- total number of branches of that node.
Binary Tree
The tree which contain atmost 2 children . it can be 0, 1, 2.some common type of binary tree are full, complete, balanced , degenerateor pathological binary tree.
Basic Operation of tree data structure
- Insertion
- Create
- Search
- Traversal — -> preorder , post-order, in order traversal
- Preorder Traversal — perform Traveling a tree in a pre-order manner in the data structure.
- In order Traversal — perform Traveling a tree in an in-order manner.
- Post-order Traversal –perform Traveling a tree in a post-order manner.
