I do not know much c++. What I am trying to do is create a Bst.h, Bst.cpp and main.cpp file. The program works correctly if all are placed in a single file. But once i place them in separate file, main.cpp starts giving errors like ..\Temp\ccK88Dum.o main.cpp:(.text+0x22a): undefined reference to `Bst::insertNode(int)' I am using Dev C++ to compile.
bst.h file:
#ifndef BLAH_H
#define BLAH_H
#pragma once
//Stores nodes of the tree
class Node
{
public:
Node *parent, *left, *right;
int key;
Node();
};
class BinaryTree{
protected:
Node *root;
public:
BinaryTree();
};
class Bst :public BinaryTree{
private:
// Pointer root will hold the location of the root node.
//Traversal in preOrder
void preOrder(Node *current);
//Traversal in postOrder
void postOrder(Node *current);
//Traversal in pinOrder
void inOrder(Node *current);
//Search for the memory location of a node
Node* findMeomoryLoc(Node* current, int value);
//Finds a value is present
bool search(Node* current, int value);
//Display leaf Nodes
int findLeafNodes(Node *current);
int maxOfTree(Node* current);//can find maximum of a sumtree.
int minOfTree(Node* current);//Can find minimum of a subtree.
int countNodes(Node* current);//Can count noddes of a subtree.
int countLeaves(Node* current);
int internalNodes(Node* current);
int findTreeHeight(Node *current);
int branchOfHeightK(Node* current,int height,int maxHeight);
int BranchHeightLessK(Node* current,int height,int maxHeight);
public:
//Constructor initializes root to NULL
Bst();
//find successor of a node
int successor(int value);
//finds successor
int predecessor(int value);
//Insertation of node
void insertNode(int value);
int deleteNode(int value);
//Traversal methods
void prOrder();
void poOrder();
void inOrder();
//get Memory location of a Searched Node
Node* getMemoryLocation(int value);
//Search a value in tree
bool find(int value);
//Displays leaves
int findleaves();
//Counts Leaves
int countAllLeaves();
//Maxium of BST
int maximumOfBST();
//Minimum of BST
int minimumOfBST();
//Count Total No. of Nodes
int countAllNodes();
//Find Internal Nodes
int allInternalNodes();
//Get Height of a tree
int treeHeight();
int branchOfHeightK(int value);
int branchHeightLessK(int value);
};
#endif
My Bst.cpp:
#include <iostream>
#include "Bst.h"
using namespace std;
//Stores nodes of the tree
Node::Node()
{
parent = left = right = NULL;
}
BinaryTree::BinaryTree()
{
root=NULL;
}
Bst::Bst()
{
root = NULL;
}
void Bst::prOrder()
{
preOrder(root);
}
void Bst::poOrder()
{
postOrder(root);
}
void Bst::inOrder()
{
inOrder(root);
}
//get Memory location of a Searched Node
Node* Bst::getMemoryLocation(int value)
{
return findMeomoryLoc(root, value);
}
//Search a value in tree
bool Bst::find(int value)
{
return search(root, value);
}
//Displays leaves
int Bst::findleaves()
{
return findLeafNodes(root);
}
//Counts Leaves
int Bst::countAllLeaves()
{
return countLeaves(root);
}
//Maxium of BST
int Bst::maximumOfBST()
{
return maxOfTree(root);
}
//Minimum of BST
int Bst::minimumOfBST()
{
return minOfTree(root);
}
//Count Total No. of Nodes
int Bst::countAllNodes()
{
return countNodes(root);
}
//Find Internal Nodes
int Bst::allInternalNodes()
{
internalNodes(root);
}
//Get Height of a tree
int Bst::treeHeight()
{
findTreeHeight(root);
}
int Bst::branchOfHeightK(int value)
{
return branchOfHeightK(root,0,value);
}
int Bst::branchHeightLessK(int value)
{
return Bst::BranchHeightLessK(root,0,value);
}
int Bst::successor(int value)
{
Node* current=getMemoryLocation(value); //finds memory Location of the node
if (current==NULL) //if the node doesnot exist
return 0;
if (current->key==maximumOfBST()) //if the node is maximum of the tree then it will have no successor
return 0;
if (current->right!=NULL) //If the node has right child then
return minOfTree(current->right); //minimum to right is successor
if(current->key<current->parent->key)//if node is a left child
{
return current->parent->key;//immediate parent is successor
}
else
{
while(current->key>current->parent->key)//loop to move towards parent until it is a right child.
{
current=current->parent;
}
return current->parent->key;
}
}
int Bst::predecessor(int value)
{
Node* current=getMemoryLocation(value); //finds memory Location of the node
if (current==NULL) //if the node doesnot exist
return 0;
if (current->key==minimumOfBST()) //if the node is minimum of the tree then it will have no predicessor
return 0;
if (current->left!=NULL) //If the node has left child then
return maxOfTree(current->right); //maximum to right is successor
if(current->key>current->parent->key)//if the node is a right child
{
return current->parent->key;//immediate parent is successor
}
else
{
while(current->key<current->parent->key)//loop to move towards parent until it is a left child.
{
current=current->parent;
}
return current->parent->key;
}
}
//Internal Nodes
int Bst::internalNodes(Node* current)
{
if(current==NULL)
return 0;
if(current->parent!=NULL&&(current->right!=NULL||current->left!=NULL))
return 1;
else
return internalNodes(current->left)+internalNodes(current->right);
}
//CountLeaves
int Bst::countLeaves(Node* current)
{
if (current==NULL)
return 0;
if(current->left==NULL && current->right==NULL)
{
return 1;
}
else
return (countLeaves(current->left)+countLeaves(current->right));
}
//No of branches of height k
int Bst::branchOfHeightK(Node* current,int height,int maxHeight)
{
if (current==NULL)
return 0;
if(current->left==NULL && current->right==NULL&&height==maxHeight)
{
return 1;
}
else
return (branchOfHeightK(current->left,height+1,maxHeight)+branchOfHeightK(current->right,height+1,maxHeight));
}
//Branches with height less than k
int Bst::BranchHeightLessK(Node* current,int height,int maxHeight)
{
if (current==NULL)
return 0;
if(current->left==NULL && current->right==NULL&&height<maxHeight)
{
return 1;
}
else
return (BranchHeightLessK(current->left,height+1,maxHeight)+BranchHeightLessK(current->right,height+1,maxHeight));
}
//Height of a Tree
int Bst::findTreeHeight(Node *current)
{
if(current==NULL)
return -1;
return 1+ max(findTreeHeight(current->right),findTreeHeight(current->left));
}
//Count the number of nodes
int Bst::countNodes(Node* current)
{ if(current==NULL)
return 0;
else{
return (countNodes(current->left)+countNodes(current->right)+1);
}
}
//Find node with maximum value.
int Bst::maxOfTree(Node* current)
{
if (current!=NULL) //If root is not NuLL
{
while(current->right!=NULL)
{
current=current->right;
}
return current->key;
}
}
//Find minimum of a tree
int Bst::minOfTree(Node* current)
{
if (current!=NULL)
{
while(current->left!=NULL)
{
current=current->left;
}
return current->key;
}
}
//Displays the leaves of the BST
int Bst::findLeafNodes(Node *current) {
if (current == NULL)
return 0;
if (current->left == NULL && current->right == NULL)
{
cout << current->key << ", ";
return 0;
}
findLeafNodes(current->left);
findLeafNodes(current->right);
}
void Bst::insertNode(int value)
{
//A new node pointed by temp is created which stores the value to be inserted.
Node *temp = new Node();
temp->key = value;
//We take a pointer current which points to the root of tree initially.
//parent is used to indicate the parent of current node.
Node *current = root, *parent = NULL;
//If current is Null then there is no Bst and new node will form the root of the tree.
//If it is not null then it has child and current becomes the child.
while (current != NULL)
{
//Parent is assigned the current position and current goes to the child
parent = current;
if (value < current->key)
{
current = current->left;
}
else
{
current = current->right;
}
}
//Now we check if parent of current is NULL then currnt node is at root
if (parent == NULL)
{
root = temp;//temp was used to store the insertion value. Now root points to it.
}
else if (value < parent->key)
{
parent->left = temp;
}
else
{
parent->right = temp;
}
temp->parent = parent;
}
int Bst:: deleteNode(int value)
{
/* Node* x=NULL;
Node* y=NULL;
Node* node=getMemoryLocation(value);//gets the pointer to the node to be deleted
if(node==NULL)//if number does not exist.
return 0;
if(node->left==NULL||node->right==NULL)
y=node;
else
{
y=getMemoryLocation(successor(x->key));
}
if (node->left!=NULL)
x=y->left;
else
x=y->right;
if(x!=NULL)
x->parent=y->parent;
if(y->parent==NULL)//if node to be deleted is root
node=x;
if(y=y->parent->left)
y->parent->left=x;
else
y->parent->right=x;
if(y!=node)
node->key=y->key;
delete y;*/
Node *y=NULL;
Node* node=getMemoryLocation(value);
if (node == NULL) //if node does not exist
return 0;
//if root has no child
if (node->left == NULL && node->right == NULL)
{
if(node->parent==NULL)//if it is the root node
{
root=NULL;
}
else//if not a root node
{
//parent should point to null
if(node==node->parent->right)
node->parent->right=NULL;
else//if it is the left child
node->parent->left=NULL;
}
delete node;
return 1;
}
//if node has 2 child
if(node->left!=NULL&&node->right!=NULL)
{
y=getMemoryLocation(successor(node->key));
node->key=y->key;
if(y==y->parent->right) //replaced node's parent should point to null
y->parent->right=NULL;
else
y->parent->left=NULL;
delete y;//we delete the node that replaces the node to be deleted
return 1;
}
//if node has 1 child
if(node->left!=NULL)
{
y=node->left;
y->parent=node->parent;
node->parent->left=y;
}
else
{
y=node->right;
y->parent=node->parent;
node->parent->right=y;
}
delete node;
return 1;
}
//find the memory location of a node
Node* Bst::findMeomoryLoc(Node* current,int value)
{
if (current == NULL || value == current->key)
return current;
if (value < current->key)
findMeomoryLoc(current->left, value);
else
findMeomoryLoc(current->right, value);
}
//find if a node exist
bool Bst::search(Node* current, int value)
{
if(current == NULL)
return false;
while(current!=NULL)
{
if (current->key==value)
return true;
else
{
if(value<current->key)
current=current->left;
else
current=current->right;
}
}
}
void Bst::preOrder(Node *current)
{
if (current == NULL)
return;
cout << current->key << " ";
preOrder(current->left);
preOrder(current->right);
}
void Bst::postOrder(Node *current)
{
if (current == NULL)
return;
postOrder(current->left);
postOrder(current->right);
cout << current->key << " ";
}
void Bst::inOrder(Node *current)
{
if (current == NULL)
return;
inOrder(current->left);
cout << current->key << " ";
inOrder(current->right);
}
main.cpp
#include<iostream>
using namespace std;
#include"Bst.h"
int main()
{
Bst obj;
int choice=-1;
cout<<"\t\tWelcome to Binary Search Program"<<endl;
int value;
while(choice!=0)
{
cout<<"Select:"<<endl<<"\t1. to Insert a new Node.\t2. to delete a node\n\t3. to Traverse nodes\t4. Search a Node\n\t5. to find leaves of the tree\t6. to find Minimum value of the Tree";
cout<<endl<<"\t7. to find Maximum value of the Tree\t8. to find total no of leaves\n\t9. to find no of Branches.\t10. to get the no of branches oh height k.\n\t11. to find branch with height less than k\t12. to find the longest branch.";
cout<<endl<<"\t13. to find Successor of a node\t14. to find the predecessor of a node\n\t15. to find the number internal nodes."<<endl<<"\t0 to QUIT"<<endl;
while(!(cin>>choice))//Validation of Number
{
cout<<"\n\tERROR!! Enter a number. (Symbols and letters not allowed.)\n";
cin.clear();
cin.ignore(123,'\n');
}
switch(choice)
{
case 0:
cout<<"\n\t\tBye. See you again.\n";
break;
case 1:
cout<<"Enter value of node to be inserted\n";
while(!(cin>>value))//Validation of Number
{
cout<<"\n\tERROR!! Enter a number. (Symbols and letters not allowed.)\n";
cin.clear();
cin.ignore(123,'\n');
}
obj.insertNode(value);
break;
case 2:
cout<<"Enter value of node to be deeted\n";
while(!(cin>>value))//Validation of Number
{
cout<<"\n\tERROR!! Enter a number. (Symbols and letters not allowed.)\n";
cin.clear();
cin.ignore(123,'\n');
}
if(obj.deleteNode(value))
{
cout<<"Successfully Deleted\n";
}
else
cout<<"NODE NOT FOUND"<<endl;
break;
case 3:
cout<<"\n\tTraversals:\n"<<"Preorder\n";
obj.prOrder();
cout << endl << "Inorder" << endl;
obj.inOrder();
cout << endl << "Postorder" << endl;
obj.poOrder();
cout<<endl;
break;
case 4:
cout<<"Enter node to search\n";
while(!(cin>>value))//Validation of Number
{
cout<<"\n\tERROR!! Enter a number. (Symbols and letters not allowed.)\n";
cin.clear();
cin.ignore(123,'\n');
}
if(!obj.find(value))
cout<<"Node present\n";
else
cout<<"Node not present\n";
break;
case 5:
cout<<"\nThe leaves have the following values: ";
obj.findleaves();
break;
case 6:
cout<<"Minimum value in the tree: "<<obj.minimumOfBST();
break;
case 7:
cout<<"Maximum value in the tree: "<<obj.maximumOfBST();
break;
case 8:
cout<<"Total no of leaves: "<<obj.countAllLeaves();
break;
case 9: cout<<"Total no of branches: "<<obj.countAllLeaves();
break;
case 10: cout<<"Enter height of branch: "<<endl;
while(!(cin>>value))//Validation of Number
{
cout<<"\n\tERROR!! Enter a number. (Symbols and letters not allowed.)\n";
cin.clear();
cin.ignore(123,'\n');
}
cout<<"No of branches of height "<<value<<" is "<<obj.branchOfHeightK(value)<<endl;
break;
case 11:cout<<"Enter maximum allowed height of a branch.\n";
while(!(cin>>value))//Validation of Number
{
cout<<"\n\tERROR!! Enter a number. (Symbols and letters not allowed.)\n";
cin.clear();
cin.ignore(123,'\n');
}
cout<<"Total no of branches of height less than "<<value<<"is: "<<obj.branchHeightLessK(value)<<endl;
break;
case 12:cout<<"Longest branch of height k "<<"Not done\n";
obj.treeHeight();
break;
case 13:cout<<"Enter value: ";
while(!(cin>>value))//Validation of Number
{
cout<<"\n\tERROR!! Enter a number. (Symbols and letters not allowed.)\n";
cin.clear();
cin.ignore(123,'\n');
}
cout<<obj.successor(value)<<endl;
break;
case 14:
cout<<"Enter value: ";
while(!(cin>>value))//Validation of Number
{
cout<<"\n\tERROR!! Enter a number. (Symbols and letters not allowed.)\n";
cin.clear();
cin.ignore(123,'\n');
}
cout<<obj.predecessor(value)<<endl;
break;
case 15:
cout<<"The No. of internal nodes is: "<<obj.allInternalNodes()<<endl;
}
}
}
