Purpose:
Managing a Binary Search Tree in C using struct(s).Explanation:
Struct:
A struct is the near equivalent of an object in other object oriented programming languages. However C is not an OOP language a struct helps with at least the organization and encapsulation of data.
Pointer:
A pointer is a variable whose values are memory addresses. So a pointer points to a variable that has the value you may want to use. In other words a pointer indirectly references a value. Accessing a variable through a pointer is called indirection. When you declare a pointer the template would be <type> *<variableName>; .
The * is also used as the indirection operator or dereferencing operator. When the * is used in the following statement:
printf("%d" , *variablePointer);
would print the actual value that the pointer points to.
This is called dereferencing a pointer.
The & is also used when passing a variable to another function that has a pointer as it's parameter. When doing this in C one needs to pass the address of the variable in order to modify it's value:
doSomething( &variable);
Files: Since there are not classes in C, I have used only 1 "file."
#include <stdio.h>
#include <stdlib.h>
//Struct "object"
struct treeNode{
struct treeNode *leftPtr;
int data;
struct treeNode *rightPtr;
};
//Typedefs
typedef struct treeNode TreeNode;
typedef TreeNode *TreeNodePtr;
//Prototypes
void addNode(TreeNodePtr *treePtr, int value);
void inOrder(TreeNodePtr treePtr);
void preOrder(TreeNodePtr treePtr);
void postOrder(TreeNodePtr treePtr);
void removeNode(TreeNodePtr *treePtr, int value);
TreeNodePtr removeAll(TreeNodePtr treePtr);
int main(void){
//Local variables
TreeNodePtr rootPtr = NULL;
char choice = ' ';
char dontQuit = 1;
int order = 0;
int addN = 0;
int remN = 0;
char yayNay;
puts("Commands for managing a binary tree\nn - create a new binary tree\na - add a node to the tree\nr - remove a node\nt - traverse the tree\n\t1 - pre-order\n\t2 - in-order\n\t3 - post-order\nq - quit");
while(dontQuit == 1){
printf("%7s" ,"Enter: ");
scanf("%1s", &choice);
switch(choice){
case 'n': //new tree
if(rootPtr != NULL){
printf("Create a new tree? y or n: ");
scanf("%1s" , &yayNay);
if(yayNay == 'y'){
rootPtr = removeAll(rootPtr);
}
if(yayNay == 'n'){
break;
}
}
break;
case 'a': //Add
printf("%s", "Value to add: ");
scanf("%3d" , &addN);
addNode(&rootPtr, addN);
break;
case'r': //remove
printf("%s", "Value to remove: ");
scanf("%3d" , &remN);
removeNode(&rootPtr, remN);
break;
case 't'://traverse
printf("%23s" , "Pick type of traverse: ");
scanf("%d", &order);
if(order == 1){
//call pre-order function
preOrder(rootPtr);
printf("\n");
break;
}
if(order == 2){
//call in order function
inOrder(rootPtr);
printf("\n");
break;
}
if(order == 3){
//call post order function
postOrder(rootPtr);
printf("\n");
break;
}
else{
puts("Invalid entry. Enter 1, 2, or 3 only.");
break;
}
case 'q'://quit
dontQuit = 0;
exit(0);
}//switch
}
return 0;
}//end function main
void addNode(TreeNodePtr *treePtr, int value){
//if tree is empty
if(*treePtr == NULL){
*treePtr = malloc(sizeof(TreeNode));
if(*treePtr !=NULL){
(*treePtr)->data = value;
(*treePtr)->leftPtr = NULL;
(*treePtr)->rightPtr = NULL;
printf("%d added\n", value);
}
else{
printf( "%d not inserted. No memory available.\n" , value);
}
}//end if
else{ //tree is not empty
//data to insert is less than data in current node
if(value < (*treePtr )->data){
addNode( &( (*treePtr)->leftPtr), value);
}
else if(value > (*treePtr )->data){
addNode( &( (*treePtr)->rightPtr), value);
}
else{ //Duplicate data value is ignored
printf( "%s", "duplicate\n");
}
}//end else
}//end function addNode
void inOrder(TreeNodePtr treePtr){
if(treePtr != NULL){
inOrder(treePtr->leftPtr);
printf("%3d" , treePtr->data);
inOrder(treePtr->rightPtr);
}
}//end function inOrder
void preOrder(TreeNodePtr treePtr){
if(treePtr != NULL){
printf("%3d" , treePtr->data);
preOrder(treePtr->leftPtr);
preOrder(treePtr->rightPtr);
}
}//end function preOrder
void postOrder(TreeNodePtr treePtr){
if(treePtr != NULL){
postOrder(treePtr->leftPtr);
postOrder(treePtr->rightPtr);
printf("%3d" , treePtr->data);
}
}//end function postOrder
/*Function Remove is called when the user wants
* to delete one value.
**/
void removeNode(TreeNodePtr *treePtr, int value) {
TreeNodePtr current = *treePtr,parentTreePtr,tempTreePtr;
if (!current){
printf("Tree empty.\n");
return;
}
if(current->data == value){
if(!current->rightPtr && !current->leftPtr){
*treePtr = NULL;
free(current);
}
else if (!current->rightPtr) {
*treePtr = current->leftPtr;
free(current);
}else {
tempTreePtr = current->rightPtr;
if(!tempTreePtr->leftPtr){
tempTreePtr->leftPtr = current->leftPtr;
}else{
while (tempTreePtr->leftPtr) {
parentTreePtr = tempTreePtr;
tempTreePtr = tempTreePtr->leftPtr;
}
parentTreePtr->leftPtr = tempTreePtr->rightPtr;
tempTreePtr->leftPtr = current->leftPtr;
tempTreePtr->rightPtr = current->rightPtr;
}
*treePtr =tempTreePtr;
free(current);
}
}//end if
else if(value > current->data){
removeNode(&(current->rightPtr), value);
}
else if(value < current->data){
removeNode(&(current->leftPtr), value);
}
}//end function removeNode
/*Function RemoveAll is called when the user wants
* to start over.
**/
TreeNodePtr removeAll(TreeNodePtr treePtr){
if(treePtr != NULL){
removeAll(treePtr->leftPtr);
removeAll(treePtr->rightPtr);
treePtr = NULL;
}
return treePtr;
}//end function removeALL
No comments:
Post a Comment