Указатель на новый узел в двоичном дереве - PullRequest
Новая
       51

Указатель на новый узел в двоичном дереве

0 голосов
/ 08 октября 2018

Я решал проблему вставки узла в двоичное дерево.У меня есть следующие сомнения:

1) Если мы вставляем узел, то мы должны вернуть указатель, указывающий на этот узел, поскольку только тогда мы сможем получить доступ к узлу, верно?

2) Тогда почему мы возвращаем root?Мы должны вернуть root->left или root->right соответственно, где я ошибаюсь? 

struct node* insert(struct node* root, int data)
    {
        if (root == NULL)    //If the tree is empty, return a new,single node
            return newNode(data);
        else
        {
            //Otherwise, recur down the tree 
            if (data <= root->data)
                root->left  = insert(root->left, data);
            else
                root->right = insert(root->right, data);
            return root;
        }
    }

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

Ответы [ 2 ]

0 голосов
/ 09 октября 2018

Вы неправильно понимаете возвращаемое значение.

Возвращаемое значение этой функции insert является указателем на поддерево, в которое теперь вставлено data.Если переданный в root был нулевым, это новое дерево 1 узла;если переданный в root не равен NULL, возвращаемое значение будет таким же root.

. Это делает рекурсию немного проще.Мы просто выполняем рекурсию, пока не встретимся с nullptr в ветке.Затем рекурсия останавливается, и возвращаемое значение устанавливает родительский узел left или right.

Чтобы создать новое дерево, введите: 

node* new_tree = insert(nullptr, 7);

, чтобы вставить что-либо всуществующее дерево, которое вы вводите: 

existing_tree = insert(existing_tree, 7);

или эквивалентно 

insert(existing_tree, 7);

, пока existing_tree не равно нулю.

Это «двойное использование» функции(как для создания, так и для изменения дерева) может сбить с толку, но это делает конкретное рекурсивное использование чуть менее многословным, и делает "пустое дерево пустым", а "всегда делать existing_tree = insert(existing_tree, val);" - это правило, которое делает пустое деревокак работает нулевое дерево.

Это, однако, очень простой способ ведения дел на языке Си.

Более совершенный способ ведения дел будет таким: 

std::unique_ptr<node> insert(std::unique_ptr<node> root, int data)
{
    if (root == nullptr)    //If the tree is empty, return a new,single node
        return std::make_unique<node>(data);
    else
    {
        //Otherwise, recur down the tree 
        if (data <= root->data)
            root->left  = insert(std::move(root->left), data);
        else
            root->right = insert(std::move(root->right), data);
        return std::move(root);
    }
}

, где поток данных в и из функции является более явным, и мы предполагаем, что node имеет конструктор, который принимает data.

0 голосов
/ 08 октября 2018

Эта рекурсивная вставка всегда должна возвращать самый корневой узел дерева.То, что вы прочитали return root, не означает, что исходный вызов функции завершился, просто означает, что n-я рекурсия завершилась.Все рекурсивные вызовы были помещены в стек и поэтому должны быть разрешены до того, как исходный вызывающий объект получит возвращенное значение.

Чтобы вернуться к вставленному узлу, выполните find для вставленного значения.

...