Вставка C ++ в двоичное дерево поиска с использованием массива

Question

Итак, в этой конкретной программе у меня есть узлы, хранящиеся внутри вектора узлов. Эти узлы содержат пользовательский ввод int ID, int age и строковое имя.

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

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

Если он меньше идентификатора в корне, то он помещается в положение (корень * 2). Если он больше, чем корень, он помещается в положение (корень * 2 + 1)

Тем не менее, я испытываю огромные трудности с размещением в векторе, если эти две точки уже заняты другим узлом.

Можно ли каким-либо образом создать цикл, который будет проверять значение в заполненной области и продолжать цикл до тех пор, пока не найдет пустую область?

Текущий пример, с которым я работаю

ID 50, ID 100, ID 75

ID 50 находится в положении 1.

ID 100 вставляется в позицию 3, так как он пуст (2 * 1)

Идентификатор 75 пытается быть вставлен, но позиция 3 заполнена, поэтому мне нужно сравнить его с идентификатором в позиции 3, используя тот же алгоритм. В этом случае, поскольку 75 меньше 100, он будет помещен в положение 4.

Я полностью озадачен тем, как реализовать такой алгоритм в цикле

Любая помощь будет высоко ценится.

Вот мой код.

void BST :: insert () {

int ID;
int AGE;
string NAME;
bool done = false;

int root = 1;

cout << "Please enter the ID number, age and name" << endl;
do
{
    cin >> ID >> AGE >> NAME;
} while (ID <= 0);



Node *tree = new Node(ID, AGE, NAME);


if (!binaryTree.empty())
{

    do
    {
        Node &n = binaryTree.at(root);
        if (n.ID == 0)
        {
            n.ID = ID;
            n.age = AGE;
            n.name = NAME;
            done = true;
            break;
        }
        else if (ID < n.ID)
        {
            root = 2 * root;
        }
        else
        {
            root = 2 * root + 1;
        }
    } while (done = true);
}

if (binaryTree.empty())
{
    binaryTree.push_back(*tree);
}


start();

}

Я все еще плохо знаком с этим языком, поэтому любая помощь будет принята с благодарностью!

EDIT:

Я исправил некоторые несоответствия и добавил предложенный код, однако теперь выдается исключение out_of_bounds.

Спасибо!

Answer 1

Мой вопрос, по сути, как бы мне превратить такой алогрит в цикл while / do цикл while и т. д.

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

Но сначала возникли некоторые проблемы с вашим кодом.

1. Вы сравниваете Node.ID (int) с NULL, чтобы проверить, является ли местоположение в векторе "пустым". NULL имеет ту же семантику, что и 0, поэтому я предполагаю, что никакие идентификаторы не будут 0. Ваш код на самом деле не проверяет это, поэтому вы можете решить этот случай и / или решить эти проблемы проектирования.

2. Я понятия не имею, почему вы динамически распределяете память с помощью new, если вы используете вектор для хранения ваших узлов. Это может привести к утечке памяти.

3. Я предполагаю, что вы обрабатываете создание вектора соответствующего размера в коде, который вы не опубликовали. Если вы этого не сделаете, ваш код потерпит крах, когда at выдает исключение, когда root находится за пределами вектора.

Если он меньше идентификатора в корне, то он помещается в положение (корень * 2). Если он больше, чем корень, то он помещается в положение (корень * 2 + 1)

4. Что если идентификатор равен идентификатору в корне?

И, наконец, код с циклом goto.

int root = 1;

BEGIN LOOP            
    Node &n = binaryTree.at(root);
    if (n.ID == 0)
    {
        n.ID = ID;
        n.age = AGE;
        n.name = NAME;
        BREAK OUT OF LOOP
    }
    else if (ID < n.ID)
    {
        root = 2*root;
    }
    else
    {
        root = 2*root + 1;
    }
REPEAT