How would i fix the search function?
AVL.h:
#pragma once
#include<iostream>
#include<stdio.h>
using namespace std;
template<class T>
struct TreeNode;
template<class T>
class AVLType
{
public:
AVLType();
void InsertItem(T item);
void Insert(TreeNode<T>*& tree, T item, bool & taller);
void RotateLeft(TreeNode<T>*& tree);
void RotateRight(TreeNode<T>*& tree);
void RightBalance(TreeNode<T> *& tree, bool & taller);
void LeftBalance(TreeNode<T> *& tree, bool & taller);
void PrintTreeInOrder();
void PrintOrdered(TreeNode<T>* tree);
void InOrderPrint(TreeNode<T>* tree);
void PrintTreePreOrder();
void PrintPreOrdered(TreeNode<T>* tree);
void PreOrderPrint(TreeNode<T>* tree);
void RetrieveItem(T& item, bool& found);
void Retrieve(TreeNode<T>* tree, T& item, bool& found);
private:
TreeNode<T>* root;
};
enum Balancefactor {LH, EH, RH};
template<class T>
void AVLType<T>::Retrieve(TreeNode<T>* tree, T& item, bool& found)
{
if (tree == nullptr)
found = false;
else if (item < tree->info)
Retrieve(tree->left, item, found);
else if (item > tree->info)
Retrieve(tree->right, item, found);
else
{
item = tree->info;
found = true;
}
}
template<class T>
void AVLType<T>::RetrieveItem(T& item, bool& found)
{
Retrieve(root, item, found);
}
template<class T>
struct TreeNode
{
T info;
Balancefactor bf;
TreeNode<T>* left;
TreeNode<T>* right;
};
template<class T>
AVLType<T>::AVLType()
{
root = nullptr;
}
template <class T>
void AVLType<T>::RotateLeft(TreeNode<T> *& tree)
{
TreeNode<T> * rs;
if (tree == NULL)
cerr << "It is impossible to rotate an empty tree in RotateLeft"<< endl;
else if (tree->right == NULL)
cerr << "It is impossible to make an empty subtree the root in RotateLeft" << endl;
else
{
rs = tree->right;
tree->right = rs->left;
rs->left = tree;
tree = rs;
}
}
template <class T>
void AVLType<T>::RotateRight(TreeNode<T> * & tree)
{
TreeNode<T> * ls;
if (tree == NULL)
cerr << "It is impossible to rotate an empty tree in RotateRight"
<< endl;
else if (tree->left == NULL)
cerr << "It is impossible to make an empty subtree the root in RotateRight" << endl;
else
{
ls = tree->left;
tree->left = ls->right;
ls->right = tree;
tree = ls;
}
}
template <class T>
void AVLType<T>::InsertItem(T item)
// Calls recursive function Insert to insert item into tree.
{
bool taller = false;
Insert(root, item, taller);
}
template <class T>
void AVLType<T>::Insert(TreeNode<T>*& tree, T item, bool & taller)
// Inserts item into tree.
// Post: item is in tree; search property is maintained.
{
if (tree == NULL)
{ // Insertion place found.
tree = new TreeNode<T>;
tree->left = NULL;
tree->right = NULL;
tree->info = item;
tree->bf = EH;
taller = true;
}
else if (item == tree->info)
cerr << "Duplicate key is not allowed in AVL tree." << endl;
else if (item < tree->info)
{
Insert(tree->left, item, taller); // Insert into left subtree
if (taller)
switch (tree->bf)
{
case LH: LeftBalance(tree, taller);
break;
case EH: tree->bf = LH;
break;
case RH: tree->bf = EH;
taller = false;
break;
}
}
else
{
Insert(tree->right, item, taller); // Insert into right subtree
if (taller)
switch (tree->bf)
{
case RH: RightBalance(tree, taller);
break;
case EH: tree->bf = RH;
break;
case LH: tree->bf = EH;
taller = false;
break;
}
}
}
template <class T>
void AVLType<T>::RightBalance(TreeNode<T> *& tree, bool & taller)
{
TreeNode<T> * rs = tree->right;
TreeNode<T> * ls;
switch (rs->bf)
{
case RH: tree->bf = rs->bf = EH;
RotateLeft(tree);
taller = false;
break;
case EH: cerr << "Tree already balanced " << endl;
break;
case LH: ls = rs->left;
switch (ls->bf)
{
case RH: tree->bf = LH;
rs->bf = EH;
break;
case EH: tree->bf = rs->bf = EH;
break;
case LH: tree->bf = EH;
rs->bf = RH;
break;
}
ls->bf = EH;
RotateRight(tree->right);
RotateLeft(tree);
taller = false;
}
}
template <class T>
void AVLType<T>::LeftBalance(TreeNode<T> *& tree, bool & taller)
{
TreeNode<T> * ls = tree->left;
TreeNode<T> * rs;
switch (ls->bf)
{
case LH: tree->bf = ls->bf = EH;
RotateRight(tree);
taller = false;
break;
case EH: cerr << "Tree already balanced " << endl;
break;
case RH: rs = ls->right;
switch (rs->bf)
{
case LH: tree->bf = RH;
ls->bf = EH;
break;
case EH: tree->bf = ls->bf = EH;
break;
case RH: tree->bf = EH;
ls->bf = LH;
break;
}
rs->bf = EH;
RotateLeft(tree->left);
RotateRight(tree);
taller = false;
}
}
template<class T>
void AVLType<T>::PrintTreeInOrder()
// Calls recursive function Print to print items in the tree.
{
InOrderPrint(root);
}
template<class T>
void AVLType<T>::InOrderPrint(TreeNode<T>* tree)
// Prints info member of items in tree in sorted // order on outFile.
{
if (tree != NULL)
{
InOrderPrint(tree->left);
// Print left subtree.
PrintOrdered(tree);
InOrderPrint(tree->right);
// Print right subtree.
}
}
template<class T>
void AVLType<T>::PrintOrdered(TreeNode<T>* tree)
{
cout << tree->info << " BF: ";
switch (tree->bf)
{
case LH:
cout << "Left High" << endl;
break;
case RH:
cout << "Right High" << endl;
break;
case EH:
cout << "Equal High" << endl;
break;
}
if (tree->left != nullptr)
cout << " left child : " << tree->left->info << endl;
if (tree->right != nullptr)
cout << "right child : " << tree->right->info << endl;
if (tree->left == nullptr && tree->right == nullptr)
cout << "This is a Leaf Node." << endl;
cout << endl;
}
template<class T>
void AVLType<T>::PrintTreePreOrder()
{
PreOrderPrint(root);
}
template<class T>
void AVLType<T>::PreOrderPrint(TreeNode<T>* tree)
{
if (tree != NULL)
{
PrintPreOrdered(tree);
PreOrderPrint(tree->left);
PreOrderPrint(tree->right);
}
}
template<class T>
void AVLType<T>::PrintPreOrdered(TreeNode<T>* tree)
{
cout << tree->info << " BF: ";
switch (tree->bf)
{
case LH:
cout << "Left High" << endl;
break;
case RH:
cout << "Right High" << endl;
break;
case EH:
cout << "Equal High" << endl;
break;
}
if (tree->left != nullptr)
cout << " left child : " << tree->left->info << endl;
if (tree->right != nullptr)
cout << " right child : " << tree->right->info << endl;
if (tree->left == nullptr && tree->right == nullptr)
cout << "This is a Leaf Node." << endl;
cout << endl;
}
AVL.cpp
#include "stdafx.h"
#include "AVL.h"
#include <string>
#include <iostream>
struct PersonData;
using namespace std;
int ShowMenu(void);
template<class T>
void ProcessMenu(AVLType<T>& data);
template<class T>
void EnterData(AVLType<T>& data);
template<class T>
void SearchBySurname(AVLType<T>& data);
//template<class T>
//void PrintData(AVLType<T>& data);
int _tmain(int argc, _TCHAR* argv[])
{
AVLType<string> data;
ProcessMenu(data);
return 0;
}
int ShowMenu(void)
{
int option;
cout << "\n\n";
cout << "\tAVL TREE";
cout << "\n\n\n";
cout << "\t1. Insert" << endl;
cout << "\t2. Print Tree Preorder" << endl;
cout << "\t3. Print Tree Inorder" << endl;
cout << "\t4. Search Address by Surname" << endl;
cout << "\t0. Exit" << endl;
cout << "\n";
cout << "\tEnter Option: ";
cin >> option;
system("cls");
return option;
}
template<class T>
void ProcessMenu(AVLType<T>& data)
{
bool quit = false;
do {
switch (ShowMenu())
{
case 1:
EnterData(data);
cout << "\t"; system("PAUSE");
break;
case 2:
data.PrintTreePreOrder();
cout << "\t"; system("PAUSE");
break;
case 3:
data.PrintTreeInOrder();
cout << "\t"; system("PAUSE");
break;
case 4:
SearchBySurname(data);
cout << "\t"; system("PAUSE");
break;
case 0:
quit = true;
break;
default:
cout << "Invalid Entry!";
}
system("cls");
} while (!quit);
}
template<class T>
void SearchBySurname(TreeNode<T>& data)
{
cout << "\nSearch Contact by surname.\n\n" << endl;
cout << "\nEnter surname: ";
string surname;
cin >> surname;
TreeNode<T> itemToSearch(surname);
bool found = false;
data.RetrieveItem(itemToSearch, found);
if (found)
{
cout << "\nDetails are:" << endl;
cout << "\nSurname: " << itemToSearch.surname << endl;
}
else
cout << "\nWord not found.\n" << endl;
}
template<class T>
void EnterData(AVLType<T>& data)
{
string value;
cout << "\n\n";
cout << "\t AVL tree";
cout << "\n\n\n";
cout << "\t(Type quit to terminate)\n\n";
do
{
cout << "\tEnter a Value: ";
cin >> value;
if (value != "quit")
{
data.InsertItem(value);
}
} while (value != "quit");
}
The error is:
1>AVL_cpp.obj : error LNK2019: unresolved external symbol "void __cdecl SearchBySurname<class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> > >(class AVLType<class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> > > &)" (??$SearchBySurname@V?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@@@YAXAAV?$AVLType@V?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@@@@Z) referenced in function "void __cdecl ProcessMenu<class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> > >(class AVLType<class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> > > &)" (??$ProcessMenu@V?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@@@YAXAAV?$AVLType@V?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@@@@Z)
