Brushing up C part 6-data structures advanced

In continuation of my previous blog, Brushing up C, data structures, we’ll be taking up Binary Trees .

1. Terminology

  • Tree: A non-linear, hierarchical structure is called a tree. Linked list is linear, a family tree ( a representation of family members and their generations) is non linear.
  • Binary tree: A tree, where there is a parent, who has two children is called a binary tree.
  • Binary Search Tree: A binary tree, where the value of left child is less than parent value and the value of right child is more than the parent value, is called binary search tree.
  • Root: The topmost or the first node of the tree is root.
  • Parent node: The node having children.
  • Child node: The child of a parent node. The parent node has a pointer to the child node.
  • Leaf node: A node that doesn’t have any child is leaf node.

2. Why trees?

Sometimes, we want to arrange data in hierarchical manner, trees are a better choice in those cases.

Search operations on Binary Search Trees are more efficient than linked lists. We can insert and delete elements in good time.

3. Tree traversals

Unlike linked lists (which can traversed only linearly), trees can be travesed in many different ways. 

  • In order: The sequence of traversal is left child, root, right child. 
  • Pre order: Here, the root is processed first, then the left child and then the right child.
  • Post order: As is evident by now, left child first, then right child and then finally the parent node .

      4. Implementation

      The basic structure for a tree node can be defined as:
      struct treenode

      {

      int data;

      struct treenode *leftChild;

      struct treenode *rightChild;

      };

       A new node can be dynamically allocated for a new entry.

      Struct treenode * root = (struct treenode *)malloc(sizeof(struct treenode));

       Root node can be initialised as:

      root->data = someValue;

      root->leftChild = NULL;

      root->rightChild = NULL;

      When adding a child, create a new node.

       Assign the parent’s leftChild/rightChild to the new node.

      Struct treenode *newNode= (struct treenode *)malloc(sizeof(struct treenode));

      root->leftChild = newNode; 

      Or

      root->rightChild = newNode;

      depending on if new data value is less than or more than root data value.

      The search operations are generally recursive, as the nodes are recursively searched till a leaf or match is found.
      Summary

      Friends, here I end my series Brushing up C . I hope you enjoyed it, and got to learn along ☺️ .

      I will be starting my next tutorial series on C++. Please be a part of it ☺️ .

      Advertisements

      Leave a Reply

      Fill in your details below or click an icon to log in:

      WordPress.com Logo

      You are commenting using your WordPress.com account. Log Out / Change )

      Twitter picture

      You are commenting using your Twitter account. Log Out / Change )

      Facebook photo

      You are commenting using your Facebook account. Log Out / Change )

      Google+ photo

      You are commenting using your Google+ account. Log Out / Change )

      Connecting to %s