Сбои дерева двоичного поиска

Question

Я реализую дерево бинарного поиска в C ++. У меня есть следующий код для добавления записи в дерево:

void tree::add(int n)
{
    int found;
    leaf *t,*parent;
    findparent(n,found,parent);
    if(found==YES)
        cout<<"\nSuch a Node Exists";
    else
    {
        t=new leaf;
        t->data=n;
        t->l=NULL;
        t->r=NULL;

        if(parent==NULL)
            p=t;
        else
            parent->data > n ? parent->l=t : parent->r=t;
    }
}

В основном я использую карту для хранения значений, считанных изтекстовый файл как целое число.Теперь, когда я передаю значение функции add, происходит сбой программы.

int main()
{
    tree t;
    map<int,int> word;
    map<int,int>::iterator count;
    string str;
    int num;
    string space ="";
    while((str=value(cin))!=space )
    {
        num = atoi(str.c_str());
        ++word[num];
    }
    int size = (int) word.size();
    int data[size];
    int x = 0;
    for(count = word.begin(); count!=word.end(); ++count){
        data[x] = (*count).first;
        x = x+1;
    }
    for (int iter = 0; iter<size; iter++){
        int x = 3 * data[iter];
        t.add(x);
    }

    return 0;
}

То, что я делаю здесь, я преобразовываю пользовательский ввод в целые числа, используя atoi, а затем добавляю их на карту.Затем я получаю размер карты и использую его для заполнения массива элементами.Теперь, когда я перебираю массив и пытаюсь передать элементы массива в дерево с помощью функции add, происходит сбой программы.Программа работает нормально, когда я пытаюсь добавить фиксированный элемент массива.Например:

int data [] = {6,7,8,9};

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

Pastebin Ссылка всей программы: http://pastebin.com/SWqTccJf

Answer 1

Я думаю, что Тайлер Хиндман прав, что это не стандартный C ++. Однако g ++, например, поддерживает это «расширение языка» C99. Это не отменяет того факта, что обычно плохая практика - размещать в стеке массивы, размер которых неизвестен во время компиляции и может быть довольно большим.

Я предполагаю, что в коде есть ошибка, которая не была предоставлена. Некоторые ошибки, связанные с проблемами памяти / указателя, могут быть замаскированы в зависимости от содержимого памяти, что может расстраивать их. В любом случае, я не вижу ошибки в прилагаемом коде. Я бы обратил внимание на то, где именно происходит сбой, и каково состояние программы в момент сбоя.

Для получения наилучшей помощи укажите минимальный (но достаточный) код для воспроизведения проблемы. Может быть, использовать pastebin, если он кажется слишком большим?

// РЕДАКТИРОВАТЬ // ОК. Я посмотрел ваш полный список кодов.

См. исправленный код . Основные отличия:

1) У вас есть ошибка в коде, которая очищает дерево. Здесь не следует вызывать Tree :: del (), потому что он предназначен для удаления определенного значения. Он должен найти узел, который нужно удалить, а затем разобраться с различными особыми случаями. Когда вы стираете содержимое дерева, вы можете просто рекурсивно удалить все узлы. Легко и быстро!

2) Я объединил ваши две функции поиска в одну.

3) В Tree :: del произошла ошибка для случая, когда удаляемый узел является корневым. При удалении корневого узла родитель будет иметь значение NULL ...

4) Логика чтения чисел с входа изменена.

Надеюсь, вы изучите код и узнаете, что изменилось и почему. Также не забудьте точно определить, где происходит сбой вашего кода, и получить как можно больше информации о сбое, вместо того чтобы просто сказать «о черт, он разбился!».

С наилучшими пожеланиями:)

Answer 2

В C ++ вы не можете использовать

int data[size];

, когда size не известно во время компиляции.Либо используйте

int * data = new int[size];

// use data

delete [] data; // remember to delete

Или, так как это C ++, используйте std::vector

std::vector<int> data(size);