Я пытаюсь запрограммировать дерево AVL на c ++. Мой профессор предоставил main.cpp, а также файл для вставки и несколько файлов для удаления, чтобы можно было провести тестирование. Моя программа правильно берет файл вставки и первый из файлов удаления, но не может вернуть результат для остальных файлов удаления. Я не уверен, связано ли это с ошибкой чтения файла, или эти файлы создают случаи, когда у меня не завершается цикл, и т. Д.
Я попытался вставить операторы cout, чтобы отслеживать, куда идет код, ноне получили никаких полезных результатов для отладки. Программа никогда не отображает результаты для 2-го, 3-го или 4-го файла удаления, только для первого. Я также попытался начать с каждого файла удаления на новой версии.
Мой main.cpp (как предусмотрено инструктором) выглядит следующим образом:
#include "utility.h"
#include "Binary_node.h"
#include "Binary_tree.h"
#include "Search_tree.h"
#include "AVL_node.h"
#include "AVL_tree.h"
int main(){
string input = "";
bool exit_now = false;
AVL_tree<int> atree;
while(!exit_now){
cout << endl;
cout << "***********************" << endl;
cout << "Menu:" << endl;
cout << "1. Incremental Insert" << endl;
cout << "2. Insert from File" << endl;
cout << "3. Incremental Delete" << endl;
cout << "4. Delete from File" << endl;
cout << "p. Print tree" << endl;
cout << "x. Exit" << endl;
cout << "***********************" << endl;
getline(cin, input);
if(input == "1"){
cout << endl;
cout << "Enter new integer keys to insert. Enter \"q<Enter>\" to quit." << endl;
cout << endl;
getline(cin, input);
while(input != "q"){
atree.insert(string_to_int(input));
atree.print();
getline(cin, input);
}
}
else if(input == "2"){
cout << endl << "Enter Insertion File Name:" << endl;
getline(cin, input);
ifstream insertion_file;
insertion_file.open(input.c_str());
if(!insertion_file.fail()){
while(!insertion_file.fail() && !insertion_file.eof()){
getline(insertion_file, input);
atree.insert(string_to_int(input));
}
atree.print();
} else
cout << "Invalid file name." << endl;
}
else if(input == "3"){
cout << endl;
cout << "Enter integer keys to delete. Enter \"q<Enter>\" to quit." << endl;
cout << endl;
getline(cin, input);
while(input != "q"){
atree.remove(string_to_int(input));
atree.print();
getline(cin, input);
}
}
else if(input == "4"){
cout << endl << "Enter Deletion File Name:" << endl;
getline(cin, input);
ifstream deletion_file;
deletion_file.open(input.c_str());
if(!deletion_file.fail()){
while(!deletion_file.fail() && !deletion_file.eof()){
getline(deletion_file, input);
atree.remove(string_to_int(input));
}
atree.print();
} else
cout << "Invalid file name." << endl;
}
else if (input == "p")
atree.print();
else if(input == "x")
exit_now = true;
}
}
Моя функция avl_delete и ее вспомогательнаяФункции следующие:
template <class Record>
Error_code AVL_tree<Record>::avl_delete(Binary_node<Record>* &sub_root,
const Record &old_data, bool &shorter)
{
//If key not found
if (sub_root == NULL) return not_present;
//Key is less than current subroot's value
else if (old_data < sub_root->data){
avl_delete(sub_root->left, old_data, shorter);
}
//Key is greater than current subroot's value
else if (old_data > sub_root->data){
avl_delete(sub_root->right, old_data, shorter);
}
//Key found, delete this
else
{
//Create a temp node
Binary_node<Record> *temp;
//No child case
if (sub_root->left == NULL && sub_root->right == NULL){
temp = sub_root;
sub_root = NULL;
delete temp;
shorter = true;
}
//No left child case
else if (sub_root->left == NULL){
temp = sub_root->right;
sub_root = temp;
delete temp;
shorter = true;
}
//No right child case
else if (sub_root->right == NULL){
temp = sub_root->left;
sub_root = temp;
delete temp;
shorter = true;
}
//Two child case
else {
//Find immediate successor
temp = sub_root->right;
while (sub_root->left != NULL){
temp = sub_root->left;
}
//Change the value of the deleted Node's key to that of it's immediate successor
sub_root->data = temp->data;
//Delete the immediate successor
avl_delete(sub_root->right, temp->data, shorter);
}
}
//If tree's only node has been deleted
if (sub_root == NULL) return success;
//Handle rebalancing cases (only if shorter == true)
if (shorter) {
//Reset shorter to false. Will be changed back to true to propogate in cases where appropriate
shorter = false;
if (sub_root->get_balance() == equal_height) {
if (old_data < sub_root->data) sub_root->set_balance(right_higher);
else if (old_data > sub_root->data) sub_root->set_balance(left_higher);
}
else if (sub_root->get_balance() == right_higher) {
//This case is unbalanced
if (old_data < sub_root->data){
right_balance(sub_root);
//Check to see whether to propogate shorter
if (sub_root->get_balance() == equal_height) shorter = true;
}
else if (old_data > sub_root->data) {
sub_root->set_balance(equal_height);
shorter = true;
}
}
else if (sub_root->get_balance() == left_higher) {
if (old_data < sub_root->data){
sub_root->set_balance(equal_height);
shorter = true;
}
//This case is unbalanced
else if (old_data > sub_root->data) {
left_balance(sub_root);
//Check to see whether to propogate shorter
if (sub_root->get_balance() == equal_height) shorter = true;
}
}
}
return success;
}
template <class Record>
void AVL_tree<Record>::left_balance(Binary_node<Record>* &sub_root)
/*
Pre: sub_root points to a subtree of an AVL_tree that
is doubly unbalanced on the left.
Post: The AVL properties have been restored to the subtree.
Uses:
*/
{
Binary_node<Record>* &left_tree = sub_root->left;
// case left_higher: single right rotation
// O ub --> subroot
// /
// O lh --> left_tree
// /
//O
switch (left_tree->get_balance()) {
case left_higher: // single right rotation
sub_root->set_balance(equal_height);
left_tree->set_balance(equal_height);
rotate_right(sub_root); //pointer adjustment
break;
case equal_height: // impossible case
cout << "WARNING: If you see this in an insertion, program error is detected in left_balance" << endl;
left_tree->set_balance(right_higher);
rotate_right(sub_root);
break;
// case left_higher: double rotation left
// O ub --> sub_root
// /
// O rh --> left_tree
// \
// O three cases --> sub_tree
case right_higher:
Binary_node<Record> *sub_tree = left_tree->right;
//set balance of sub_root and left_tree assuming rotation is done
switch (sub_tree->get_balance()) {
case equal_height:
sub_root->set_balance(equal_height);
left_tree->set_balance(equal_height);
break;
case left_higher:
sub_root->set_balance(right_higher);
left_tree->set_balance(equal_height);
break;
case right_higher:
sub_root->set_balance(equal_height);
left_tree->set_balance(left_higher);
break;
}
//set balance of sub_tree after rotation
sub_tree->set_balance(equal_height);
//perform actual rotation
rotate_left(left_tree);
rotate_right(sub_root);
break;
}
}
template <class Record>
void AVL_tree<Record>::right_balance(Binary_node<Record> *&sub_root)
/*
Pre: sub_root points to a subtree of an AVL_tree that
is unbalanced on the right.
Post: The AVL properties have been restored to the subtree.
Uses: Methods of struct AVL_node;
functions rotate_right and rotate_left.
*/
{
Binary_node<Record>* &right_tree = sub_root->right;
// case right_higher: sigle left rotation
// O ub --> subroot
// \
// O rh --> right_tree
// \
// O
switch (right_tree->get_balance()) {
case right_higher: // single left rotation
sub_root->set_balance(equal_height);
right_tree->set_balance(equal_height);
rotate_left(sub_root); //pointer adjustment
break;
case equal_height: // impossible case
cout << "WARNING: If you see this in an insertion, program error is detected in right_balance" << endl;
right_tree->set_balance(left_higher);
rotate_left(sub_root);
break;
// case left_higher: double rotation left
// O ub --> sub_root
// \
// O lh --> right_tree
// /
// O three cases --> sub_tree
case left_higher:
Binary_node<Record> *sub_tree = right_tree->left;
//set balance of sub_root and right_tree assuming rotation is done
switch (sub_tree->get_balance()) {
case equal_height:
sub_root->set_balance(equal_height);
right_tree->set_balance(equal_height);
break;
case left_higher:
sub_root->set_balance(equal_height);
right_tree->set_balance(right_higher);
break;
case right_higher:
sub_root->set_balance(left_higher);
right_tree->set_balance(equal_height);
break;
}
//set balance of sub_tree after rotation
sub_tree->set_balance(equal_height);
//perform actual rotation
rotate_right(right_tree);
rotate_left(sub_root);
break;
}
}
//adjustment of pointers
template <class Record>
void AVL_tree<Record>::rotate_left(Binary_node<Record> *&sub_root)
/*
Pre: sub_root points to a subtree of the AVL_tree.
This subtree has a nonempty right subtree.
Post: sub_root is reset to point to its former right child, and the former
sub_root node is the left child of the new sub_root node.
*/
{
if (sub_root == NULL || sub_root->right == NULL) // impossible cases
cout << "WARNING: program error detected in rotate_left" << endl;
else {
Binary_node<Record> *right_tree = sub_root->right;
sub_root->right = right_tree->left;
right_tree->left = sub_root;
sub_root = right_tree;
}
}
template <class Record>
void AVL_tree<Record>::rotate_right(Binary_node<Record> *&sub_root)
/*
Pre: sub_root points to a subtree of the AVL_tree.
This subtree has a nonempty left subtree.
Post:
*/
{
if (sub_root == NULL || sub_root->left == NULL) // impossible cases
cout << "WARNING: program error detected in rotate_right" << endl;
else {
Binary_node<Record> *left_tree = sub_root->left;
sub_root->left = left_tree->right;
left_tree->right = sub_root;
sub_root = left_tree;
}
}
Ожидаемые результаты приведут к печатному списку значений ключа и значений ключа правого и левого дочерних элементов соответствующих узлов. Общая структура дерева AVL.