Двоичное дерево поиска Вставка и удаление функций

Question

Я работаю над проектом для своего класса информатики и столкнулся с небольшими проблемами со вставкой и удалением функций двоичного дерева поиска.

Проект предполагает вставку слова и целого числа в узел и присоединение этих узлов в двоичном дереве поиска. Вот full project description.

Моя программа будет вставлять слова в дерево просто отлично, но слова пустые. Код для этих операций поступал прямо от инструктора, и я не уверен, где проблема. Любая помощь очень ценится!

Заголовочный файл: Файл

#ifndef CONCORDANCE_H 
#define CONCORDANCE_H 
#include <iostream> 
#include <cstdlib> 

const int MAX = 8; 

class Concordance 
{ 
    public: 
     typedef char Item[MAX+1]; 

     // Constructor 
     Concordance() { root = NULL; } 

     // Destructor 
     ~Concordance(); 

     // Modification Member Functions 
     void insert(Item entry, int n); 
     void remove(Item target); 
     int get_count(Item target); 

     // Constant Member Functions 
     int length(); 

     // Friend Functions 
     friend std::ostream& operator << (std::ostream& out_s, Concordance& c); 

    private: 
     // Data Members 
     struct Node 
     { 
      Item data; 
      int count; 
      Node *left; 
      Node *right; 
     }; 
     Node *root; 
     void destroy(Node *r); 
     void help_remove(Node *&t, Item target); 
     void remove_node(Node *&t); 
     void print(Node *p, std::ostream& out_s); 
     void help_insert(Node* &t, Item entry, int n); 
     int count(Node *r); 
}; 
#endif 

Реализация:

#include "concordance.h" 
#include <iostream> 
#include <iomanip> 
#include <cstring> 
using namespace std; 

void Concordance::destroy(Node *r) 
{ 
    if(r != NULL) 
    { 
     destroy(r -> left); 
     destroy(r -> right); 
     delete r; 
    } 
} 

Concordance::~Concordance() 
{ 
    destroy(root); 
} 

void Concordance::help_insert(Node* &t, Item entry, int n) 
{ 
    if (t == NULL) 
    { 
     t = new Node; 
     strcpy(t -> data, entry); 
     t -> count = n; 
     t -> left = NULL; 
     t -> right = NULL; 
    } 
    else if (strcmp(entry, t -> data) < 0) 
     help_insert (t -> left, entry, n); 
    else 
     help_insert (t -> right, entry, n); 
} 

void Concordance::insert(Item entry, int n) 
{ 
    help_insert(root, entry, n); 
} 

void Concordance::help_remove(Node *&t, Item target) 
{ 
    if(strcmp(t -> data, target) == 0) 
     remove_node(t); 
    else if(strcmp(target, t -> data) < 0) 
     help_remove(t -> left, target); 
    else 
     help_remove(t -> right, target); 
} 

void Concordance::remove_node(Node *&t) 
{ 
    Node *ptr; 
    Node *back; 
    if(t -> left == NULL && t -> right == NULL) 
    { 
     delete t; 
     t = NULL; 
    } 
    else if(t -> left == NULL) 
    { 
     ptr = t; 
     t = t -> right; 
     delete ptr; 
    } 
    else if(t -> right == NULL) 
    { 
     ptr = t; 
     t = t -> left; 
     delete ptr; 
    } 
    else 
    { 
     back = t; 
     ptr = t -> right; 
     while(ptr -> left != NULL) 
     { 
      back = ptr; 
      ptr = ptr -> left; 
     } 
     strcpy(t -> data, ptr -> data); 
     if(back == t) 
      remove_node(back -> right); 
     else 
      remove_node(back -> left); 
    } 
} 

void Concordance::remove(Item target) 
{ 
    help_remove(root, target); 
} 

int Concordance::get_count(Item target) 
{ 
    Node *p = root; 
    int temp; 
    while(p != NULL) 
    { 
     if(strcmp(p -> data, target) == 0) 
      temp = p -> count; 
     else if(strcmp(target, p -> data) < 0) 
      p = p -> left; 
     else 
      p = p -> right; 
    } 
    return temp; 
} 

int Concordance::count(Node *r) 
{ 
    if(r == NULL) 
     return 0; 
    else 
     return count(r -> left) + 1 + count(r -> right); 
} 

int Concordance::length() 
{ 
    return count(root); 
} 

void Concordance::print(Node *p, ostream& out_s) 
{ 
    if(p != NULL) 
    { 
     print(p -> left, out_s); 
     out_s << left << setw(10) << p -> data << right << setw(9) << p -> count << endl; 
     print(p -> right, out_s); 
    } 
} 

ostream& operator << (ostream& out_s, Concordance& c) 
{ 
    Concordance::Node *output; 

    out_s << "Word" << setw(10) << " " << "Count" << setw(8) << endl; 
    out_s << "--------------------" << endl; 

    c.print(c.root, out_s); 

    out_s << "--------------------" << endl; 

    return out_s; 
} 

Основная программа:

#include <iostream> 
#include <iomanip> 
#include <fstream> 
#include <cstring> 
#include "concordance.h" 
using namespace std; 

typedef char Word[MAX+1]; 

void read_word(ifstream& infile, Word array) 
{ 
    char ch; 
    int i = 0; 

    infile.get(ch); 

    while(isalpha(ch) && !isspace(ch) && !ispunct(ch)) 
    { 
     if(i > MAX-1) 
     { 
      while(!isspace(ch) && !ispunct(ch)) 
       infile.get(ch); 
      break; 
     } 

     ch = toupper(ch); 

     array[i] = ch; 
     i++; 
     infile.get(ch); 
    } 
    if(i != 0) 
     array[i] = '\0'; // Null Character 
} 

void make_list(ifstream& infile, Word& array) 
{ 
    Concordance concord; 
    int count = 0; 
    int length; 

    read_word(infile, array);    // Read a word 
    while(!infile.eof())     // While the file isn't empty... 
    { 
     concord.insert(array, count);  // Insert into concordance 
     read_word(infile, array);   // Read another word 
    } 

    cout << concord; 
    length = concord.length(); 

    cout << "The file contains " << length << " distinct words." << endl; 
} 

int main() 
{ 
    char file_name[100]; 
    typedef char Word[MAX+1]; 
    ifstream infile; 
    Word array; 

    cout << "Enter a file name: "; 
    cin >> file_name;    // Get file name 

    infile.open(file_name);   // Open file 
    if(!infile)      // If we couldn't open the file... 
    { 
     cout << "Failed to open file." << endl; 
     return 0; 
    } 

    make_list(infile, array);  // Make the concordance 

    infile.close();     // Close the input file 

    return 0; 
} 

Answer 1

Ваша проблема не с используя реализацию бинарного дерева, но при реализации read_word: просто добавьте проверку для eof в состояние цикла, и все должно быть в порядке.

т.д .:

while(!infile.eof() && isalpha(ch) && !isspace(ch) && !ispunct(ch))