test.cpp

AVL树的实现代码（包括插入

#include "head.h"
#include <iostream>
using namespace std;

void Test_StepByStep() {
	AVLTree avl;
	cout << "***********AVL Tree***********" << endl
	     << "Commands:" << endl
	     << "S - See whether a value is in the tree or not." << endl
		 << "s - Search the tree for the Nth smallest value." << endl
		 << "I - Insert a value into the AVL Tree." << endl
		 << "D - Delete a value from the AVL Tree." << endl
		 << "T - Traverse the tree in level order." << endl
		 << "E - Exit the program." << endl
		 << "Attention:" << endl
		 << "Integer supported only & The program is not robust..." << endl;
	char command = 'A';
	while (command != 'E') {
		cout << endl << "Command:";
		cin >> command;
		int count = 0;
		switch(command) {
			case 'S': 
				cout << "The value:";
				int val;
				cin >> val;
				if (avl.Search_InOrNot(val)) cout << "Already in." << endl;
				else cout << "Not yet." << endl;
				break;
			case 's':
				cout << "N:";
				int N;
				cin >> N;
				count = 0;
				int result;
				bool mark;
				avl.Search_NthSmallest(N, mark, result, avl.Getroot(), count);
				if (mark) cout << result << endl;
				else cout << "Out of Range." << endl;
				break;
			case 'I':
				cout << "The value:";
				cin >> val;
				avl.AVLInsert(val);
				break;
			case 'D':
				cout << "The value:";
				cin >> val;
				avl.AVLDelete(val);
				break;
			case 'T':
				cout << "val(bal_fac)" << endl; 
				avl.Traverse();
				break;
			case 'E':
				cout << "Byebye!" << endl << endl;
				return;
		}
	}
	return;
}

void Test_WithSetOfData() {
	cout << "***********AVL Tree***********" << endl
		 << "This program will first create an AVL Tree" << endl
		 << "with 100,000 random intergers(using \"Insertion\" operation)," << endl
		 << "and then test the \"Searching\" operation" << endl
		 << "with both an element already in the tree" << endl
		 << "and another newly created random interger." << endl
		 << "At last, the tree will be destructed," << endl
		 << "using \"Deletion\" operation and deleting one element at a time." << endl << endl;
	int seed;
	cout << "Please input the seed:";
	cin >> seed;
	srand(seed);
	AVLTree avl;
	int a[100000];
	cout << endl << "Starting creating the AVL Tree with 100,000 random integers..." << endl;
	for (int i = 0; i < 100000; i++) {
		a[i] = rand();
		avl.AVLInsert(a[i]);
	}
	cout << "Finished!" << endl << endl;
	int temp = rand();
	cout << "The integer " << a[temp%100000] << " is "
		<< (avl.Search_InOrNot(a[temp%100000]) ? "in the tree." : "not in the tree.") << endl;
	cout << "The integer " << temp << " is "
		<< (avl.Search_InOrNot(temp) ? "in the tree." : "not in the tree.") << endl << endl;
	cout << "Starting destructing the AVL Tree..." << endl;
	for (int i = 0; i < 100000; i++) 
		avl.AVLDelete(a[i]);
	avl.Traverse();
	return;
}