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

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

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

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

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

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

как удалить этот корень?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.02.2013, 03:56
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Удаление корня двоичного дерева (C++):

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

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

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

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

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

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

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

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

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
15
Yandex
Объявления
11.02.2013, 16:29
Ответ Создать тему
Опции темы

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