Monday, February 17, 2014

C: Create Binary Search Tree from a Array

Hi, Today we will create a Binary Search Tree, which is nothing but a Sorted Binary Tree. The methods which we have used here are:

  1. Create Tree to iterate the Tree to the length of the array, with a reference to the array and to the root of the Tree
  2. Create a Method to create a node and on the basis of the value at the index in the array and condition to put the node in the Tree should satisfy 
  3. Print theTree
#include <stdio.h>
#include <stdlib.h>

struct BST
{
    struct BST* left;
    int info;
    struct BST* right;
};

void createTree(struct BST*, int*, int);
void makeNode(struct BST*, int*);
void printTree(struct BST*);

int main()
{
    int arr[100] = {6,5,3,7,9,4,1,10};
    struct BST* root = (struct BST*) malloc(sizeof(struct BST));
    root->info = arr[0];
    root->left = root->right = NULL;
    
    createTree(root, arr, 7);
    printTree(root);
    return 0;
}

void createTree(struct BST* root, int* arr_ref, int arr_len)
{
    struct BST* temproot = root;
    
    while(arr_len > 0)
    {
        arr_ref++;
        makeNode(temproot, arr_ref);
        arr_len--;
    }
}

void makeNode(struct BST* root, int* arr_ref)
{
    struct BST* temp = root;
    
        if(temp->info > *arr_ref)
        {
            if(temp->left == NULL)
            {
                struct BST* newnode = (struct BST*) malloc(sizeof(struct BST));
                newnode->info = *arr_ref;
                newnode->left = newnode->right = NULL;
                temp->left = newnode;
            }
            else
                makeNode(temp->left, arr_ref);
        }
        else if(temp->info <= *arr_ref)
        {
            if(temp->right == NULL)
            {
                struct BST* newnode = (struct BST*) malloc(sizeof(struct BST));
                newnode->info = *arr_ref;
                newnode->left = newnode->right = NULL;
                temp->right = newnode;
            }
            else
                makeNode(temp->right, arr_ref);
        }
}

void printTree(struct BST* root)
{
    struct BST* temp = root;
    
    if(temp == NULL)
        return;
    else
    {
        printTree(temp->left);
        printf(" %d ",temp->info);
        printTree(temp->right);
    }
}