0

Функция должна возвращать указатель на новый корень дерева (упорядоченность не теряется). Меня интересует случай, когда node->left и node->right не равны NULL. Сохраняю правое поддерево во временной переменной-указателе. В старый указатель на корень записываю указатель на правое поддерево (корень правого поддерева становится новым корнем всего дерева). После этого имею правое поддерево в качестве основного и отдельно левое поддерево. Прохожу в правом поддереве до минимального элемента (иду по ветке влево, пока не дойду до конца). И после последнего вставляю хранимое в переменной левое дерево (вставляю в node->left). Все, кроме этого работает, проверял, тестил.

Проблема в том, что у меня не получается присвоить это левое поддерево. Наверное, это нужно делать через адрес или двойной указатель (гадать не буду...). Подскажите, пожалуйста, как сделать, чтобы левое поддерево было в node при возврате значения функцией (пока что возвращает правое поддерево. Буду благодарен замечаниям по теории, что посмотреть по указателям, чтобы не путаться и, конечно, ответу на вопрос.

работа функции

Код:

tnode* deleteRootSubTree(tnode* node) {
if (node != NULL) {
    cout << "removing from root" << endl;

    if (node->left == NULL && node->right == NULL) {
        return NULL;
    }
    if (node->left != NULL && node->right == NULL) {
        node = node->left;// Присваиваем корню левую часть дерева (от корня)
        return node;
    }
    if (node->left == NULL && node->right != NULL) {
        node = node->right;// Присваиваем корню правую часть дерева (от корня)
        return node;
    }
    if (node->left != NULL && node->right != NULL) {
        tnode* left_node = node->left;// Сохраняем левую часть дерева (от корня)
        node = node->right;// Присваиваем корню правую часть дерева (от корня)
        //нужно левую часть дерева вставить после наименьшего элемента в дереве 
        
        tnode* tmp = node;// Временный узел для прохода по ветке
        while (tmp) {
            tmp = (tmp)->left;
        }
        tmp = left_node;*****// ТУТ ОШИБКА: left_node теряется, тут я неправильно присваиваю левое поддерево*****
        return node;
    }
    
    
    return node;// = *left_node;//<последний наименьший элемент в правом дереве>->left = бывшее левое дерево
    
}
else node;}

Структура дерева

struct tnode {// Узел дерева
int key;// Ключ
int level;//уровень
struct tnode* left;// Левый потомок
struct tnode* right;// Правый потомок};
2
  • А как вы поняли, что функция работает не правильно? Я понял как вы хотите, но не понимаю что вы в итоге получаете. Как понять "ТУТ ОШИБКА: left_node теряется, тут я неправильно присваиваю левое поддерево" 16 мар 2021 в 19:00
  • в итоге я получал неправильно сформированное дерево (в нём не было левого поддерева) 17 мар 2021 в 4:06

1 ответ 1

2

Цикл while доходит до NULL. А вам нужен последний элемент перед NULL. К нему и нужно подвесить поддерево. Поправьте код так чтобы он смотрел на один узел вперёд:

tnode* tmp = node;// Временный узел для прохода по ветке
while (tmp->left != NULL) {
    tmp = tmp->left;
}
tmp->left = left_node;
1
  • Спасибо, помогло 17 мар 2021 в 4:05

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.