Construct a complete binary tree from given array in level order …

BlogsDope image
BlogsDope

Binary Trees in C : Array Representation and Traversals


Sept. 12, 2018


ARRAY C C++ TREE BINARY TREE BINARY SEARCH TREE DATA STRUCUTRE



588

submit your article

Become an Author


Submit your Article

Download Our App.
BlogsDope App
Get it on Google Play

Previous:

  • Trees in Computer Science
  • Binary Trees

This post is about implementing a binary tree in C using an array. You can visit  Binary Trees  for the concepts behind binary trees. We will use array representation to make a binary tree in C and then we will implement inorderpreorder and postorder traversals in both the representations and then finish this post by making a function to calculate the height of the tree.

binary tree

We will use the above tree for the array representation. As discussed in the post  Binary Trees , the array we will use to represent the above tree will be:

\0DAFEBRTGQ\0\0V\0JL

Let’s start with the first step and make an array.

#include <stdio.h> int complete_node = 15;char tree[] = '\0', 'D', 'A', 'F', 'E', 'B', 'R', 'T', 'G', 'Q', '\0', '\0', 'V', '\0', 'J', 'L';int main() return 0;

int complete_node = 15 – It is just a variable to keep the total number of nodes if the tree given is a complete binary tree.

char tree[ ] – It is the array which is storing the entire binary tree.

Now, we are ready with a binary tree and the next step is to make the functions to traverse over this binary tree. But before doing so, we need two more functions to get the left and the right children of any node. So, let’s make these functions first.

Function to Get Right and Left Children


int get_right_child(int index) if(tree[index]!='\0' && ((2*index)+1)<=complete_node) return (2*index)+1; return -1;

tree[index]!='\0' – Checking if the current node is not null.

(2*index)+1)<=complete_node – We know that the right child of node ‘i’ is given by (2*i)+1 but this value must lie within the number of elements in the array. And this condition checks the same.

return (2*index)+1 – If both the above conditions are satisfied then we are returning the index of the right child.

return -1 – In case of failure, we are returning -1, a negative value to represent failure.

Similarly, we can make a function to get the left child of the tree by using the property that the left child of node ‘i’ of a complete binary tree is given by 2*i.

int get_left_child(int index) if(tree[index]!='\0' && (2*index)<=complete_node) return 2*index; return -1;

We are now ready with the functions. So, let’s make the functions to traverse the binary tree.

Traversals in Binary Tree


Preorder Traversal

void preorder(int index) if(index>0 && tree[index]!='\0')  printf(" %c\n",tree[index]); preorder(get_left_child(index)); preorder(get_right_child(index)); 

if(index>0 && tree[index]!='\0') – We are first checking if the index given is valid or not because the functions we made above to get the children of the tree return -1 for an invalid result so, the condition index>0 checks the same. The condition tree[index]!='\0' checks if the node is not null.

printf(" %c\n",tree[index]) – We are first visiting the root.

preorder(get_left_child(index)) – Then we are visiting the left child

preorder(get_right_child(index)) – And at last, the right child.

These are explained in the  Binary Trees  post.

Similarly, we can write functions for the postorder and inorder traversals.

Postorder Traversal

void postorder(int index) if(index>0 && tree[index]!='\0')  postorder(get_left_child(index)); postorder(get_right_child(index)); printf(" %c\n",tree[index]); 

Inorder Traversal

void inorder(int index) if(index>0 && tree[index]!='\0')  inorder(get_left_child(index)); printf(" %c\n",tree[index]); inorder(get_right_child(index)); 

Let’s test these function in the main function.

