Tree data structure - 2

Trees - 2

1. Types:
   • Strictly binary tree: Degree is every node either 0 or 2.
     
   • Full Binary tree: Degree of every node is 2.
     
   • Complete Binary Tree:A binary tree in which every level , exccept possibly the last , is completely filled and all nodes are as far left as possible.
     
2. Array Representation of binary tree:
   
   • Also called as sequential representation or linear representation
   • We use 1D array
   • Store the data with indexed 1 i.e., root node at Array[1](Even we can use 0 based index )
   • If a node is at index k in the array, its left child is at index 2k and right child at index 2k+1.
   • If a node at index k then its parent is at index floor(k/2)
   • The size of array needed to store a tree of height h is 2^h-1
3. Linked list representation :
   

   • 
       struct node {
         struct node *left;
         struct node *right;
         int data;
         }
         

   • This structure can be used for the binary tree.
   • Self referential structure where first and second members are structure pointers.
   • The leaf nodes have the left and right pointers as NULL.
   • To access the root node, we maintain a pointer that points to root node.
     struct node *root;
   • For the node with pointer ptr, the left node can be accessed with ptr->left and similarly the right node can be accessed with ptr-> right
   • The linked list representation used dynamic memory allocation. Hence there are no restrictions on the size of the tree.
   • The only drawback of this representation is that it requires more memory in order to store the pointers of left and right children of each and every node.
   • Though there are many pointer which point to NULL, still we need them .. :P
   • If there are n nodes in a binary tree, there would be (n+1) nodes with NULL pointer.