BST вставить в C ++

Question

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

BSTNode * BST::Insert(const std::string & v) {
    BSTNode *n = !root ? root = new BSTNode(v) : Insert_Helper(v,root);
    if(n) size++;
    return n;
}

BSTNode * BST::Insert_Helper(const std::string & v, BSTNode *n) {
    if(!n->value.compare(v))
        return NULL; // already have v
    else if(n->value.compare(v) > 0) // v goes to the left
        if(n->left) return Insert_Helper(v,n->left);
        else return n->left = new BSTNode(v);
    else // v goes to the right
        if(n->right) Insert_Helper(v,n->right);
        else return n->right = new BSTNode(v);
}

Ошибка, которую я получаю, выглядит следующим образом: все работает нормально и прекрасно, пока я не попытаюсь вставить дублирующий узел. Он не добавляет новый узел, но увеличивает счетчик.

Наблюдая в GDB, я обнаружил, что когда я пытаюсь добавить уже имеющуюся строку, Insert_Helper работает правильно и возвращает NULL. Однако это значение (на моей машине) примерно равно 0x6, что, конечно, выходит за пределы, но не 0x0, как я думал. Я думаю, что это вызывает проблему в тот момент, когда у меня есть оператор if (n). В этом случае n оценивается как true и увеличивает размер на единицу больше, чем следует.

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

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

Answer 1

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

if(n->right) Insert_Helper(v,n->right);

Вы, вероятно, должны вернуть все, что вернет Insert_Helper:

if(n->right) return Insert_Helper(v,n->right);

Answer 2

Вы можете изменить if(n) size++ на if (n != NULL) size++