#include <stdio.h> // variable to store maximum number of nodesint complete_node = 15;// array to store the treechar tree[] = '\0', 'D', 'A', 'F', 'E', 'B', 'R', 'T', 'G', 'Q', '\0', '\0', 'V', '\0', 'J', 'L';int get_right_child(int index) // node is not null // and the result must lie within the number of nodes for a complete binary tree if(tree[index]!='\0' && ((2*index)+1)<=complete_node) return (2*index)+1; // right child doesn't exist return -1;int get_left_child(int index) // node is not null // and the result must lie within the number of nodes for a complete binary tree if(tree[index]!='\0' && (2*index)<=complete_node) return 2*index; // left child doesn't exist return -1;void preorder(int index) // checking for valid index and null node if(index>0 && tree[index]!='\0')  printf(" %c ",tree[index]); // visiting root preorder(get_left_child(index)); //visiting left subtree preorder(get_right_child(index)); //visiting right subtree void postorder(int index) // checking for valid index and null node if(index>0 && tree[index]!='\0')  postorder(get_left_child(index)); //visiting left subtree postorder(get_right_child(index)); //visiting right subtree printf(" %c ",tree[index]); //visiting root void inorder(int index) // checking for valid index and null node if(index>0 && tree[index]!='\0')  inorder(get_left_child(index)); //visiting left subtree printf(" %c ",tree[index]); //visiting root inorder(get_right_child(index)); // visiting right subtree int main() printf("Preorder:\n"); preorder(1); printf("\nPostorder:\n"); postorder(1); printf("\nInorder:\n"); inorder(1);    printf("\n"); return 0;

Output:
Preorder:
 D  A  E  G  Q  B  F  R  V  T  J  L 
Postorder:
 G  Q  E  B  A  V  R  J  L  T  F  D 
Inorder:
 G  E  Q  A  B  D  V  R  F  J  T  L

Function to Determine the Height of a Binary Tree


Before making this function, we need to make one more function to determine whether a node is a leaf or not. A node is a leaf if it doesn’t have any children. Thus in our array, a node can be a leaf if both the left and the right subtrees are null like node ‘B’ or if the indices returned by the functions get_left_child and get_right child are -1 which will be in the case of nodes ‘G’, ‘Q’, ‘V’, etc.

int is_leaf(int index) // to check of the indices of the left and right children are valid or not if(!get_left_child(index) && !get_right_child(index)) return 1; // to check if both the children of the node are null or not if(tree[get_left_child(index)]=='\0' && tree[get_right_child(index)]=='\0') return 1; return 0; // node is not a leaf

!get_left_child(index) && !get_right_child(index) – The condition will be true if both the conditions are false i.e., both the indices are non-positive meaning both the left child and the right child don’t exist and thus, the node is a leaf.

tree[get_left_child(index)]=='\0' && tree[get_right_child(index)]=='\0' – If the above case is not satisfied then we are still in the function and these conditions will check if both the children of a node are null or not. In this case also, the node will be a leaf.

return 0 – If neither of the above cases is satisfied then the node is a non-leaf node.

Let’s write the function to determine the height of a binary tree.

int get_max(int a, int b) return (a>b) ? a : b;

The function given above just returns the maximum among two numbers.

int get_height(int index)

if(tree[index]=='\0' || index<=0 || is_leaf(index)) – The height of a leaf is 0. Also, for the invalid cases, the height will be 0.

return(get_max(get_height(get_left_child(index)), get_height(get_right_child(index)))+1) – The height of a node will be 1+ maximum of the height of the left subtree and the height of the right subtree.

Using this in the main function:

#include <stdio.h> int complete_node = 15;char tree[] = '\0', 'D', 'A', 'F', 'E', 'B', 'R', 'T', 'G', 'Q', '\0', '\0', 'V', '\0', 'J', 'L';int get_right_child(int index) // node is not null // and the result must lie within the number of nodes for a complete binary tree if(tree[index]!='\0' && ((2*index)+1)<=complete_node) return (2*index)+1; // right child doesn't exist return -1;int get_left_child(int index) // node is not null // and the result must lie within the number of nodes for a complete binary tree if(tree[index]!='\0' && (2*index)<=complete_node) return 2*index; // left child doesn't exist return -1;int is_leaf(int index) // to check of the indices of the left and right children are valid or not if(!get_left_child(index) && !get_right_child(index)) return 1; // to check if both the children of the node are null or not if(tree[get_left_child(index)]=='\0' && tree[get_right_child(index)]=='\0') return 1; return 0; // node is not a leafint get_max(int a, int b) return (a>b) ? a : b;int get_height(int index) // if the node is a leaf the the height will be 0 // the height will be 0 also for the invalid cases if(tree[index]=='\0' int main() printf("%d\n",get_height(1)); return 0;

