Tree Order

#include <iostream>
#include <conio.h>
#include <stdlib.h>

using namespace std;

/* The structure of the node used in the tree */
struct NODE{
int val;
struct NODE *left;
struct NODE *right;

};

struct NODE *root = NULL; /* Points to the root node of the tree */
int nodes = 0; /* Stores the number of nodes in the tree */


/****************************** INSERT NODES *****************************/
void insert(int value)
/* Inserts a new node in the binary search tree that contains the value
   passed in the argument. */
{
struct NODE *anode, *parent;
struct NODE *newnode;

parent = NULL; /* used to point to the parent node */
anode = root; /* used to traverse the btree */

while (anode!=NULL) {
parent = anode;
if (value <= anode->val) /* move on to the left or right node */
anode = anode->left; /* depending on the value */
else
anode = anode->right;
}

/* Allocate memory for the new node */
newnode = (struct NODE *) malloc(sizeof(struct NODE));
newnode-> val = value;
newnode-> right = newnode-> left = NULL;

/* Insert the newnode in the tree */

if (parent == NULL)
root = newnode; /* Make the newnode the root node if the tree is
  empty */
else {
if (value <= parent->val)
parent->left = newnode;
else
parent->right = newnode;
}
}


/****************************** FIND A NODES *****************************/
struct NODE *find(int value)
/* Searches the binary search tree for a node containing the value passed
   as argument and returns its address. NULL is returned if node is not
   found */
{
struct NODE *anode;

anode = root; /* used to traverse the tree */

while ((anode!=NULL) && (anode->val!=value))  /* loop while the a leaf */
if (value <= anode->val) /* is not reached and the value to */
anode = anode->left; /* be searched is not found */
else
anode = anode->right;

return anode;
}


/*************************** FIND A NODES POINTER **************************/
struct NODE **findnodeptr(int value)
/* Searches the binary search tree for a node containing the value passed
   as argument and returns the address of the pointer that points to the node.
   The main difference is that this pointer to a pointer of a node makes it
   easier to create functions to delete nodes */
{
struct NODE *node, *parent;

node = root;
parent = NULL;

while ( (node!=NULL) && (node->val!=value) ) {
parent = node;
if (value <= node->val)
node = node->left;
else
node = node->right;
}

if (parent == NULL)
return &root;
else {
if (parent->left == node)
return &parent->left; /* return the address of the pointer */
else
return &parent->right;
}
}


/****************************** DELETE A NODE ******************************/
void deletenode(struct NODE **nodeptr)
/* Deletes a node in the binary search tree. The address of a pointer to that
   node is gien as argument. */
{
struct NODE *node;
struct NODE **tempptr;

node = *nodeptr;

/* If both the left and right node exists then the value of the inorder
  successor of the right node is deleted after storing the value of the
  in the node to be deleted */
if ((node->left != NULL) && (node->right != NULL)) {
tempptr = &node->right;
while ((*tempptr)->left!=NULL)
tempptr = &(*tempptr)->left;
node->val = (*tempptr)->val;
deletenode(tempptr);
} else {
if ((node->left == NULL) && (node->right == NULL))
*nodeptr = NULL; /* If both childs are NULL then ... */
else if (node->right == NULL)
*nodeptr = node->left;
else
*nodeptr = node->right;
free(node);
}
}

/***************************** INORDER TRAVERSAL ***************************/
void shownode_inorder(struct NODE *anode)
{
if (anode!=NULL) {
shownode_inorder(anode->left);
printf("%d ", anode->val);
shownode_inorder(anode->right);
}
}

/**************************** PREORDER TRAVERSAL ***************************/
void shownode_preorder(struct NODE *anode)
{
if (anode!=NULL) {
printf("%d ", anode->val);
shownode_preorder(anode->left);
shownode_preorder(anode->right);
}
}

/**************************** POSTORDER TRAVERSAL **************************/
void shownode_postorder(struct NODE *anode)
{
if (anode!=NULL) {
shownode_postorder(anode->left);
shownode_postorder(anode->right);
printf("%d ", anode->val);
}
}


/******************************---------------****************************/
/****************************** MAIN FUNCTION ****************************/
/******************************---------------****************************/


int main()
{

int ch;  /* Used to store menu option */
int input;
struct NODE **nodeptr;

do {


printf("NODES:%d\n", nodes);

printf("--------------------------------------------\n");
printf("| BINARY SEARCH TREE DEMONSTRATION PROGRAM |\n");
printf("--------------------------------------------\n");
printf("  1. Insert an item\n");
printf("  2. Find an item\n");
printf("  3. Delete an item\n");
printf("  4. Show inorder traversal\n");
printf("  5. Show preorder traversal\n");
printf("  6. Show postorder traversal\n");
printf("  7. Quit\n");
printf(" Enter option (1-8) :");
do {
ch = getch();
} while ((ch<'1') || (ch>'8'));
printf("%c\n", ch);
printf("--------------------------------------------\n");

switch (ch) {
case '1' :
printf("Enter value to insert:");
scanf("%d", &input);
insert(input);
nodes++;
break;
case '2' :
break;
case '3' :
printf("Enter value to delete:");
scanf("%d", &input);
nodeptr=findnodeptr(input);
if (*nodeptr==NULL)
printf("Cannot delete, item not found in the tree.\n");
else {
deletenode(nodeptr);
nodes--;
}
getch();
break;
case '4' :
printf("Inorder traversal result: ");
shownode_inorder(root);
printf("\n");
getch();
break;
case '5' :
printf("Preorder traversal result: ");
shownode_preorder(root);
printf("\n");
getch();
break;
case '6' :
printf("Postorder traversal result: ");
shownode_postorder(root);
printf("\n");
getch();
break;

}
} while (ch!='7');  /* Loops until option 4 (quit) is selected */
printf("Quitting...\n");
return 0;
}