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>
#ifndef NULL
#define NULL 0
#endif
typedef struct tagBSTNode {
int nValue;
tagBSTNode *pLeft;
tagBSTNode *pRight;
} BSTNode;
BSTNode *CreateNode(int nValue) {
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);
}
int CompareNodes(BSTNode *pNode1, BSTNode *pNode2) {
if (pNode1->nValue < pNode2->nValue) {
return -1;
} else if (pNode1->nValue > pNode2->nValue) {
return 1;
} else {
return 0;
}
}
int CompareNode(BSTNode *pNode, int nValue) {
if (pNode->nValue > nValue) {
return -1;
} else if (pNode->nValue < nValue) {
return 1;
} else {
return 0;
}
}
BSTNode *InsertNode(BSTNode *pHead, BSTNode *pNew) {
if (pHead == NULL) {
return pNew;
}
if (CompareNodes(pNew, pHead) < 0) {
if (pHead->pLeft == NULL) {
pHead->pLeft = pNew;
} else {
pHead->pLeft = InsertNode(pHead->pLeft, pNew);
}
return pHead;
} else {
if (pHead->pRight == NULL) {
pHead->pRight = pNew;
} else {
pHead->pRight = InsertNode(pHead->pRight, pNew);
}
return pHead;
}
}
void PrintTreePreOrder(BSTNode *pHead) {
printf("%d ", pHead->nValue);
if (pHead->pLeft != NULL) {
PrintTreePreOrder(pHead->pLeft);
}
if (pHead->pRight != NULL) {
PrintTreePreOrder(pHead->pRight);
}
}
void PrintTreeInOrder(BSTNode *pHead) {
if (pHead->pLeft != NULL) {
PrintTreeInOrder(pHead->pLeft);
}
printf("%d ", pHead->nValue);
if (pHead->pRight != NULL) {
PrintTreeInOrder(pHead->pRight);
}
}
void PrintTreePostOrder(BSTNode *pHead) {
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;
}
int nCmp = CompareNode(pHead, nValue);
if (nCmp == 0) {
return pHead;
} else if (nCmp < 0) {
return SearchTree(pHead->pLeft, nValue);
} else {
return SearchTree(pHead->pRight, nValue);
}
}
int main() {
BSTNode *pBST = NULL;
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");
}
}
DestroyTree(pBST);
return 0;
}