Hi,have slight problem,my delete function does not work in avl tree:
#include "stdafx.h"
#include "TreeType.h"
using namespace std;
// menu helpers
int ShowMenu(void);
template<class T>
void ProcessMenu(TreeType<T>& tree);
// callbacks
template<class T>
void InsertItem(TreeType<T>& tree);
template<class T>
void DeleteItem(TreeType<T>& tree);
template<class T>
void PrintTree(TreeType<T>& tree);
int _tmain(int argc, _TCHAR* argv[])
{
typedef TreeType<int> tree_type;
tree_type tree;
ProcessMenu(tree);
return 0;
}
int ShowMenu(void)
{
int option;
cout << "\n\t" << endl;
cout << "\t\t===============================" << endl;
cout << "\t\t1. Insert into tree" << endl;
cout << "\t\t2. Print tree" << endl;
cout << "\t\t3. Delete tree" << endl;
cout << "\t\t4. Quit" << endl;
cout << "\t\t===============================" << endl;
cout << endl;
cout << "Choose an option: ";
cin >> option;
return option;
}//ShowMenu
template<class T>
void ProcessMenu(TreeType<T>& tree)
{
bool quit = false;
do {
switch (ShowMenu())
{
case 1:
InsertItem(tree);
break;
case 2:
PrintTree(tree);
break;
case 3:
DeleteItem(tree);
break;
case 4:
quit = true;
break;
default:
cout << "Error: Invalid option. Try again." << endl;
}//switch
} while (!quit);
}//ProcessMenu
template<class T>
void InsertItem(TreeType<T>& tree)
{
cout << "Enter number: ";
int num;
cin >> num;
tree.InsertItem(num);
cout << "Number inserted:" << num;
}
template<class T>
void PrintTree(TreeType<T>& tree)
{
tree.PrintTree();
}
template<class T>
void DeleteItem(TreeType<T>& tree)
{
cout << "Enter number: ";
int num;
cin >> num;
tree.DeleteItem(num);
}
Have .h file and .cpp ok:
template <class ItemType>
void TreeType<ItemType> ::DeleteItem(ItemType item)
{
bool shorter;
Delete(root, item, shorter);
}
template <class ItemType>
void Delete(TreeNode<ItemType>*& tree, ItemType item, bool & shorter)
// Deletes item from tree.
// Post: item is not in tree.
{
if (tree != NULL)
{
if (item < tree->info)
{
Delete(tree->left, item, shorter);
// Look in left subtree.
if (shorter)
switch (tree->bf)
{
case LH: tree->bf = EH; break;
case EH: tree->bf = RH; shorter = false;
break;
case RH: DelRightBalance(tree, shorter);
}
}
else if (item > tree->info)
{
Delete(tree->right, item, shorter);
// Look in right subtree.
if (shorter)
switch (tree->bf)
{
case LH: DelLeftBalance(tree, shorter);
break;
case EH: tree->bf = LH; shorter = false;
break;
case RH: tree->bf = EH; break;
}
}
else
DeleteNode(tree, shorter);
// Node found; call DeleteNode.
}
else
{
cout << "\nNOTE: " << item << " not in the tree so cannot be deleted.";
}
}