Click here to Skip to main content
15,921,174 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more:
Hi friends I am having problem while coding a c language program for operations as insert, preorders, inorders, postorders ,deletion and searching of nodes in a binary search tree. I have search net but programs that I found has tree.h or windows.h header files which does not open in my Turbo C software. Please if anyone can provide me this code would be great. Actual problem is coming for preorders and postorders also deletion of node than whole tree.
Posted
Updated 21-Feb-11 3:29am
v2

1 solution

I wrote up a quick tree implementation in Visual C, but it should work in Turbo C as well.
Because it was quick, it isn't perfect. Search will have trouble finding all nodes if there are more than 1 with the same value, and I will leave delete for you to implement.

Also, this code was not well tested, you should check the accuracy of the results.

In addition to your requirements, you may also wish to implement a Balance() method to balance the tree, otherwise in extreme circumstance it can end up as a linked list with a bigger memory footprint.

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>

//I don't know if Turbo C has NULL defined
#ifndef NULL
	#define NULL 0
#endif

typedef struct tagBSTNode {
	int nValue; //This could be a struct or whatever other data type you are using as the nodes
	tagBSTNode *pLeft; //The left child node for elements that are less than this element
	tagBSTNode *pRight; //The right child node for elements that are greater than or equal to this node
} BSTNode;

BSTNode *CreateNode(int nValue) { //The parameter here would be whatever data type the node is representing
	BSTNode *pNode = (BSTNode *)malloc(sizeof(BSTNode));
	if (pNode == NULL) {
		puts("Out of memory.");
		exit(-1);
	}
	pNode->nValue = nValue;
	pNode->pLeft = NULL;
	pNode->pRight = NULL;
	return pNode;
}

void DestroyNode(BSTNode *pNode) {
	if (pNode != NULL) {
		free(pNode);
	}
}

void DestroyTree(BSTNode *pHead) {
	if (pHead->pLeft != NULL) {
		DestroyTree(pHead->pLeft);
	}
	if (pHead->pRight != NULL) {
		DestroyTree(pHead->pRight);
	}
	DestroyNode(pHead);
}

//This function compares 2 BSTNodes and returns their relationship in terms of sorted order:
// <0 if pNode1 < pNode2
// =0 if pNode1 == pNode2
// >0 if pNode1 > pNode2
int CompareNodes(BSTNode *pNode1, BSTNode *pNode2) {
	if (pNode1->nValue < pNode2->nValue) {
		return -1;
	} else if (pNode1->nValue > pNode2->nValue) {
		return 1;
	} else {
		return 0;
	}
}

//This function compares a BSTNode and an int and returns the relationship in terms of sorted order:
// <0 if pNode > nValue
// =0 if pNode == nValue
// >0 if pNode < nValue
int CompareNode(BSTNode *pNode, int nValue) {
	if (pNode->nValue > nValue) {
		return -1;
	} else if (pNode->nValue < nValue) {
		return 1;
	} else {
		return 0;
	}
}

//Returns the new head of (sub)tree. In most cases this will be the same value as pHead.
BSTNode *InsertNode(BSTNode *pHead, BSTNode *pNew) {
	if (pHead == NULL) { //The tree is empty.
		return pNew; //This is now the head element in the tree
	}
	if (CompareNodes(pNew, pHead) < 0) { //pNew needs to go to the left
		if (pHead->pLeft == NULL) { //There are no child nodes on the left. Set it and return the head.
			pHead->pLeft = pNew;
		} else {
			pHead->pLeft = InsertNode(pHead->pLeft, pNew); //Recurse through the tree untill we find an empty child node
		}
		return pHead; //Return the head element
	} else { //pNew needs to go to the right
		//This could also be that pNew == pHead. It is up to you which side it goes, I chose right (greater than)
		if (pHead->pRight == NULL) { //There are no child nodes on the right. Set it and return the head.
			pHead->pRight = pNew;
		} else {
			pHead->pRight = InsertNode(pHead->pRight, pNew); //Recurse through the tree untill we find an empty child node
		}
		return pHead; //Return the head element
	}
}

void PrintTreePreOrder(BSTNode *pHead) {
	//Iterates the tree in pre-order and prints each element
	//Hopefully you can see how to do pre-order and post-order
	printf("%d ", pHead->nValue);
	if (pHead->pLeft != NULL) {
		PrintTreePreOrder(pHead->pLeft);
	}
	if (pHead->pRight != NULL) {
		PrintTreePreOrder(pHead->pRight);
	}
}

void PrintTreeInOrder(BSTNode *pHead) {
	//Iterates the tree in order and prints each element
	if (pHead->pLeft != NULL) {
		PrintTreeInOrder(pHead->pLeft);
	}
	printf("%d ", pHead->nValue);
	if (pHead->pRight != NULL) {
		PrintTreeInOrder(pHead->pRight);
	}
}

void PrintTreePostOrder(BSTNode *pHead) {
	//Iterates the tree in post-order and prints each element
	if (pHead->pLeft != NULL) {
		PrintTreePostOrder(pHead->pLeft);
	}
	if (pHead->pRight != NULL) {
		PrintTreePostOrder(pHead->pRight);
	}
	printf("%d ", pHead->nValue);
}

BSTNode *SearchTree(BSTNode *pHead, int nValue) {
	if (pHead == NULL) {
		return NULL; //Element not found
	}
	int nCmp = CompareNode(pHead, nValue);
	if (nCmp == 0) {
		return pHead; //This is the element we are looking for
	} else if (nCmp < 0) {
		return SearchTree(pHead->pLeft, nValue);
	} else { //if (nCmp > 0)
		return SearchTree(pHead->pRight, nValue);
	}
}

int main() {
	BSTNode *pBST = NULL;
	//This will build a sample tree from the following values
	int nSampleValues[] = { 5, 1, 8, 0, 2, 3 };
	int nSearchValues[] = { 3, 1, 7 };
	int nValue;
	for (nValue = 0; nValue < sizeof(nSampleValues) / sizeof(nSampleValues[0]); ++nValue) {
		pBST = InsertNode(pBST, CreateNode(nSampleValues[nValue]));
	}
	printf(" Pre-order: ");
	PrintTreePreOrder(pBST);
	printf("\n");
	printf("  In-order: ");
	PrintTreeInOrder(pBST);
	printf("\n");
	printf("Post-order: ");
	PrintTreePostOrder(pBST);
	printf("\n");
	for (nValue = 0; nValue < sizeof(nSearchValues) / sizeof(nSearchValues[0]); ++nValue) {
		printf("Searching for %d: ", nSearchValues[nValue]);
		if (SearchTree(pBST, nSearchValues[nValue]) == NULL) {
			printf("Not Found\n");
		} else {
			printf("Found\n");
		}
	}
	//Cleanup the memory used
	DestroyTree(pBST);
	return 0;
}
 
Share this answer
 
Comments
Archit9373284448 22-Feb-11 2:34am    
:) ya ya... This is it.... :)

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900