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

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

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

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

C++

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++

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;

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

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

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

@slipp1 13 / 12 / 9 Регистрация: 09.11.2012 Сообщений: 367 Записей в блоге: 1
	11.02.2013, 04:24 [ТС]	3
	Сообщение от nonedark2008 Берешь, удаляешь элемент корня, а на его место ставишь какой-нибудь лист дерева. Если у тебя бинарное дерево поиска, то после этого нужно дерево перестроить. как удалить? меня есть только ptr что вставить вместо него? 0

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

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

@Nixy ComfyMobile 401 / 282 / 34 Регистрация: 24.07.2012 Сообщений: 916
	11.02.2013, 16:25	14
	Сообщение от nonedark2008 Совершенно не верно. 1) Нужно найти лист дерева. 2) Переприсвоить указатели 3) Удалить старый корень. Т. е. все как я описпл выше. Если не понятно, то найди литературу по бинарным деревьям - там все есть. Например, книга Кормена. алгоритм есть,сделайте перерыв,в этом деле необходимо разобраться самим 0

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

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