binary tree code complete
This code runs on devc++. I made this codes because this is a requirements of our teacher in our subject Data Structure.
#include <iostream>
#include <conio.h>
using namespace std;
struct node
{
int num;
node *lLink;
node *rLink;
};
void createNode(node *&root);
void connectNode(node *newNode,node *current);
void preOrder(node *current);
void inOrder(node *current);
void postOrder(node *current);
void smallestNumber(node *current);
void biggestNumber(node *current);
void menu(int& choice);
void searchNode(int num,node* searchNode,node* parentNode);
void deleteNode(node* dNode);
void deleteNodeWithNoChild(node* dNode,node* pNode);
void deleteNodeWithOneChild(node* dNode,node* pNode);
void deleteNodeWithTwoChildren(node* dNode,node* pNode);
bool found; //control for searching a node
node* gSNode; //global variable for search node
node* gPNode; //global variable for parent node
node* gSmallestNode; //global variable for the smallest node
node* gBiggestNode; //global variable for the biggest node
main()
{
int choice;
int num;
node *root; //root of the tree
node *parent;
node *current;
node *sNode;
node *temp; //used in deleting a node
root = NULL;
do
{
menu(choice);
switch(choice)
{
case 1:
createNode(root);
getch();
break;
case 2:
cout<<"Pre-order Traversal"<<endl<<endl;
preOrder(root);
getch();
break;
case 3:
cout<<"In-order Traversal"<<endl<<endl;
inOrder(root);
getch();
break;
case 4:
cout<<"Post-order Traversal"<<endl<<endl;
postOrder(root);
getch();
break;
case 5:
cout<<"Smallest Number"<<endl<<endl;
smallestNumber(root);
cout<<"The smallest number in the tree is "<<gSmallestNode->num;
getch();
break;
case 6:
cout<<"Biggest Number"<<endl<<endl;
biggestNumber(root);
cout<<"The biggest number in the tree is "<<gBiggestNode->num;
getch();
break;
case 7:
cout<<"Enter a number to be search:";
cin>>num;
found=false;
searchNode(num,root,root);
if(found==true)
{
if(gSNode==root)
cout<<gSNode->num <<" is the root of the tree.";
else
cout <<"Node Search is "<<gSNode->num<<" and the parent is "
<<gPNode->num;
}
else cout<<"The number was not on the tree.";
getch();
break;
case 8:
if(root==NULL) cout<<"There is no tree.";
else
{
cout<<"Enter a number to be deleted:";
cin>>num;
found=false;
searchNode(num,root,root);
if(found==true)
{
if(gSNode==root && root->lLink==NULL && root->rLink==NULL)
{
root=NULL;
}
else if(gSNode==root && root->lLink!=NULL && root->rLink==NULL)
{
temp=root;
root=root->lLink;
delete temp;
}
else if(gSNode==root && root->lLink==NULL && root->rLink!=NULL)
{
temp=root;
root=root->rLink;
delete temp;
}
else
{
if(gSNode->lLink!=NULL || gSNode->rLink!=NULL) //if the search
deleteNodeWithTwoChildren(gSNode,root); //node has two child
else deleteNode(gSNode);
}
cout<<endl<<endl
<<num<<" was successfully deleted.";
}
else cout<<"The number was not on the tree.";
}
getch();
break;
}
}while(choice!=24);
}
void menu(int& choice)
{
system("cls");
cout<<"[1] Add New Node"<<endl
<<"[2] Display "<<endl
<<"[3] Inorder Traversal"<<endl
<<"[4] Postorder Traversal"<<endl
<<"[5] Smallest Number"<<endl
<<"[6] Biggest Number"<<endl
<<"[7] Search Number"<<endl
<<"[8] Delete Number"<<endl
<<"[24] Exit"<<endl;
cout<<"Enter your choice:";
cin>>choice;
}
void createNode(node* &root)
{
node *newNode;
int num;
newNode=new node;
newNode->lLink=NULL;
newNode->rLink=NULL;
cout<<"Enter number:";
cin>>num;
newNode->num=num;
if(root==NULL){root=newNode;cout<<"root";}
else connectNode(newNode,root);
}
void connectNode(node *newNode,node *current)
{
if(newNode->num > current->num)
{
if(current->rLink!=NULL)
{
cout<<"Move to the right of "<<current->num<<endl;
connectNode(newNode,current->rLink);
}
else
{
current->rLink=newNode;
cout<<newNode->num<<" is connected to the right of "<<current->num<<endl;
}
}
else
{
if(current->lLink!=NULL)
{
cout<<"Move to the left of "<<current->num<<endl;
connectNode(newNode,current->lLink);
}
else
{
current->lLink=newNode;
cout<<newNode->num<<" is connected to the left of "<<current->num<<endl;
}
}
}
void preOrder(node* current)
{
if(current->lLink!=NULL)
cout<<current->num<<" has a left child of "<<current->lLink->num<<endl;
else cout<<current->num<<" has no left child."<<endl;
if(current->rLink!=NULL)
cout<<current->num<<" has a right child of "<<current->rLink->num<<endl;
else cout<<current->num<<" has no right child."<<endl;
//cout<<current->num <<" ";
if(current->lLink!=NULL)preOrder(current->lLink);
if(current->rLink!=NULL)preOrder(current->rLink);
}
void inOrder(node *current)
{
if(current->lLink!=NULL)inOrder(current->lLink);
cout<<current->num <<" ";
if(current->rLink!=NULL)inOrder(current->rLink);
}
void postOrder(node *current)
{
if(current->lLink!=NULL)postOrder(current->lLink);
if(current->rLink!=NULL)postOrder(current->rLink);
cout<<current->num <<" ";
}
void smallestNumber(node *current)
{
if(current->lLink!=NULL)smallestNumber(current->lLink);
if(current->lLink==NULL)gSmallestNode=current;
}
void biggestNumber(node *current)
{
if(current->rLink!=NULL)biggestNumber(current->rLink);
if(current->rLink==NULL)gBiggestNode=current;
}
void searchNode(int num,node* sNode,node* parentNode)
{
if(sNode->num==num)
{
found=true;
gSNode=sNode;
gPNode=parentNode;
}
if(found==false)
{
if(sNode->lLink!=NULL)searchNode(num,sNode->lLink,sNode);
if(sNode->rLink!=NULL)searchNode(num,sNode->rLink,sNode);
}
}
void deleteNode(node* dNode)
{
if(dNode->lLink==NULL && dNode->rLink==NULL)
{
deleteNodeWithNoChild(gSNode,gPNode);
}
else if(dNode->lLink!=NULL && dNode->rLink==NULL || dNode->lLink==NULL && dNode->rLink!=NULL)
{
deleteNodeWithOneChild(gSNode,gPNode);
}
}
void deleteNodeWithNoChild(node* dNode,node* pNode)
{
if(dNode->num > pNode->num) pNode->rLink=NULL;
else pNode->lLink=NULL;
delete dNode;
}
void deleteNodeWithOneChild(node* dNode,node* pNode)
{
node *dChild;
if(dNode->lLink!=NULL) dChild=dNode->lLink; //check the child position
else dChild=dNode->rLink;
if(dNode->num > pNode->num) pNode->rLink=dChild; //connect the child to the
else pNode->lLink=dChild; //parent of the node to be deleted.
delete dNode;
}
void deleteNodeWithTwoChildren(node* dNode,node* root)
{
int bNumber;
biggestNumber(dNode->lLink); //search the biggest number of the left branch
bNumber=gBiggestNode->num; //store the biggest number of left branch to bNumber variable
found=false; //seach the biggest number of the left branch to find
searchNode(bNumber,root,root); //the parent node
deleteNode(gSNode); //delete the biggest node of the left branch.
dNode->num=bNumber; //replace the value of the original node to be deleted to
//the value of the largest number of the left branch
}
