Binary Tree Implementation Using Arrays

Implementation

Converting a binary tree into a list of arrays is one interesting problem. Let us see that in depth.

In this section, we will see the implementation of the binary Trees while using arrays. let us proceed: -

#include<bits/stdc++.h>
using namespace std;
char T[10];
int root(char ky) {
if (T[0] != '\0')
	cout << "T already had root";
else
	T[0] = ky;
return 0;
}


int set_lft(char ky, int Parr) {
if (T[Parr] == '\0')
	cout << "\nCan't set child at "
	<< (Parr * 2) + 1
	<< " , no Parr found";
else
	T[(Parr * 2) + 1] = ky;
return 0;
}


int set_rt(char ky, int Parr) {
if (T[Parr] == '\0')
	cout << "\nCan't set child at "
	<< (Parr * 2) + 2
	<< " , no Parr found";
else
	T[(Parr * 2) + 2] = ky;
return 0;
}


int print_T() {
cout << "\n";
for (int i = 0; i < 10; i++) {
	if (T[i] != '\0')
	cout << T[i];
	else
	cout << "-";
}
return 0;
}
int main() {
root('A');
set_lft('B',0);
set_rt('C', 0);
set_lft('D', 1);
set_rt('E', 1);
set_rt('F', 2);
print_T();
return 0;
}

Output:

Example 2)

Let's start with the step by making an array

#include <stdio.h>


/*


           D
          / \
         /   \
        /     \
       A       F
      / \     / \    
     /   \   /   \
    E     B R     T
   / \     /     / \
  G   Q   V     J   L
*/


int CO_nod = 15;


char T[] = {'\0', 'D', 'A', 'F', 'E', 'B', 'R', 'T', 'G', 'Q', '\0', '\0', 'V', '\0', 'J', 'L'};


int main()
{
    return 0;
}
int get_rt_child(int idx)
{
    if(T[idx]!='\0' && ((2*idx)+1)<=CO_nod)
        return (2*idx)+1;
    return -1;
}
/*


           D
          / \
         /   \
        /     \
       A       F
      / \     / \    
     /   \   /   \
    E     B R     T
   / \     /     / \
  G   Q   V     J   L
*/


int CO_nod = 15;


char T[] = {'\0', 'D', 'A', 'F', 'E', 'B', 'R', 'T', 'G', 'Q', '\0', '\0', 'V', '\0', 'J', 'L'};


int get_rt_child(int idx)
{
    if(T[idx]!='\0' && ((2*idx)+1)<=CO_nod)
        return (2*idx)+1;
    return -1;
}


int get__lft_child(int idx)
{
    
    if(T[idx]!='\0' && (2*idx)<=CO_nod)
        return 2*idx;
    return -1;
}


int Is__lf(int idx)
{
    if(!get__lft_child(idx) && !get__rt_child(idx))  
        return 1;
    if(T[get__lft_child(idx)]=='\0' && T[get__rt_child(idx)]=='\0')
        return 1;
    return 0; 
}


int get_high(int x, int y)
{
    return (x>y) ? x: y;
}


int get_H(int idx)
{
    if(T[idx]=='\0' || idx<=0 || Is__lf(idx))
        return 0;
    return(get_high(get_H(get__lft_child(idx)), get_H(get_rt_child(idx)))+1);
}


int main()
{
    printf("%d\n",get_H(1));
    return 0;
}

Output:

Example 3)

#include <stdio.h>


/*


           D
          / \
         /   \
        /     \
       A       F
      / \     / \    
     /   \   /   \
    E     B R     T
   / \     /     / \
  G   Q   V     J   L
*/


int CO_nod = 15;


char T[] = {'\0', 'D', 'A', 'F', 'E', 'B', 'R', 'T', 'G', 'Q', '\0', '\0', 'V', '\0', 'J', 'L'};
//creating a function to get the parent node
int get_Parr(int idx)
{
    if(T[idx]!='\0' && idx>1 && idx<=CO_nod) 
        return idx/2;
    return -1;
}


int get__rt_child(int idx)
{
    if(T[idx]!='\0' && ((2*idx)+1)<=CO_nod)
        return (2*idx)+1;
    return -1;
}


int get__lft_child(int idx)
{
    if(T[idx]!='\0' && (2*idx)<=CO_nod)
        return 2*idx;
    return -1;
}


void pre_Ord(int idx)
{
    // checking for valid idx and NILL node
    if(idx>0 && T[idx]!='\0')
    {
        printf(" %c ",T[idx]); 
        pre_Ord(get__lft_child(idx)); 
        pre_Ord(get_rt_child(idx)); 
    }
}


void post_Ord(int idx)
{
    // checking whether the index is correct or not.
    if(idx>0 && T[idx]!='\0')
    {
        post_Ord(get__lft_child(idx)); 
        post_Ord(get_rt_child(idx)); 
        printf(" %c ",T[idx]); 
    }
}


void In_Ord(int idx)
{
    // checking whether the index is correct or not.
    if(idx>0 && T[idx]!='\0')
    {
        In_Ord(get__lft_child(idx)); 
        printf(" %c ",T[idx]); 
        In_Ord(get_rt_child(idx)); 
    }
}


int Is__lf(int idx)
{
    //verifying whether the left and right children have valid indices or not. 
    if(!get__lft_child(idx) && !get__rt_child(idx))  
        return 1;
    //verifying if both the child nodes have NILL value or not  
    if(T[get__lft_child(idx)]=='\0' && T[get_rt_child(idx)]=='\0')
        return 1;
    return 0; // node is not a leaf
}


int get_high(int x, int y)
{
    return (x>y) ? x: y;
}


int get_H(int idx)
{
    // if the node is a leaf, then the height will be 0
    // the height will be 0 also for the invalid cases
    if(T[idx]=='\0' || idx<=0 || Is__lf(idx))
        return 0;
    // height of node i is 1+ maximum among the height of left subtree and the height of right subtree
    return(get_high(get_H(get__lft_child(idx)), get_H(get_rt_child(idx)))+1);
}

Output: