Tree Data Structure

Introduction:

• Trees are flexible,powerful non-linear data structure that can be used to represent data items which has hierarchical relationship
• Tree is an ideal data structure for representing hierarchical data.
• Tree can be defined as a finite set of one or more data items(ie nodes) such that
  (a) There is a special node called the root of the tree
  (b) The remaining nodes are partitioned in to n disjointed set of nodes each of which is a subtree. 
• Example of a tree(figure 1)

          This is a tree contains a set of nodes {A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S},with node A as a root node and the remaining nodes partitioned in to 3 disjointed sets {B,E,F,L,M,N},{C,G,H,O} and {D,I,J,K,P,Q,R,S}.Each of these sets is a tree because each satisfies the tree definition.

• Example of a structure that is not a tree

  

              This also contains a set of nodes {A,B,C,D,G,H,I,E,F} with node A as a root node but this is not a tree because the node E is shared. so we cant subdivide the nodes in to disjointed sets.

Tree Terminologies:

Node:

• Each data item in a tree is called a node.
• Node specifies the data information and links to other data items

Root:

• Root is the first node in the tree
• Node A is the root node in the tree example

Degree of a Node:

• Degree of a node is the number of subtrees of a node in a given tree.
• In figure1degree of node A is 3,degree of node B is 2,degree of node C is 2,degree of node D is 3 and degree of node j is 4

Degree of a Tree:

• The Degree of a tree is the maximum degree of node in a given tree.
• In figure1 node j has maximum degree as 4,all the other nodes have less or equal degree so the degree of the tree in figure 1 is 4

Leaf Node (or) Terminal Node:

• A node with degree 0 is called a leafnode
• ie a node with no subtrees or children is called leafnode.
• In figure1 nodes L,M,N,O,H,I,P,Q,R,S,K are leaf nodes
• Any node whose degree is non-zero is called non-terminal node

Level of a Node:

• The tree is structured in different levels.
• The root node is always at level 0.Then its immediate children are at level 1and their immediate children are at level 2 and so on up to the terminal nodes
• ie If a node is at level n, then its children will be at level n+1.

Depth of a tree (or)Height of a tree:

• Depth of a tree is the maximum level of any node in a given tree.
• The depth of a tree in figure 1 is 4.(including level 0)