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:
- 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
- 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
- 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);
}
}
