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

Question

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

tree.h:

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 ++ и мне было интересно, как я могу исправить этот код, чтобы он правильно заполнил дерево?

Answer 1

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

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

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

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

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

Answer 2

root = newKey;

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

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

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 );
}

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

Answer 3

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

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

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