Output:
3

#include <stdio.h> int complete_node = 15;char tree[] = '\0', 'D', 'A', 'F', 'E', 'B', 'R', 'T', 'G', 'Q', '\0', '\0', 'V', '\0', 'J', 'L';// funtion to get parentint get_parent(int index) if(tree[index]!='\0' && index>1 && index<=complete_node) //root has no parent return index/2; return -1;int get_right_child(int index) // node is not null // and the result must lie within the number of nodes for a complete binary tree if(tree[index]!='\0' && ((2*index)+1)<=complete_node) return (2*index)+1; // right child doesn't exist return -1;int get_left_child(int index) // node is not null // and the result must lie within the number of nodes for a complete binary tree if(tree[index]!='\0' && (2*index)<=complete_node) return 2*index; // left child doesn't exist return -1;void preorder(int index) // checking for valid index and null node if(index>0 && tree[index]!='\0')  printf(" %c ",tree[index]); // visiting root preorder(get_left_child(index)); //visiting left subtree preorder(get_right_child(index)); //visiting right subtree void postorder(int index) // checking for valid index and null node if(index>0 && tree[index]!='\0')  postorder(get_left_child(index)); //visiting left subtree postorder(get_right_child(index)); //visiting right subtree printf(" %c ",tree[index]); //visiting root void inorder(int index) // checking for valid index and null node if(index>0 && tree[index]!='\0')  inorder(get_left_child(index)); //visiting left subtree printf(" %c ",tree[index]); //visiting root inorder(get_right_child(index)); // visiting right subtree int is_leaf(int index) // to check of the indices of the left and right children are valid or not if(!get_left_child(index) && !get_right_child(index)) return 1; // to check if both the children of the node are null or not if(tree[get_left_child(index)]=='\0' && tree[get_right_child(index)]=='\0') return 1; return 0; // node is not a leafint get_max(int a, int b) return (a>b) ? a : b;int get_height(int index)

Next:

  1. Binary Tree in C: Linked Representation & Traversals
  2. Binary Search Tree
  3. Binary Search Tree in C

Liked the post?




Developer and founder of CodesDope.

MOST POPULAR

C++ : Linked lists in C++ (Singly linked list)

May 30, 2017

Inserting a new node in a linked list in C.

May 25, 2017

Backtracking – Explanation and N queens problem

Oct. 21, 2017

Making a stack using linked list in C

May 26, 2017

Making a queue using linked list in C

May 26, 2017

FOLLOW US

RECENT

Quicksort

Nov. 19, 2018

Maximum Subarray Sum Using Divide and Conquer

Nov. 13, 2018

Change Background Gradient on Scroll Using CSS

Nov. 11, 2018

12 Creative CSS and JavaScript Text Typing Animations

Nov. 11, 2018

How to Create Knockout Text with CSS

Nov. 11, 2018

You Might Also Like

Inserting a new node in a linked list in C.

C++ : Linked lists in C++ (Singly linked list)

Binary Tree in C: Linked Representation & Traversals

Binary Search Tree in C

Backtracking – Explanation and N queens problem

Sorting a list using bubble sort in Python

Sorting an array using insertion sort in C

Mouse Rollover Zoom Effect on Images

Editor’s Picks
article on blogsdope

Python Decorators – The simple way

article on blogsdope

Machine Learning : The Revolution

article on blogsdope

Backtracking – Explanation and N queens problem

article on blogsdope

CSS3 Moving Cloud Animation With Airplane

0 COMMENT

Please login to view or add comment(s).

</Dream.In.Code>: Programming & Web Development Community

Advanced Forum Search
  • Forums
  • Programming
  • Web Development
  • Computers
  • Tutorials
  • Snippets
  • Dev Blogs
  • Jobs
  • Lounge
  • Login
  • Join!
  • Today’s Topics