Нужно объяснение работы кода

Question

Метод добавления элемента в бинарное дерево. В основном у меня путаница с двойными указателями, значками * и &. И хотелось бы понять как все-таки работает этот код

template <typename T>
void BinaryTree<T>::insert(T data){
    TreeNode<T>** current = &tree;
    while (*current){
        TreeNode<T>& node = **current;
        if (data < node.data){
            current = &node.left;
        }
        else if (data > node.data){
            current = &node.right;
        }
        else{
            return;
        }
    }
    *current = new TreeNode<T>(data);
}

Переменная tree типа TreeNode — корень дерева.

Узел дерева:

template <typename T>
class TreeNode{
public:
    T data;  // T - тип данных

    // Указатели на левых и правых потомнов
    TreeNode<T> *left;
    TreeNode<T> *right
}

Answer 1

Ну в принципе ничего сложного. Просто у новичков обычно путаница с двойными указателями.
Ограничения из кода:

дерево бинарное - у узла может быть только 2 потомка
в дерево не вставляются дубликаты, т.е. не может быть 2-х одинаковых узлов
где-то при создании объектов класса TreeNode<T> должны обнуляться указатели на потомков
типы, передаваемые в шаблон, должны иметь operator<() и operator>()

// в функцию передается копия объекта
// наверное лучше было бы передавать ссылку или указатель
void BinaryTree<T>::insert(T data)
{
// делаем локальный указатель на указатель и присваиваем ему значение корневого узла дерева
    TreeNode<T>** current = &tree;
// tree - должен быть указателем на вершину дерева
// указатель на указатель нужен для того, чтобы изменяя значение `*current`
// изменения записывались в дерево

// обход по дереву, пока значение указателя не равно 0, т.е. пока не дойдет до узла, не имеющего потомков
    while (*current) 
    {
        // создается ссылка, видимо автору так удобнее
        // вместо `node.data` можно писать '(*current)->data'
        TreeNode<T>& node = **current;
        
        // если узел (значение) меньше текущего, то `current` указывает на указатель на левого потомка
        if (data < node.data) 
            current = &node.left;
        else 
        // если узел (значение) больше текущего, то `current` указывает на указатель на правого потомка
        if (data > node.data)
            current = &node.right;
        else
        // если значения равны - не делать ничего и выйти из функции
            return;
    }
    // цикл заканчивается, когда переданное в функцию значение меньше или больше значения текущего узла, но потомков у него нет
    // `current` указывает на указатель на левого или правого потомка
    // создается узел и поскольку `current` указатель на указатель, 
    // присваивание `*current =` изменяет указатель на потомка в узле дерева
    *current = new TreeNode<T>(data);
    // т.е. `*current =` аналогично `node.left =`или `node.right =`
}

То же самое, но с одинарным указателем и без ссылки

template <typename T>
void BinaryTree<T>::insert(T data)
{
    TreeNode<T>* current = tree;
    while (true)
    {
        if(data == current->data)
            return;

        if (data < current->data)
        {
            if(current->left == 0)
                current->left = new TreeNode<T>(data);
                // здесь можно вставить `break;`, чтобы выйти из цикла
            current = current->left;  // или отправиться на следующую итерацию
        }
        else 
        {
            if(current->right == 0)
                current->right = new TreeNode<T>(data);            
            current = current->right; 
        }
    }    
}

БЛОГ НА HUSL

Нужно объяснение работы кода

Ответы (1 шт):