Построение дерева с указателями

Я пытаюсь создать функцию, которая вставляет ключевую структуру в дерево. Функция правильно устанавливает корень, но не устанавливает ветки при повторном вызове с другим ключом. Вот код:

дерево.ч:

class tree{

    key *tree_root;

public:
    tree();
    //Constructor

    void treedestroy(key *root);
    //Tree destructor helper

    ~tree();
    //Destructor

    void insert(key* root, key *newkey, int disc);

};

вставить функцию из класса дерева:

void tree::insert(key *root, key *newkey, int disc){
    if (root == NULL){
        root = newkey;
        return;
    }
    if (newkey->cord[disc] <= root->cord[disc])
        insert(root->left, newkey, (disc+1)%4);
    else if (newkey->cord[disc] > root->cord[disc])
        insert(root->right, newkey, (disc+1)%4);
}

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


c++ tree
person HighLife    schedule 11.10.2011    source источник

Ответы (3)


arrow_upward
1
arrow_downward

Я не совсем уверен в вашем подходе здесь, но чтобы помочь вам встать на ноги, было бы полезно использовать сигнатуру функции:

void insert(key*& root, key *newkey, int disc);

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

Ваша функция в ее нынешнем виде изменяет локальную переменную функции без распространения этих изменений.

Эта статья является сбалансированным и быстрым чтением при переходе по ссылке (я не могу скажи, что лучший - просто первый достойный, который я нашел)

person Nate    schedule 11.10.2011

arrow_upward
0
arrow_downward

  1. Если при первом вызове newkey имеет значение null, root останется нулевым. Убедитесь, что вызов метода правильный.

  2. Я бы поставил else, а не else if. Если это бинарное дерево, оно либо равно, либо больше, либо меньше.

  3. Он попадает в Insert_helper или нет? Почему вы не включили это, кажется важным? Я предполагаю, что это заходит как минимум так далеко.

person Ted Johnson    schedule 11.10.2011
comment
Извините, это должно быть вставка, а не вставка_хелпер, и нет, это не позволяет вставить. Если я передаю tree_root как root, он всегда равен нулю и устанавливает root в newkey, но не в tree_root. - person HighLife; 11.10.2011

arrow_upward
0
arrow_downward 

root = newKey;

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

Правильный вариант будет выглядеть примерно так:

private:
void tree::insert_helper( key **root, key *newkey, int disc ) {
  if ( (*root) == NULL ) {
     *root = key;
  } else if (newkey->cord[disc] <= root->cord[disc]) {
     insert_helper( &((*root)->left), newkey, (disc+1)%4 );
  } else {
     insert_helper( &((*root)->right), newkey, (disc+1)%4);
  }
}

public:
void tree::insert( key *newKey, int disc ) {
    insert_helper( &tree_root, newkey, disc );
}

Также вы должны быть уверены, что конструкция 'key' устанавливает NULL для левого и правого. И конструктор дерева должен установить NULL для tree_root

person Ilya Denisov    schedule 11.10.2011