Проблема со вставкой в ​​бинарное дерево поиска - PullRequest
Новая
       42

Проблема со вставкой в ​​бинарное дерево поиска

0 голосов
/ 17 апреля 2019

Я написал код для вставки в дерево двоичного поиска и его обход.

class node
{
public:
    int data;
    node *left;
    node *right;
};
node* createNode(int value)
{
    node *temp = new node;
    temp->data = value;
    temp->left = NULL;
    temp->right = NULL;
    return temp;
}

node *start = NULL;

void insertNode(int val)
{
    if (start == NULL)
    {
        start = createNode(val);
        return;
    }

    node *temp = start;
    while ((temp->left != NULL) && (temp->right != NULL))
    {
        if (val < temp->data)
        {
            temp = temp->left;
        }
        else if (val > temp->data)
        {
            temp = temp->right;
        }
        else
        {
            cout << "Already exists in tree\n";
            return;
        }
    }
    if (val < temp->data)
    {
        temp->left = createNode(val);
        return;
    }
    else
    {
        temp->right = createNode(val);
        return;
    }


}

void inorder(node *root)
{
    if (root != NULL)
    {
        inorder(root->left);
        printf("%d \n", root->data);
        inorder(root->right);
    }
}

Он не работает нормально в некоторых тестовых случаях.

Например, если вставить 15, 25, а затем 35, а затем пройти по дереву, он печатает только 15 и 25.

Я не могу найти проблему в коде.В чем проблема с моей логикой вставки?

1 Ответ

0 голосов
/ 17 апреля 2019

Давайте рассмотрим поведение -

  1. вы вставляете 15. if (start == NULL)
    • , эта проверка создает начальный узел.Теперь есть начальный узел со значением 15 и слева и справа как NULL.
вы вставляете 25. (temp->left != NULL) && (temp->right != NULL)
  • это оказывается ложным.
  • (val < temp->data) эта проверка создает правый узел.
вы вставляете 35. (temp->left != NULL) && (temp->right != NULL)
  • все равно оказывается ложным.
  • (val < temp->data) эта проверка создает правый узел (заменяя текущий правый узел). Что не так.

Здесь необходимо исправить условие цикла while.

...