avltreedemo.cpp

Addison-Velski 和 Landis (AVL-Tree s)的二叉树

#include <afx.h>
#include <afxwin.h>
#include <conio.h>
#include <iostream.h>

#include "AVLBaum.h"

// simple class for demo 2
// note: the class should have a default constructor
class CCity : public CObject
{
public:
	CCity(const char* city = NULL);
	virtual ~CCity();

	// note: Compare-Function is const, and takes const reference
	//  as argument (why should a Compare manipulate anything?)
	virtual int Compare(const CCity& other) const;

	CString City;
};

CCity::CCity(const char* city) : City(city)
{
}

CCity::~CCity()
{
}

int CCity::Compare(const CCity& other) const
{
	return City.Compare(other.City);
}

int main()
{
	// Demo 1: AVL-Tree with CString's in it 
	cout << "Demo 1: simple CString-tree" << endl;
	cout << "----------------------------------" << endl << endl;
	// this is the simplest way to create and fill in a tree
	CAVLTree<CString> tree1;
	tree1.Insert(new CString(_T("London")));
	tree1.Insert(new CString(_T("Paris")));
	tree1.Insert(new CString(_T("Moskau")));
	tree1.Insert(new CString(_T("Helsinki")));
	tree1.Insert(new CString(_T("Canberra")));
	tree1.Insert(new CString(_T("Athen")));
	tree1.Insert(new CString(_T("Irkutsk")));
	tree1.Insert(new CString(_T("Paris")));
	tree1.Insert(new CString(_T("Berlin")));
	tree1.Insert(new CString(_T("Hamburg")));
	tree1.Insert(new CString(_T("Mexico")));
	tree1.Insert(new CString(_T("Aden")));
	tree1.Insert(new CString(_T("Rom")));

	// create an iterator and iterate throw all nodes in the tree
	//  for sorted output
	// note: there are no duplicates in the tree, they have never
	//  been inserted (it is a good idea to no insert such items
	//  rather than delete them after sorting
	CAVLTreeIterator<CString> iter1(tree1);
	for (iter1.MoveFirst(); iter1; iter1++)
	{
		// note: GetData() returns CString*
		cout << *(iter1.GetData()) << endl;
	}
	CString str1 = _T("Paris");
	if (tree1.Search(str1))
		cout << _T("\"") << str1 << "\" is in the tree." << endl;
	else
		cout << _T("\"") << str1 << "\" is in not the tree." << endl;
	str1 = _T("Frankfurt");
	if (tree1.Search(str1))
		cout << _T("\"") << str1 << "\" is in the tree." << endl;
	else
		cout << _T("\"") << str1 << "\" is in not the tree." << endl;
	cout << "Press any key to continue" << endl;
	getch();

	// Demo 2: the same, but with user class
	cout << endl << endl << endl;
	cout << "Demo 2: AVL-Tree with user class" << endl;
	cout << "----------------------------------" << endl << endl;
	CAVLTree<CCity> tree2;
	tree2.Insert(new CCity(_T("London")));
	tree2.Insert(new CCity(_T("Paris")));
	tree2.Insert(new CCity(_T("Moskau")));
	tree2.Insert(new CCity(_T("Helsinki")));
	tree2.Insert(new CCity(_T("Canberra")));
	tree2.Insert(new CCity(_T("Athen")));
	tree2.Insert(new CCity(_T("Irkutsk")));
	tree2.Insert(new CCity(_T("Paris")));
	tree2.Insert(new CCity(_T("Berlin")));
	tree2.Insert(new CCity(_T("Hamburg")));
	tree2.Insert(new CCity(_T("Mexico")));
	tree2.Insert(new CCity(_T("Aden")));
	tree2.Insert(new CCity(_T("Rom")));
	// create an iterator and iterate throw all nodes in the tree
	//  for sorted output
	CAVLTreeIterator<CCity> iter2(tree2);
	for (iter2.MoveFirst(); iter2; iter2++)
	{
		// note: GetData() returns CCity*
		cout << iter2.GetData()->City << endl;
	}
	CCity city1(_T("Paris"));
	CCity city2(_T("Frankfurt"));
	if (tree2.Search(city1))
		cout << _T("\"") << city1.City << "\" is in the tree." << endl;
	else
		cout << _T("\"") << city1.City << "\" is in not the tree." << endl;
	if (tree2.Search(city2))
		cout << _T("\"") << city2.City << "\" is in the tree." << endl;
	else
		cout << _T("\"") << city2.City << "\" is in not the tree." << endl;
	cout << "Press any key to continue" << endl;
	getch();

	// Demo 3: insert/delete of strings, user input
	cout << endl << endl << endl;
	cout << "Demo 3: Testing AVL-Trees" << endl;
	cout << "----------------------------------" << endl << endl;
	char c;
	printf(_T("Do you want the computer to test the trees or do you want to do it yourself?\n"));
	printf(_T("Press C for computer or M for men: "));
	c = getche();
	c = toupper(c);
	while (c != 'C' && c != 'M')
	{
		c = getche();
		c = toupper(c);
	}
	printf(_T("\n\n"));
	bool AutoInput = (c=='C');
	CAVLTree<CString> tree3;
	char UserString[255];
	if (AutoInput)
		printf("Press CTRL+C to break\n");
	else
		printf(_T("(I)nsert / (D)elete / (E)xit   "));
	srand( (unsigned)time( NULL ) );
	long counter = 0;
	do 
	{
		counter++;
		char message[255];
		if (tree3.GetRoot() && !tree3.GetRoot()->CheckBalances(message, sizeof(message)-1))
		{
			printf("\nThe Balances are not correct!\n%s\n", message);
			getch();
		}
		if (AutoInput)
		{
			c = 'I';
			if (counter<=1000 && (rand()%5)==0)
				c = 'D';
			if (counter>1000 && (rand()%2)==0)
				c = 'D';
		}
		else
		{
			c = getch();
			c = toupper(c);
		}
		if (c=='I')
		{
			if (AutoInput)
			{
				sprintf(UserString, "%0d", rand()%2000);
				printf("%9ld: %6s", counter, UserString);
			}
			else
			{
				printf("Enter a string to insert: ");
				cin.getline(UserString, sizeof(UserString)-1);
			}
			if (tree3.Insert(new CString(UserString)))
				printf("              Successfully inserted!      %6ld Nodes\n", tree3.NodesInTree());
			else 
				printf("              Item could not be inserted! %6ld Nodes\n", tree3.NodesInTree());
			if (!AutoInput) printf(_T("(I)nsert / (D)elete / (E)xit   "));
		}
		if (c=='D')
		{
			if (AutoInput)
			{
				sprintf(UserString, "%0d", rand()%2000);
				printf("%9ld: %6s", counter, UserString);
			}
			else
			{
				printf("Enter a string to delete: ");
				cin.getline(UserString, sizeof(UserString)-1);
			}
			CString hstr = UserString;
			if (tree3.Delete(&hstr))
				printf("              Successfully deleted!       %6ld Nodes\n", tree3.NodesInTree());
			else 
				printf("              Item could not be deleted!  %6ld Nodes\n", tree3.NodesInTree());
			if (!AutoInput) printf(_T("(I)nsert / (D)elete / (E)xit   "));
		}
	} while (c != 'E');
	cout << "\nPress any key to continue" << endl;
	getch();
	return 0;
}