Блог

Главная - Вопросы по программированию - AVLTree не может найти данные при поиске

AVLTree не может найти данные при поиске

#c #binary-tree #nodes #avl-tree

#c #двоичное дерево #узлы #avl-дерево

Вопрос:

Я работаю над заданием для школы. Я должен создать AVLTree, прочитать данные из текстового файла, а затем создать объект Professor с этими данными. Однако, когда я пытаюсь выполнить поиск профессора по имени, он не может быть найден. В программе по умолчанию используется имя Майкла Скотта, и я не могу найти того, кого я ищу. Моя функция readFromFile работает отлично и получает все данные из файла, поэтому у меня есть данные. На данный момент это вопрос проблем с деревом AVL. Я свяжу все ниже.

Driver.cpp:

 #include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include "AVLTree.h"

using namespace std;

void readFromFile(AVLTree *treeAccess) {

    int numOfProfs = 0;
    string line;
    
    const char *path="/Users/collinchappell/Desktop/Program4Official/Program4Official/ProfessorData.txt";
    
    fstream myFile (path, ios::in);
    
    if (!myFile) {
        cout << "Sorry can't read ProfessorData.txt!" << endl;
    }
    else {
        // Splitting up all the data in the .txt file and the looping through using string stream
        // Not the best solution, however nothing else would work for me so this is what I went with.
        while (getline(myFile, line)) {
            string n;
            string nT;
            string s;
            int b1,b2,b3,b4,b5,b6,b7;
            
            replace(line.begin(), line.end(), '

AVLTree.h:


 #ifndef AVLTree_h
#define AVLTree_h


#include <iostream>
#include "Professor.h"

using namespace std;

class AVLTree {
private:
    
    // TreeNode structure
    struct TreeNode {
        string name;
        Professor *prof;
        struct TreeNode* left;
        struct TreeNode* right;
    };
    // Root of tree
    TreeNode* root;
    
    // Function declarations
    void insert(TreeNode *amp;nodePtr, TreeNode *amp;newNode);
    void destroySubTree(TreeNode *nodePtr);
    void displayInOrder(TreeNode *nodePtr) const;
    int height(TreeNode *nodePtr);
    int diff(TreeNode *nodePtr);
    void balance(TreeNode *amp;temp);
    
    TreeNode* l_rotation(TreeNode *parent) {
        TreeNode *temp;
        temp = parent->right;
        
        parent->right = temp->left;
        temp->left = parent;
        return temp;
    }

    TreeNode* r_rotation(TreeNode *parent) {
        TreeNode *temp;
        temp = parent->left;
        
        parent->left = temp->right;
        temp->right = parent;
        return temp;
    }

    TreeNode* lr_rotation(TreeNode *parent) {
        TreeNode *temp;
        temp = parent->left;
        
        parent->left = (l_rotation(temp));
        return r_rotation(parent);
    }

    TreeNode* rl_rotation(TreeNode *parent) {
        TreeNode *temp;
        temp = parent->right;
        
        parent->right = (r_rotation(temp));
        return l_rotation(parent);
    }
    
    
public:
    AVLTree() { // Constructor
        root = NULL;
    }
    
    ~AVLTree() { // Destructor
        destroySubTree(root);
    }
    
    void insertNode(string n, Professor* professor);
    Professor* searchNode(string);
    
    // Call private displayInOrder()
    void displayInOrder() const {
        displayInOrder(root);
    }

    
};


#endif /* AVLTree_h */
 


AVLTree.cpp:


 #include <iostream>
#include "AVLTree.h"

using namespace std;

// Insert a node into the tree recursively
void AVLTree::insert(TreeNode *amp;nodePtr, TreeNode *amp;newNode) {
    if (nodePtr == NULL) {
        nodePtr = newNode;
    }
    else if (newNode->name < nodePtr->name) {
        insert(nodePtr->left, newNode);
        balance(nodePtr);
    }
    else {
        insert(nodePtr->right, newNode);
        balance(nodePtr);
    }
}

// Destory the sub tree
void AVLTree::destroySubTree(TreeNode *nodePtr) {
    if (nodePtr) {
        if (nodePtr->left) {
          destroySubTree(nodePtr->left);
        }
        if (nodePtr->right) {
          destroySubTree(nodePtr->right);
        }
        delete nodePtr;
    }
}

// Display the tree in order
void AVLTree::displayInOrder(TreeNode *nodePtr) const {
    if (nodePtr) {
        displayInOrder(nodePtr->left);
        cout << nodePtr->name << endl;
        displayInOrder(nodePtr->right);
    }
}

// Get the tree's height
int AVLTree::height(TreeNode *temp) {
    int leftHeight, rightHeight;
    if (temp) {
        leftHeight = height(temp->left);
        rightHeight = height(temp->right);
        
        if (leftHeight > rightHeight) {
            return leftHeight   1;
        }
        else if (leftHeight < rightHeight) {
            return rightHeight   1;
        }
        else {
            return 0;
        }
        
    }
    return 0;
}

// Get the difference
int AVLTree::diff(TreeNode *temp) {
    int l_height = height(temp->left);
    int r_height = height(temp->right);
    return l_height - r_height;
}

// Balance the tree
void AVLTree::balance(TreeNode *amp;temp) {
    int bal_factor = diff (temp);
    if (bal_factor > 1)
    {
        if (diff(temp->left) > 0)  // 2, 1  RIGHT
        {
            temp = r_rotation(temp);
            cout << "nRIGHT rotation";
        }
        else                            // 2, -1 LEFT-RIGHT
        {
            temp = lr_rotation(temp);
            cout << "nLEFT-RIGHT rotation";
        }
    }
    else if (bal_factor < -1)
    {
        if (diff (temp->right) > 0) // -2, 1 RIGHT-LEFT
        {
            temp = rl_rotation(temp);
            cout << "nRIGHT-LEFT rotation";
        }
        else                             // -2, -1 LEFT
        {
            temp = l_rotation(temp);
            cout << "nLEFT Rotation";
        }
    }
}

// Insert a node, calls the private insert function
void AVLTree::insertNode(string n, Professor *proffesor) {
    TreeNode *newNode = NULL; // Pointer to a new node.
    
    newNode = new TreeNode;
    newNode->name = n;
    newNode->prof = proffesor;
    newNode->left = newNode->right = NULL;
    
    // Insert the node.
    insert(root, newNode);
}

Professor* AVLTree::searchNode(string s) {
    
    cout << "Name inputted into search: " << s << endl;
    cout << endl << "Actual name: " << root->name << endl;
    
    TreeNode *nodePtr = root;

    while (nodePtr != NULL) {
        if (nodePtr->name == s) {
          return nodePtr->prof;
        }
        else if (nodePtr->name > s) {
            nodePtr = nodePtr->left;
            cout << "Left -> " << nodePtr << endl;
        }
        else {
            nodePtr = nodePtr->right;
            cout << "Right -> " << nodePtr << endl;
        }
    }
    return NULL;
}
 


Professor.h:


 #ifndef PROFESSOR_H
#define PROFESSOR_H

#include <iostream>
#include <iomanip>
using namespace std;

class Professor
{
    private:
        string name;
        string course;
        bool clearGrading;
        bool goodFeedback;
        bool caring;
        bool reachable;
        bool toughGrader;
        bool lectureHeavy;
        bool attendance;
    public:
        Professor(string n, string course, bool cG, bool gF, bool c, bool r, bool tG, bool lH, bool a) {
            this->name = n;
            this->course = course;
            this->clearGrading = cG;
            this->goodFeedback = gF;
            this->caring = c;
            this->reachable = r;
            this->toughGrader = tG;
            this->lectureHeavy = lH;
            this->attendance = a;
        }
        friend ostream amp;operator << (ostream amp;strm, Professor amp;p)
        {
            strm << endl << endl;
            strm << setw(30) << "Professor:" << setw(20) << p.name << endl;
            strm << setw(30) << "Course:" << setw(20) << p.course << endl;
            strm << setw(30) << "Clear Grading Criteria:" << setw(20);
            if(p.clearGrading == 0) strm << "no"; else strm << "yes";
            strm << endl;
            strm << setw(30) << "Provides Good Feedback:" << setw(20);
            if(p.goodFeedback == 0) strm << "no"; else strm << "yes";
            strm << endl;
            strm << setw(30) << "Caring:" << setw(20);
            if(p.caring == 0) strm << "no"; else strm << "yes";
            strm << endl;
            strm << setw(30) << "Reachable Outside of Class:" << setw(20);
            if(p.reachable == 0) strm << "no"; else strm << "yes";
            strm << endl;
            strm << setw(30) << "Tough Grader:" << setw(20);
            if(p.toughGrader == 0) strm << "no"; else strm << "yes";
            strm << endl;
            strm << setw(30) << "Lecture Heavy:" << setw(20);
            if(p.lectureHeavy == 0) strm << "no"; else strm << "yes";
            strm << endl;
            strm << setw(30) << "Attendance Mandatory:" << setw(20);
            if(p.attendance == 0) strm << "no"; else strm << "yes";
            strm << endl;
            
            return strm;
        }
        
};
#endif
 


ProfessorData.txt:


 Michael Scott$CSC1310$0$0$1$1$0$1$1$Jim Halpert$CSC1310$1$1$1$0$0$0$0$Pam Beesly$CSC1300$1$1$1$0$1$0$1$Dwight Schrute$CSC2400$1$1$0$0$1$1$1$Angela Martin$CSC1300$1$0$0$0$1$1$1$Kelly Kapoor$CSC1300$0$0$0$0$0$0$0$Andy Bernard$CSC2400$1$0$1$1$0$1$1$Kevin Malone$CSC1310$0$1$1$1$0$0$0$Meredith Palmer$CSC1310$0$1$1$1$0$0$0$Phyllis Vance$CSC1300$1$1$1$0$1$0$0$Oscar Nunez$2400$1$1$1$1$1$1$1$
 


Запуск программы:


 11 Proffesors have added from the file.

Which Computer Science professor do you want details about?
Andy Bernard
Angela Martin
Dwight Schrute
Jim Halpert
Kelly Kapoor
Kevin Malone
Meredith Palmer
Michael Scott
Oscar Nunez
Pam Beesly
Phyllis Vance


Type Professor Name: Andy Bernard
Name inputted into search: Andy Bernard

Actual name: Michael Scott
Left -> 0x100704570
Left -> 0x105a045b0
Left -> 0x105b04120
Left -> 0x105b041a0
Name inputted into search: Andy Bernard

Actual name: Michael Scott
Left -> 0x100704570
Left -> 0x105a045b0
Left -> 0x105b04120
Left -> 0x105b041a0
0x7ffeefbfee18Would you like to search another? (Y/N): 
 


Как вы можете видеть, я вставил несколько отпечатков, чтобы отладить происходящее. Я считаю, что мои объекты неправильно вставляются в дерево, или моя функция поиска отключена. Кроме того, я не на 100% уверен в функции баланса. Любая помощь была бы замечательной.


, ' ');
stringstream ss(line);
for (int k = 0; k < 11; k ) {
ss >> n;
ss >> nT;
n = n " " nT;
ss >> s;
ss >> b1;
ss >> b2;
ss >> b3;
ss >> b4;
ss >> b5;
ss >> b6;
ss >> b7;

numOfProfs ;
Professor p(n, s, b1, b2, b3, b4, b5, b6, b7);
cout << p;
treeAccess->insertNode(n, amp;p);
}
}
}
cout << numOfProfs << " Proffesors have added from the file." << endl << endl;
}

int main() {

AVLTree tree;

readFromFile(amp;tree);

bool cont = true;

while (cont) {
cout << "Which Computer Science professor do you want details about?" << endl;
tree.displayInOrder();

cout << endl << endl << "Type Professor Name: ";
string typeName;
getline(cin, typeName);
while (tree.searchNode(typeName) == NULL) {
cout << "Couldn't find that professor! Please type another: ";
getline(cin, typeName);
}
cout << tree.searchNode(typeName);

cout << "Would you like to search another? (Y/N): ";
string ans;
cin >> ans;
if (ans == "y" || ans == "Y") {
continue;
}
else if (ans == "n" || ans == "N") {
return 0;
}

}

return 0;
}
AVLTree.h:



AVLTree.cpp:




Professor.h:




ProfessorData.txt:




Запуск программы:




Как вы можете видеть, я вставил несколько отпечатков, чтобы отладить происходящее. Я считаю, что мои объекты неправильно вставляются в дерево, или моя функция поиска отключена. Кроме того, я не на 100% уверен в функции баланса. Любая помощь была бы замечательной.








	Метки: