Функция, которая считает количество имен в дереве больше входного имени - PullRequest
Новая
       8

Функция, которая считает количество имен в дереве больше входного имени

0 голосов
/ 22 апреля 2020

Я пытаюсь найти в двоичном дереве строки, которые больше, чем строка "Jessica". Это функция, которую я сейчас пытаюсь сделать: 

int greaternames(Bnode* root, string searchname){
    if(root == NULL){return 0;}
    else{
        if(searchname <= root -> data){
            return size(root -> right) + greaternames(root -> left, searchname) + 1;
        }
        else if(searchname > root -> data){
            greaternames(root -> right, searchname);
        }
    }
}

Это мой код в целом, все остальное работает как надо: 

#include<iostream>
#include<fstream>
#include<string>
using namespace std;

struct Bnode{
    string data;
    Bnode* left;
    Bnode* right;
};

void inorder(Bnode* root){
    if(root != NULL){
        inorder(root -> left);
        cout << root -> data << endl;
        inorder(root -> right);
    }
}

void add(Bnode*& root, string item){
    if(root == NULL){
        root = new Bnode;
        root -> data = item;
        root -> left = root -> right = NULL;
    }
    else if (item <= root -> data){
        add(root -> left, item);
    }
    else{
        add(root -> right, item);
    }
}

int size(Bnode* root){
    if(root == NULL) return 0;
    else
    return size(root -> left) + size(root -> right) + 1;
}

void count(Bnode* root, string target){
    int i = 0;
    Bnode* cursor = root;
    while(cursor != NULL){
        if(cursor -> data == target){
            i++;
            cursor = cursor -> left;
        }
        else if(cursor -> data > target){
            cursor = cursor -> left;
        }
        else{cursor = cursor -> right;}
    }
    cout << "Your search name appears " << i << " times" << endl;
}

int greaternames(Bnode* root, string searchname){
    if(root == NULL){return 0;}
    else{
        if(searchname <= root -> data){
            return size(root -> right) + greaternames(root -> left, searchname) + 1;
        }
        else if(searchname > root -> data){
            greaternames(root -> right, searchname);
        }
    }
}

int main(){
    Bnode* root = NULL;
    string name;
    ifstream ins;
    ins.open("names.txt");
    while(ins >> name){
        add(root, name);
    }
    ins.close();

    count(root, "Matthew");
    cout << greaternames(root, "Jessica") << " names greater than Jessica" << endl;

return 0;
}

names.txt is просто файл, который содержит 173 строки имен.

Я попытался отсортировать копию функции размера, вместо того чтобы считать все, что подсчитывает только поддеревья правой стороны, если root меньше или равно поисковое имя "Джессика". Но вывод, который я сейчас получаю, примерно -4 миллиона.

Кроме того, это для домашнего задания, поэтому функция должна быть рекурсивной.

Ответы [ 2 ]

0 голосов
/ 22 апреля 2020

Вам не хватает оператора возврата в функции greatNames: 

int greaternames(Bnode* root, string searchname){
    if(root == NULL){return 0;}
    if(searchname <= root -> data){
        return size(root -> right) + greaternames(root -> left, searchname) + 1;
    }
    //else if statement that was here is redundant and will give you compiler warnings, 
    //  due to missing return statement at the end of the function 
    return greaternames(root -> right, searchname); //missing return statement
}
0 голосов
/ 22 апреля 2020

В качестве подсказки скомпилируйте с предупреждениями, включенными до максимума. Вы должны получить уведомление где-то, что функция не всегда возвращает значение. Какая это функция, почему она не всегда возвращает значение, и как изменение этой проблемы решит вашу проблему?

...