Wednesday, 20 September 2017

Important points to be remembered about Trees: A Non-Linear Data Structure

A Tree is recursively defined as a set of one or more nodes where one node is designated as the root of the tree and all remaining nodes can be partitioned into non-empty sets each of which is a sub-tree of the root. In Figure 1.show a Tree where node 2 on the top is the root node; 7, 5 are the children of the root node 2. In the Tree below, 2, 5, 11 and 4 are the leaf nodes.



Figure 1: Tree structure

  • The tree is a widely used abstract data type and Non-Linear Data structure.
  • In a Tree, the very first node is called Root Node. In above Figure, 2 is a root node
  • In a Tree, the root node is the origin of tree data structure.
  • Every Tree data structure must have root node like 2 in the figure above.
  • The connecting link between two nodes is known as an edge.
  • If Tree has 'n' number of nodes then there will be a maximum of 'n-1' edges. i.e in above figure we have 9 nodes and (9-1 = 8) edges.
  • The node which is predecessor of any node is called as Parent Node i.e 6 is the parent node of 5 and 11, 9 is the parent node of 4, 5 is parent node of 9 etc
  • Parent Node must have child nodes.
  • A node which is descendant of any node is called as Child Node i.e 4 is the child node of 9 etc
  • In Tree, all nodes except root node are child nodes. i.e 2 at the top position is never a child node.
  • Nodes which belong to the same Parent and have on the same level then they are called Siblings. i.e 2, 6 are siblings, 5, 11 are siblings, 7, 5 are siblings
  • In simple words, the nodes with the same parent are called as Sibling nodes.
  • Any Node which does not have a child is called as Leaf Node i.e 2, 5, 11 and 4 are leaf nodes.
  • Every child node will form a sub-tree of its parent node.
  • A tree can be empty with no nodes or a tree
  • Each node can have an arbitrary number of children may be 0, 1 and 2.
  • Nodes with no children are called leaves, or external nodes.
  • The depth of a node is the number of edges from the root to the node.
  • A general tree is a tree where each node may have zero or more children.
  • Every node in the tree is assigned a level number in such a way that the root node is at level 0, children of the root node are at level number 1.
  • Degree of a node is equal to the number of children that a node has.
  • The Degree of a leaf node is equal to 0.
  • In-Degree of a node is the number of edges arriving at that node.
  • Out-Degree of a node is the number of edges leaving that node.
  • Height of the Tree is the total numbers of nodes on the path from the root node to the deepest node of the tree.
  • A Tree with only a root node has a height of 1.
  • The depth of the root node is 0.

Different Types of Tree: There are different types of Tree we have in Data Structure according to there properties and features
  • General Tree
  • Forests Binary Trees
  • Binary Search Trees
  • Expression Trees
  • Tournament Trees

Thanks
Mukesh Rajput

No comments:

Post a Comment

Thanks
Mukesh Rajput