Удаление корня двоичного дерева

@slipp1 · Регистрация: 09.11.2012

Студворк — интернет-сервис помощи студентам

двоичное дерево состоит только из

C++
1
ptr

корень двоичного дерева

как удалить этот корень?

@nonedark2008 · 11.02.2013, 04:08

Берешь, удаляешь элемент корня, а на его место ставишь какой-нибудь лист дерева. Если у тебя бинарное дерево поиска, то после этого нужно дерево перестроить.

@slipp1 · 11.02.2013, 04:24 **[ТС]**

Сообщение от nonedark2008

Берешь, удаляешь элемент корня, а на его место ставишь какой-нибудь лист дерева. Если у тебя бинарное дерево поиска, то после этого нужно дерево перестроить.

как удалить?
меня есть только ptr что вставить вместо него?

@nonedark2008 · 11.02.2013, 05:02

ptr - это указатель на вершину, у любого узла дерева есть 3 указателя: на левый и правый дочерние и на родителя. У корня дерева указатель на родителя NULL. После удаления корня, чтобы не перестраивать все дерево целиком, можно вместо корня поставить другой элемент этого дерева. Проще всего подставить лист дерева. ptr указывает на корень. Перенаправляем его на выбранный лист, у родителя листа ставим указатель на левый/правый в NULL(зависит от того каким дочерним является лист по отношению к родителю). А правый и левый у листа ставим как и у старого корня. А затем освобождаем память из под старого корня. Т.е. в итоге мы заменили корень на лист дерева, а потом удалили старый корень.

@slipp1 · 11.02.2013, 13:15 **[ТС]**

Сообщение от nonedark2008

ptr - это указатель на вершину, у любого узла дерева есть 3 указателя: на левый и правый дочерние и на родителя. У корня дерева указатель на родителя NULL. После удаления корня, чтобы не перестраивать все дерево целиком, можно вместо корня поставить другой элемент этого дерева. Проще всего подставить лист дерева. ptr указывает на корень. Перенаправляем его на выбранный лист, у родителя листа ставим указатель на левый/правый в NULL(зависит от того каким дочерним является лист по отношению к родителю). А правый и левый у листа ставим как и у старого корня. А затем освобождаем память из под старого корня. Т.е. в итоге мы заменили корень на лист дерева, а потом удалили старый корень.

C++
1
2
3
4
5
6
7
TreeNode<NODETYPE>* Node=ptr->leftPtr;
ptr=ptr->leftPtr;
        
ptr->leftPtr=0;
        
Node->leftPtr=ptr->leftPtr;
Node->rightPtr=ptr->rightPtr;

если сделал так то не получаетсо

Добавлено через 7 часов 37 минут
up?

@nonedark2008 · 11.02.2013, 14:09

Совершенно не верно. 1) Нужно найти лист дерева. 2) Переприсвоить указатели 3) Удалить старый корень.
Т. е. все как я описпл выше. Если не понятно, то найди литературу по бинарным деревьям - там все есть. Например, книга Кормена.

@slipp1 · 11.02.2013, 15:58 **[ТС]**

Сообщение от nonedark2008

Совершенно не верно. 1) Нужно найти лист дерева. 2) Переприсвоить указатели 3) Удалить старый корень.
Т. е. все как я описпл выше. Если не понятно, то найди литературу по бинарным деревьям - там все есть. Например, книга Кормена.

C++
1
ptr=ptr->leftPtr; - Перенаправляем его на выбранный лист

C++
1
ptr->leftPtr=0; - у родителя листа ставим указатель на левый/правый в NULL

C++
1
2
Node->leftPtr=ptr->leftPtr; - правый и 
Node->rightPtr=ptr->rightPtr; - левый у листа ставим как и у старого корня

что ж не так?

@Nixy · 11.02.2013, 16:04

ну вам же уже сказали что неверно рассуждаете,

C++
1
ptr=ptr->leftPtr; - Перенаправляем его на выбранный лист

после этого действия если не запомнить ptr то корень утечет

@slipp1 · 11.02.2013, 16:07 **[ТС]**

Сообщение от Nixy

ну вам же уже сказали что неверно рассуждаете,

C++
1
ptr=ptr->leftPtr; - Перенаправляем его на выбранный лист

после этого действия если не запомнить ptr то корень утечет

извеняюсь как запомнить?

@nonedark2008 · 11.02.2013, 16:11

Запоминается в некую временную переменную. Лист дерева - это элемент, у которого нет дочерних. А объяснять теорию по деревьям слишком долго и влом. Так что, имхо - бери книгу, открывай нужную главу и читай, а Кормен есть в открытом доступе в инете.

@slipp1 · 11.02.2013, 16:14 **[ТС]**

Сообщение от nonedark2008

Запоминается в некую временную переменную. Лист дерева - это элемент, у которого нет дочерних. А объяснять теорию по деревьям слишком долго и влом. Так что, имхо - бери книгу, открывай нужную главу и читай, а Кормен есть в открытом доступе в инете.

это не есть временная переменная которая является листом?

C++
1
TreeNode<NODETYPE>* Node=ptr->leftPtr;

@Nixy · 11.02.2013, 16:18

так вот в Node а не в ptr , вы сами то хоть просматривайте что пишите
тогда

C++
1
2
3
Node = ptr->leftPtr;
Node->leftPtr=ptr->leftPtr; - правый и 
Node->rightPtr=ptr->rightPtr; - левый у листа ставим как и у старого корня

