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

@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;

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

Новые блоги и статьи Все статьи Все блоги /
Модель здравосоХранения 6. ESG-повестка и устойчивое развитие; углублённый анализ кадрового бренда anaschu 31.03.2026 В прикрепленном документе раздумья о том, как можно поменять модель в будущем	10 пpимет, которые всегда сбываются Maks 31.03.2026 1. Чтобы, наконец, пришла маршрутка, надо закурить. Если сигарета последняя, маршрутка придет еще до второй затяжки даже вопреки расписанию. 2. Нaдоели зима и снег? Не надо переезжать. Достаточно. . .	Перемещение выделенных строк ТЧ из одного документа в другой Maks 31.03.2026 Реализация из решения ниже выполнена на примере нетипового документа "ВыдачаОборудованияНаСпецтехнику" с единственной табличной частью "ОборудованиеИКомплектующие" разработанного в конфигурации КА2. . . .	Functional First Web Framework Suave DevAlt 30.03.2026 Sauve. IO Апнулись до NET10. Из зависимостей один пакет, работает одинаково хорошо как в режиме проекта так и в интерактивном режиме. из сложностей - чисто функциональный подход. Решил. . .
Автоматическое создание документа при проведении другого документа Maks 29.03.2026 Реализация из решения ниже выполнена на нетиповых документах, разработанных в конфигурации КА2. Есть нетиповой документ "ЗаявкаНаРемонтСпецтехники" и нетиповой документ "ПланированиеСпецтехники". В. . .	Настройка движения справочника по регистру сведений Maks 29.03.2026 Решение ниже реализовано на примере нетипового справочника "ТарифыМобильнойСвязи" разработанного в конфигурации КА2, с целью учета корпоративной мобильной связи в коммерческом предприятии. . . .	Автозаполнение реквизита при выборе элемента справочника Maks 27.03.2026 Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. При выборе "Спецтехники" (Тип Справочник. Спецтехника), заполняется. . .	Сумматор с применением элементов трёх состояний. Hrethgir 26.03.2026 Тут. https:/ / fips. ru/ EGD/ ab3c85c8-836d-4866-871b-c2f0c5d77fbc Первый документ красиво выглядит, но без схемы. Это конечно не даёт никаких плюсов автору, но тем не менее. . . всё может быть. . .

@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