NEWS: Total Picture Views: 151536 | Total Article Views: 161005 | Top 5 Most Popular Article: 1. Am I Stuck Algorithm with Becker Robot | 2. PickUpThings with Becker Robot | 3. How to read a JSON and work with it | 4. Encrypted Data GUI (Download .Zip) | 5. Create Wall and Things with Becker

Binary Search Tree (BST) C

Description:

In this example I will show you how to create a binary search tree from getting number in a text file.


Example:

5
3
2
1
...

Code:

#include <stdio.h>
#include <string.h>

static int comp = 1; // Setting the comparaison to start at 1

//Creating the tree structure
struct BinTree {
	int data;
	struct BinTree * right, *left;
};

typedef struct BinTree node;

//Inserting the value into the tree.
void insert(node ** tree, int val)
{
	node *temp = NULL;
	if (!(*tree))
	{
		temp = (node *)malloc(sizeof(node));
		temp->left = temp->right = NULL;
		temp->data = val;
		*tree = temp;
		return;
	}

	if (val < (*tree)->data)
	{
		insert(&(*tree)->left, val); //Inserting the value in the tree (Left)
	}
	else if (val >(*tree)->data)
	{
		insert(&(*tree)->right, val); //Inserting the value in the tree (Right)
	}

}

//Creating the array from the number that we are getting from the file
int *createArray(FILE *in){
	static int num[100];
	for (int i = 0; i < 100; i++){
		fscanf(in, "%d", &num[i]); //Scanning the file and putting the value in a array
	}
	return num;
}



//Function to print the tree (If you need to see it)
static int inc = 1; // Adding number beside the tree number
void printPreOrder(node * tree)
{
	if (tree)
	{
		printf("#%d: %d\n", inc++, tree->data); //Printing the value from the tree to the screen
		printPreOrder(tree->left);
		printPreOrder(tree->right);
	}

}

//Function to search in the tree
node* search(node ** tree, int val)
{

	if (!(*tree))
	{
		return NULL;
	}

	if (val < (*tree)->data) //If the value is smaller then go left
	{
		comp++;
		search(&((*tree)->left), val);
	}
	else if (val >(*tree)->data) //If the value is bigger then go right
	{
		comp++;
		search(&((*tree)->right), val);
	}
	else if (val == (*tree)->data) //If the value are the same then return the value
	{

		return *tree;
	}
}

//This method will return the valie in the array if they are the same. Else it will loop until they find it or return 0 if they can't find it
int getValueInArray(int x, int arrayValue[]){
	int inc = 0;
	for (int i = 0; i < 100; i++){
		//printf("x: %d Array Value: %d \n", x, arrayValue[i]);
		if (x == arrayValue[i]){

			return inc;
		}
		inc++;
	}
	return 0;
}

int main(int argc, char *argv[]){
	node *root;
	node *tmp;
	FILE *in = fopen("integers.txt", "r");

	//Getting the value from the file and put it in the array
	int *arrayPointer = createArray(in);

	//Printing the array
	for (int i = 0; i < 100; i++){
		//printf("#%d . %d \n", i, arrayPointer[i]); //Uncomment this line if you want to see the value int he array
	}
	root = NULL;

	//Inserting the value into the tree
	for (int i = 0; i < 100; i++){
		insert(&root, arrayPointer[i]);
	}

	//Value for the second comparaison
	int comp2;


	int input; //input of the user
	printf("Enter a number: ");
	scanf("%d", &input);

	//Searching in the tree for the first comparaison
	tmp = search(&root, input);
	if (tmp){
		printf("Search node=%d | Number of comparaison: %d \n", tmp->data, comp);
	}
	else{
		printf("Data Not found in tree.\n");
	}

	//Searching in the array for the second part
	int inArray = getValueInArray(input, arrayPointer);
	printf("Search node=%d in the array. Number Location: %d\n", input, inArray);

	int givenValue[10] = { 90, 49, 100, 30, 75, 79, 25, 5, 15, 55 };
	int result[10];
	for (int i = 0; i < 10; i++){
		comp = 0;
		tmp = search(&root, givenValue[i]);
		if (tmp){
			result[i] = comp;
			int nodeComp = getValueInArray(givenValue[i], arrayPointer);
			printf("Search node=%d | Location in the Array=%d | Num of comparaison in the tree: %d \n", tmp->data, nodeComp, result[i]);
		}
		else{
			printf("Data Not found in tree.\n");
		}
	}

	//If you want to see the value in the entire tree
	//printf("Pre Order Display\n");
	//printPreOrder(root);

	system("pause");
}

Attachments: None

Tags: BST Binary Search Tree Structure Node Reading Text File Array

Total Views: 875

My name is Jean-Mathieu

I created this website so other people could enjoy finding useful stuff easier. If you have any question do not hesitate to contact me.

jean8mathieuCreated on 03/28/15 and updated on 03/28/15


affiliate_link

Disclosure: We are a website that needs compensation to operate like any other website on the internet.
We may receive consideration for our reviews but we are totally unbiased and do not accept paid reviews or fake reviews claiming to be something they are not.