Функция должна возвращать указатель на новый корень дерева (упорядоченность не теряется). Меня интересует случай, когда 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;// Правый потомок};