Указатель обхода в дереве при вставке - PullRequest
Новая
       30

Указатель обхода в дереве при вставке

0 голосов
/ 05 ноября 2018 
#include<iostream>

using namespace std;

struct node
{
    int data;
    node *right;
    node *left;
} ;

node *root = NULL;
node *right = NULL;
node *left = NULL;

node insert(int data)
{
    node *ptr = new node;
    ptr->data = data;
    ptr->left = NULL;
    ptr->right = NULL;

    if(root==NULL)
    {
        root = ptr;
        cout<<"Inserted "<<root->data<<" at root\n";
    }
    else
    {
        node *pos = root;
        while(pos)
        {
            cout<<pos->data<<" pos->data\n";
            if(pos->data > data)
            {
                cout<<pos->data<<": data\n";
                pos = pos->left;
            }
            else if(pos->data < data)
            {
                cout<<pos->data<<": data\n";
                pos = pos->right;
            }
            if(!pos)
                cout<<"NULL\n";
        }
        pos = ptr;
        cout<<"Inserted\n";
    }
    return *root;
}

void preorder(node *root)
{
    if(root)
    {
        cout<<root->data;
        preorder(root->left);
        preorder(root->right);
    }
}

int main()
{
    insert(2);
    insert(1);
    insert(3);
    insert(4);
    insert(5);
    preorder(root);
    return 0;
}

Здесь, вставляя новый элемент, я указываю root на новую переменную pos, чтобы корень не изменялся, чтобы он стал параметром для функции preorder() должным образом, поскольку он является действительным корнем

Но pos не вставляет все элементы и не отображает требуемые результаты. Короче говоря, я должен использовать root вместо pos для вставки, но использование root напрямую изменяет «фактический» корень (который в данном случае равен 2).

1 Ответ

0 голосов
/ 05 ноября 2018

Но pos не вставляет все элементы, а также не отображает требуемые результаты.

Я думаю, что в основном есть две ошибки.

  • root никогда не обновляется в текущей функции insert, поскольку ptr назначается только временной переменной pos после завершения цикла.

  • Мы должны рассмотреть случай, когда значение переданного аргумента data уже сохранено в двоичном дереве.

Кроме того, preorder снова отображает root и снова сбивает с толку. Пример исправления insert и preorder следующий. ДЕМО здесь. 

node insert(int data)
{
    node *ptr = new node;
    ptr->data = data;
    ptr->left = nullptr;
    ptr->right = nullptr;

    if(!root)
    {
        root = ptr;
    }
    else
    {
        node *pos = root;

        while(true)
        {
            if(pos->data > data)
            {
                if(!pos->left){
                    pos->left = ptr;
                    break;
                }

                pos = pos->left;
            }
            else if(pos->data < data)
            {
                if(!pos->right){
                    pos->right = ptr;
                    break;
                }

                pos = pos->right;                
            }
            else{
                break;
            }
        }
    }
    return *root;
}

void preorder(node *next)
{
    if(next)
    {
        cout << next->data << std::endl;
        preorder(next->left);
        preorder(next->right);
    }
}
...