do
{
cin >> ID >> AGE >> NAME;
} while (ID < 0);
Не фактическая проблема, но вы должны проверить std::cin для его состояния после этой операции - если пользователь действительно ввел неправильный ввод ("xyz"), cin остается в состоянии сбоя, и вы никогда не получите действительный ввод. .. Кроме того, если вы сделаете id и age без знака, вам не нужно проверять наличие отрицательного ввода.
Мой личный вариант:
for(;;)
{
std::cin >> id >> age >> name;
if(std::cin)
// input is valid!
break;
std::cout << "invalid input" << std::endl; // some better text?
std::cin.clear();
std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
}
Подробнее см. ...
if (index = 0)
// ^ this is an assignment! always sets index to 0 and then
// checks the value; for COMPARISON, you need to use ==
{
binaryTree[1] = *tree;
// ^ and when do you ever fill index 0???
}
Задание вместо сравнения - это то, что на самом деле вызывает вашу проблему!
Если index будет представлять количество элементов в векторе, вы можете полностью удалить его, вместо этого используйте binaryTree.size() ...
if (binaryTree.at(root).ID == NULL)
{
binaryTree.at(root) = *tree;
cout << "Vector size: " << binaryTree.size() << endl;
}
Подождите, вы собираетесь предварительно заполнить вектор значениями по умолчанию ??? Если это так, то binaryTree.size () будет всегда иметь одинаковый размер ... И вам, возможно, понадобится огромный предварительно выделенный массив и, вероятно, будут плохие оценки заполнения. Возвращаясь к позже. Помните, что NULL - это макрос, который должен представлять нулевые указатели (если вы действительно имеете дело с этим, предпочтите вместо этого ключевое слово nullptr!). Не используйте его для целочисленных сравнений, используйте значение 0 напрямую.
Дополнительно: at сгенерирует исключение, если вектор недостаточно велик. А потом? Предпочитаю использовать оператор индекса, но перед этим проверьте, достаточно ли велик вектор. Если нет, увеличьте размер вектора соответствующим образом (например, сделайте его вдвое больше предыдущего размера).
Node* tree = new Node(id, age, name);
binaryTree[x] = *tree;
delete tree;
Ну, а зачем тогда в куче все равно? Просто сделайте это так:
Node tree(id, age, name);
// no pointer! creating object directly on the stack!
binaryTree[x] = tree; // assign directly
// no delete necessary, object will be destructed automatically when leaving scope
В текущем случае нет необходимости, перемещение и копирование приводят к одному и тому же, но с более сложными объектами, перемещение вместо копирования может иметь значение, поэтому вы можете оптимизировать до:
binaryTree[x] = std::move(tree); // creates an rvalue reference...
Возвращаясь к проблеме размера / заполнения: двоичные деревья эффективны, только если вы сохраняете их сбалансированными. Как правило, во время выполнения, если хранится в массиве, как структуры, такие как векторы, также в памяти. Так что вы должны держать свое дерево сбалансированным. Вариант может начинаться не с корня дерева, а просто добавлять элемент в конце (используйте push_back), а затем перемещать его вверх, если он больше родительского узла, если он находится в левом дереве, или меньше, чем, если в правильном дереве. Если вы предоставляете конструктор перемещения, вы можете использовать std::swap для обмена элементами. Этот альтернативный подход дополнительно исключает необходимость использования дозорных значений (node.id == 0) ...
Редактировать в ответ на ваш комментарий:
ОК, теперь сначала давайте включим в алгоритм индекс 0, нет нужды пропускать позицию 0.
Тогда ваша проблема может быть уже первой вставкой: вы уверены, что вектор действительно содержит уже два фиктивных элемента? Лучше давайте посмотрим, у нас есть пустой вектор с самого начала. Тогда мы просто можем сделать:
unsigned int index = 0;
// renaming root to index, assuming we dropped
// the other index variable already
// benefit: you can clearly differentiate my and your code...
Node node(id, age, name);
for(;;)
{
if(index <= binaryTree.size()) // covers empty vector, too, as 0 <= 0...
{
binaryTree.resize(index + 1);
// vector with size of n can store n elements
// at indices [0 .. n - 1] - deduce the inverse yourself
// and you know why index + 1...
binaryTree[index] = node;
// if we needed to resize, the new elements are unoccupied
// anyway, so we simply can insert and are done...
break;
}
if(binaryTree[index].id == 0)
{
// sentinel found, can insert here:
binaryTree[index] = node;
break;
}
// now calculate the child index just as before
}
Однако при расчете индекса следующего потомка также есть ошибка:
if (tree->ID > binaryTree.at(root).ID)
root = 2 * root + 1;
if (tree->ID < binaryTree.at(root).ID)
root = 2 * root;
А что, если идентификаторы одинаковые ??? По крайней мере один из них должен содержать равенство, иначе вы попадете в бесконечный цикл. Но тогда одно условие получает в точности обратную от другого, поэтому вы можете просто использовать if / else:
if (node.id > binaryTree[index].id)
index = 2 * index + 1;
else
index = 2 * index;
Теперь немного приятной настройки: в C ++ сравнения всегда приводят к логическим значениям, затем они повышаются до (без знака) int, всегда получая либо 0, либо 1, так что вы можете, если хотите, сократить до следующей однострочной (хорошо , мое переименование применяется снова ...):
index = 2 * index + (tree->ID > binaryTree[index].ID);