сами заметите ошибку?

@slipp1 · 11.02.2013, 16:22 **[ТС]**

Сообщение от Nixy

так вот в Node а не в ptr , вы сами то хоть просматривайте что пишите
тогда

C++
1
2
3
Node = ptr->leftPtr;
Node->leftPtr=ptr->leftPtr; - правый и 
Node->rightPtr=ptr->rightPtr; - левый у листа ставим как и у старого корня

сами заметите ошибку?

ребъЯта я запуталсо...

@Nixy · 11.02.2013, 16:25

Сообщение от nonedark2008

Совершенно не верно. 1) Нужно найти лист дерева. 2) Переприсвоить указатели 3) Удалить старый корень.
Т. е. все как я описпл выше. Если не понятно, то найди литературу по бинарным деревьям - там все есть. Например, книга Кормена.

алгоритм есть,сделайте перерыв,в этом деле необходимо разобраться самим

@slipp1 · 11.02.2013, 16:29 **[ТС]**

C++
1
1) Нужно найти лист дерева

зачем искать лист, дерево пусто, есть только корень, единственные варианты с листами на которые можно сослаться это левый и правые потомки корня.

@Nixy · 11.02.2013, 16:33

дерево пусто,

или же

единственные варианты с листами на которые можно сослаться это левый и правые потомки корня.

вы определитесь, если есть потомки, и слева и права что то есть, то тогда надо, 1 запомнить адрес корня, потом в ту переменную в который был корень занести лево/право а потом удалять корень через временную переменную

@slipp1 · 11.02.2013, 16:40 **[ТС]**

Сообщение от Nixy

или же вы определитесь, если есть потомки

потомков нет, в дереве остался только корень - одно значение.

Добавлено через 4 минуты

Сообщение от Nixy

или же вы определитесь, если есть потомки, и слева и права что то есть, то тогда надо, 1 запомнить адрес корня, потом в ту переменную в который был корень занести лево/право а потом удалять корень через временную переменную

C++
1
2
3
TreeNode<NODETYPE>* node=ptr;
        ptr=ptr->leftPtr;
        delete node;

@Nixy · 11.02.2013, 17:19

если дерево уже пустое, то и удаляй просто так

Добавлено через 1 минуту
тебе же говорят о том что если оно не пустое, а корень надо убрать то выбирается лист в качестве корня,заменяется,а корень чтоб удалить надо запомнить,если и так все пусто, то и вопрос глупый

@slipp1 · 11.02.2013, 17:22 **[ТС]**

корень передавал фун-ии по ссылке

в корне число 49, левый и правый потомки равны нулю (их нет)

просто обнулил корень

варианты удаления, работает:
1.

C++
1
(*ptr)=NULL;

2.

C++
1
rootPtr=0;

3.

C++
1
(*ptr)=(*ptr)->leftPtr;

и т.д.

что есть не правильным с точки зрения внутренностей, памяти и т.п.??

@Nixy · 11.02.2013, 17:23

C++
1
(*ptr)=(*ptr)->leftPtr;

вот это неверно

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .

@nonedark2008 1394 / 1023 / 325 Регистрация: 28.07.2012 Сообщений: 2,813
	11.02.2013, 04:08
	Берешь, удаляешь элемент корня, а на его место ставишь какой-нибудь лист дерева. Если у тебя бинарное дерево поиска, то после этого нужно дерево перестроить. 0

@nonedark2008 1394 / 1023 / 325 Регистрация: 28.07.2012 Сообщений: 2,813
	11.02.2013, 05:02
	ptr - это указатель на вершину, у любого узла дерева есть 3 указателя: на левый и правый дочерние и на родителя. У корня дерева указатель на родителя NULL. После удаления корня, чтобы не перестраивать все дерево целиком, можно вместо корня поставить другой элемент этого дерева. Проще всего подставить лист дерева. ptr указывает на корень. Перенаправляем его на выбранный лист, у родителя листа ставим указатель на левый/правый в NULL(зависит от того каким дочерним является лист по отношению к родителю). А правый и левый у листа ставим как и у старого корня. А затем освобождаем память из под старого корня. Т.е. в итоге мы заменили корень на лист дерева, а потом удалили старый корень. 0

@nonedark2008 1394 / 1023 / 325 Регистрация: 28.07.2012 Сообщений: 2,813
	11.02.2013, 14:09
	Совершенно не верно. 1) Нужно найти лист дерева. 2) Переприсвоить указатели 3) Удалить старый корень. Т. е. все как я описпл выше. Если не понятно, то найди литературу по бинарным деревьям - там все есть. Например, книга Кормена. 0

@nonedark2008 1394 / 1023 / 325 Регистрация: 28.07.2012 Сообщений: 2,813
	11.02.2013, 16:11
	Запоминается в некую временную переменную. Лист дерева - это элемент, у которого нет дочерних. А объяснять теорию по деревьям слишком долго и влом. Так что, имхо - бери книгу, открывай нужную главу и читай, а Кормен есть в открытом доступе в инете. 0

@Nixy ComfyMobile 401 / 282 / 34 Регистрация: 24.07.2012 Сообщений: 916
	11.02.2013, 17:19
	если дерево уже пустое, то и удаляй просто так Добавлено через 1 минуту тебе же говорят о том что если оно не пустое, а корень надо убрать то выбирается лист в качестве корня,заменяется,а корень чтоб удалить надо запомнить,если и так все пусто, то и вопрос глупый 0