Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 20, средняя оценка - 4.85
slipp1
13 / 12 / 1
Регистрация: 09.11.2012
Сообщений: 366
Записей в блоге: 1
#1

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

11.02.2013, 03:56. Просмотров 2742. Ответов 22
Метки нет (Все метки)

двоичное дерево состоит только из
C++
1
ptr
корень двоичного дерева

как удалить этот корень?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.02.2013, 03:56     Удаление корня двоичного дерева
Посмотрите здесь:

Пример двоичного дерева - C++
Здравствуйте! Возникла мысль попробовать реализовать двоичное дерево в c++ для этого решил сначала рассмотреть какие-нибудь примеры в...

Алгоритм реализации двоичного дерева - C++
Нужно написать реализацию двоичного дерева с использованием шаблонов в упрощенном виде следуя конвенциям STL контейнеров. Основные...

Проверка корректности двоичного дерева - C++
Здравствуйте! Задача такая, Свойство двоичного дерева поиска можно сформулировать следующим образом: для каждой вершины дерева V...

Вывести все вершины двоичного дерева - C++
Двоичное дерево задано в виде: m,g],s,y]] Как с помощью стека вывести это на экран? Набросайте, кому не трудно алгоритм) просто...

Помогите сделать обход двоичного дерева - C++
Есть некий проект (большой, несколько файлов), где происходит процессы со списком (добавление, удаление и т. д.). Структура: /** *...

Как можно совершить обход двоичного дерева нерекурсивно - C++
Доброго времени суток. Хочу поинтересоваться: как можно совершить обход двоичного дерева нерекурсивно(!!!), желательно с примерами или...

Создать класс [B]TreeChar[/B], для работы с элементами двоичного дерева - C++
Создать класс TreeChar, для работы с элементами двоичного дерева ASCII-символов. В качестве членов-данных рекомендуется брать элементы...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
nonedark2008
887 / 626 / 126
Регистрация: 28.07.2012
Сообщений: 1,687
11.02.2013, 04:08     Удаление корня двоичного дерева #2
Берешь, удаляешь элемент корня, а на его место ставишь какой-нибудь лист дерева. Если у тебя бинарное дерево поиска, то после этого нужно дерево перестроить.
slipp1
13 / 12 / 1
Регистрация: 09.11.2012
Сообщений: 366
Записей в блоге: 1
11.02.2013, 04:24  [ТС]     Удаление корня двоичного дерева #3
Цитата Сообщение от nonedark2008 Посмотреть сообщение
Берешь, удаляешь элемент корня, а на его место ставишь какой-нибудь лист дерева. Если у тебя бинарное дерево поиска, то после этого нужно дерево перестроить.
как удалить?
меня есть только ptr что вставить вместо него?
nonedark2008
887 / 626 / 126
Регистрация: 28.07.2012
Сообщений: 1,687
11.02.2013, 05:02     Удаление корня двоичного дерева #4
ptr - это указатель на вершину, у любого узла дерева есть 3 указателя: на левый и правый дочерние и на родителя. У корня дерева указатель на родителя NULL. После удаления корня, чтобы не перестраивать все дерево целиком, можно вместо корня поставить другой элемент этого дерева. Проще всего подставить лист дерева. ptr указывает на корень. Перенаправляем его на выбранный лист, у родителя листа ставим указатель на левый/правый в NULL(зависит от того каким дочерним является лист по отношению к родителю). А правый и левый у листа ставим как и у старого корня. А затем освобождаем память из под старого корня. Т.е. в итоге мы заменили корень на лист дерева, а потом удалили старый корень.
slipp1
13 / 12 / 1
Регистрация: 09.11.2012
Сообщений: 366
Записей в блоге: 1
11.02.2013, 13:15  [ТС]     Удаление корня двоичного дерева #5
Цитата Сообщение от 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
887 / 626 / 126
Регистрация: 28.07.2012
Сообщений: 1,687
11.02.2013, 14:09     Удаление корня двоичного дерева #6
Совершенно не верно. 1) Нужно найти лист дерева. 2) Переприсвоить указатели 3) Удалить старый корень.
Т. е. все как я описпл выше. Если не понятно, то найди литературу по бинарным деревьям - там все есть. Например, книга Кормена.
slipp1
13 / 12 / 1
Регистрация: 09.11.2012
Сообщений: 366
Записей в блоге: 1
11.02.2013, 15:58  [ТС]     Удаление корня двоичного дерева #7
Цитата Сообщение от 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
ComfyMobile
400 / 281 / 8
Регистрация: 24.07.2012
Сообщений: 916
11.02.2013, 16:04     Удаление корня двоичного дерева #8
ну вам же уже сказали что неверно рассуждаете,
C++
1
ptr=ptr->leftPtr; - Перенаправляем его на выбранный лист
после этого действия если не запомнить ptr то корень утечет
slipp1
13 / 12 / 1
Регистрация: 09.11.2012
Сообщений: 366
Записей в блоге: 1
11.02.2013, 16:07  [ТС]     Удаление корня двоичного дерева #9
Цитата Сообщение от Nixy Посмотреть сообщение
ну вам же уже сказали что неверно рассуждаете,
C++
1
ptr=ptr->leftPtr; - Перенаправляем его на выбранный лист
после этого действия если не запомнить ptr то корень утечет
извеняюсь как запомнить?
nonedark2008
887 / 626 / 126
Регистрация: 28.07.2012
Сообщений: 1,687
11.02.2013, 16:11     Удаление корня двоичного дерева #10
Запоминается в некую временную переменную. Лист дерева - это элемент, у которого нет дочерних. А объяснять теорию по деревьям слишком долго и влом. Так что, имхо - бери книгу, открывай нужную главу и читай, а Кормен есть в открытом доступе в инете.
slipp1
13 / 12 / 1
Регистрация: 09.11.2012
Сообщений: 366
Записей в блоге: 1
11.02.2013, 16:14  [ТС]     Удаление корня двоичного дерева #11
Цитата Сообщение от nonedark2008 Посмотреть сообщение
Запоминается в некую временную переменную. Лист дерева - это элемент, у которого нет дочерних. А объяснять теорию по деревьям слишком долго и влом. Так что, имхо - бери книгу, открывай нужную главу и читай, а Кормен есть в открытом доступе в инете.
это не есть временная переменная которая является листом?
C++
1
TreeNode<NODETYPE>* Node=ptr->leftPtr;
Nixy
ComfyMobile
400 / 281 / 8
Регистрация: 24.07.2012
Сообщений: 916
11.02.2013, 16:18     Удаление корня двоичного дерева #12
так вот в Node а не в ptr , вы сами то хоть просматривайте что пишите
тогда
C++
1
2
3
Node = ptr->leftPtr;
Node->leftPtr=ptr->leftPtr; - правый и 
Node->rightPtr=ptr->rightPtr; - левый у листа ставим как и у старого корня
сами заметите ошибку?
slipp1
13 / 12 / 1
Регистрация: 09.11.2012
Сообщений: 366
Записей в блоге: 1
11.02.2013, 16:22  [ТС]     Удаление корня двоичного дерева #13
Цитата Сообщение от Nixy Посмотреть сообщение
так вот в Node а не в ptr , вы сами то хоть просматривайте что пишите
тогда
C++
1
2
3
Node = ptr->leftPtr;
Node->leftPtr=ptr->leftPtr; - правый и 
Node->rightPtr=ptr->rightPtr; - левый у листа ставим как и у старого корня
сами заметите ошибку?

ребъЯта я запуталсо...
Nixy
ComfyMobile
400 / 281 / 8
Регистрация: 24.07.2012
Сообщений: 916
11.02.2013, 16:25     Удаление корня двоичного дерева #14
Цитата Сообщение от nonedark2008 Посмотреть сообщение
Совершенно не верно. 1) Нужно найти лист дерева. 2) Переприсвоить указатели 3) Удалить старый корень.
Т. е. все как я описпл выше. Если не понятно, то найди литературу по бинарным деревьям - там все есть. Например, книга Кормена.
алгоритм есть,сделайте перерыв,в этом деле необходимо разобраться самим
slipp1
13 / 12 / 1
Регистрация: 09.11.2012
Сообщений: 366
Записей в блоге: 1
11.02.2013, 16:29  [ТС]     Удаление корня двоичного дерева #15
C++
1
1) Нужно найти лист дерева
зачем искать лист, дерево пусто, есть только корень, единственные варианты с листами на которые можно сослаться это левый и правые потомки корня.
Nixy
ComfyMobile
400 / 281 / 8
Регистрация: 24.07.2012
Сообщений: 916
11.02.2013, 16:33     Удаление корня двоичного дерева #16
дерево пусто,
или же
единственные варианты с листами на которые можно сослаться это левый и правые потомки корня.
вы определитесь, если есть потомки, и слева и права что то есть, то тогда надо, 1 запомнить адрес корня, потом в ту переменную в который был корень занести лево/право а потом удалять корень через временную переменную
slipp1
13 / 12 / 1
Регистрация: 09.11.2012
Сообщений: 366
Записей в блоге: 1
11.02.2013, 16:40  [ТС]     Удаление корня двоичного дерева #17
Цитата Сообщение от Nixy Посмотреть сообщение
или же вы определитесь, если есть потомки
потомков нет, в дереве остался только корень - одно значение.

Добавлено через 4 минуты
Цитата Сообщение от Nixy Посмотреть сообщение
или же вы определитесь, если есть потомки, и слева и права что то есть, то тогда надо, 1 запомнить адрес корня, потом в ту переменную в который был корень занести лево/право а потом удалять корень через временную переменную
C++
1
2
3
TreeNode<NODETYPE>* node=ptr;
        ptr=ptr->leftPtr;
        delete node;
Nixy
ComfyMobile
400 / 281 / 8
Регистрация: 24.07.2012
Сообщений: 916
11.02.2013, 17:19     Удаление корня двоичного дерева #18
если дерево уже пустое, то и удаляй просто так

Добавлено через 1 минуту
тебе же говорят о том что если оно не пустое, а корень надо убрать то выбирается лист в качестве корня,заменяется,а корень чтоб удалить надо запомнить,если и так все пусто, то и вопрос глупый
slipp1
13 / 12 / 1
Регистрация: 09.11.2012
Сообщений: 366
Записей в блоге: 1
11.02.2013, 17:22  [ТС]     Удаление корня двоичного дерева #19
корень передавал фун-ии по ссылке

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

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

варианты удаления, работает:
1.
C++
1
(*ptr)=NULL;
2.
C++
1
rootPtr=0;
3.
C++
1
(*ptr)=(*ptr)->leftPtr;
и т.д.

что есть не правильным с точки зрения внутренностей, памяти и т.п.??
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.02.2013, 17:23     Удаление корня двоичного дерева
Еще ссылки по теме:

Англо-русский словарь построен в виде двоичного дерева в программе с++ - C++
Англо-русский словарь построен в виде двоичного дерева. Каждая компонента содержит английское слово, соответствующее ему русское слово и...

Частотный словарь из слов текстового файла в виде дерева двоичного поиска - C++
Задача: Построить частотный словарь из слов текстового файла в виде дерева двоичного поиска. Вывести его на экран в виде дерева....

Написать рекурсивную процедуру, которая печатает ключи всех вершин двоичного дерева - C++
Необходимо написать рекурсивную процедуру, которая печатает ключи всех вершин двоичного дерева. Двоичное дерево задастся в файле в...

Удаление вершин дерева - C++
Здравствуйте! Помогите в решении задачи. Записи вершин 2-3–дерева – вещественные числа. Описать процедуру, которая удаляет все вершины со...

Удаление узла из дерева - C++
сделав функции добавления,поиска,пару обходов и вывод ввиде дерева в консоли(жаль что нельзя размер по x изменить) при тестировании...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Nixy
ComfyMobile
400 / 281 / 8
Регистрация: 24.07.2012
Сообщений: 916
11.02.2013, 17:23     Удаление корня двоичного дерева #20
C++
1
(*ptr)=(*ptr)->leftPtr;
вот это неверно
Yandex
Объявления
11.02.2013, 17:23     Удаление корня двоичного дерева
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru