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

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

Войти
Регистрация
Восстановить пароль
 
fishec
119 / 119 / 30
Регистрация: 07.09.2013
Сообщений: 338
#1

Создать бинарное дерево - C++

16.09.2013, 17:30. Просмотров 729. Ответов 7
Метки нет (Все метки)

Есть обычное дерево.
Узел описывается
struct nod
int Value;
int Number_Of_Sons;
nod *[5]Son

Число сыновей может быть до пяти.

Нужно написать рекурсивную функцию, которая создает из него бинарное дерево и возвращает указатель на корень. Подскажите пожалуйста алгоритм.
Изображения
  
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.09.2013, 17:30     Создать бинарное дерево
Посмотрите здесь:

Создать бинарное дерево - C++
Ребята, помогите с такое задачей : нужно написать ф-цию для построения бинарного дерево определенным способом, а именно : на входе есть...

Бинарное дерево - C++
дано целочисленнное бинарное дерево. найти: а)количество вершин дереваж б)значение самой левой вершины в правом поддереве в)...

Бинарное дерево - C++
пытаюсь самостоятельно разобраться с этим, но чето не выходит вот мой листинг. вроде кудато чтото вводит, но ничего не выводит....

Бинарное дерево из НЕ бинарного - C++
тащемта всё ясно из названия темы есть небинарное дерево -> надо сделать из него бинарное не могу понять, как быть, если в небинарном...

Бинарное дерево. Поиск. - C++
Здравствуйте. Дано задание, создать бинарное дерево с возможностью добавления, удаления элементов и поиск. Знаю, что тут ничего сложного и...

Бинарное дерево поиска - C++
Давайте рассмотрим некоторый пример Допустим есть числа от 0 до 99 которые добавляются в бинарное дерево Элементы в бинарное дерево...

Бинарное дерево поиска - C++
Всем привет! Не могу понять одну вещь. Есть вот такой код для заполнения бинарного дерева: #include <stdio.h> #include <stdlib.h> ...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Voivoid
674 / 277 / 12
Регистрация: 31.03.2013
Сообщений: 1,339
16.09.2013, 17:38     Создать бинарное дерево #2
Надо же, в коем-то веке более-менее интересная задачка
Кудаив
329 / 406 / 24
Регистрация: 27.05.2012
Сообщений: 1,165
Завершенные тесты: 2
16.09.2013, 17:49     Создать бинарное дерево #3
почему это g становится сыном f ?
fishec
119 / 119 / 30
Регистрация: 07.09.2013
Сообщений: 338
16.09.2013, 17:56  [ТС]     Создать бинарное дерево #4
Отец соединяется с левым сыном левой связью. Сыновья одного отца соединяются правыми связями
zer0mail
2330 / 1956 / 192
Регистрация: 03.07.2012
Сообщений: 7,013
Записей в блоге: 1
16.09.2013, 19:11     Создать бинарное дерево #5
Цитата Сообщение от fishec Посмотреть сообщение
Отец соединяется с левым сыном левой связью. Сыновья одного отца соединяются правыми связями
Этого вполне достаточно, чтобы написать программу.
fishec
119 / 119 / 30
Регистрация: 07.09.2013
Сообщений: 338
16.09.2013, 19:21  [ТС]     Создать бинарное дерево #6
Цитата Сообщение от zer0mail Посмотреть сообщение
Этого вполне достаточно, чтобы написать программу.
Можешь примерно в двух словах алгоритм обхода сказать, и какой порядок обхода, и где рекурсивно вызывать функцию? Я просто не могу понять, с чего начать вообще.
ya_noob
_
201 / 145 / 9
Регистрация: 08.10.2011
Сообщений: 432
16.09.2013, 19:39     Создать бинарное дерево #7
Код
функция(текущий узел):
    если нет узла, возвращаем NULL
    link = 0
    для каждого потомка текущего узла справа налево:
        temp = вызываем рекурсивно для него эту функцию
        правая ссылка очередного потомка = link
        link = temp
    левый потомок текущего узла = link
    возвратить ссылку на текущий узел
как видно из алгоритма (если хорошо приглядеться), функция открепляет всех правых потомков каждого узла внутри цикла а его правым потомком становится его ближайший правый брат (последнее действие происходит на один рекурсивный уровень выше) (этот ближайший брат хранится в переменной link). в конце link будет содержать левого потомка, его мы и сделаем (оставим) левым потомком узла

в цикле temp хранит каждого потомка, для которого выполняется рекурсивный вызов. рекурсивная функция возвращает ту же ссылку, что и была ей передана

кто такие правый и левый потомки реши сам, это может быть Son[0] и Son[1], либо добавь в структуру пару дополнительных ссылок, либо параллельно с обходом дерева создавай новую структуры (что более логично) (получится, что бинарное дерево формируется в порядке правый->левый->корень, т.е. в соответствии с обратным обходом дерева)
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.09.2013, 20:08     Создать бинарное дерево
Еще ссылки по теме:

Бинарное дерево поиска - C++
В текстовом файле содержится произвольный текст. Построить на его основе бинарное дерево поиска, каждый узел которого содержит слово....

Бинарное дерево поиска C++ - C++
+Доброго времени суток! У меня есть задание:создать картотеку,в ней указать тип магазина,номер магазина,ключ,и адрес магазина.Такое...

Переделать в бинарное дерево - C++
#include <iostream> #include <conio.h> using namespace std; struct Node{ int info; Node* next; }; class Spisok { ...

Бинарное дерево с шаблоном - C++
Пишу бинарное дерево типа BST<Key, Value>. Значениями хочу сделать любые типы данных. По-этому пришол к шаблонам, но с реализацией не...

Бинарное дерево поиска - C++
Решил написать бинарное дерево поиска, но что-то пошло не так, дерево не выводиться не понимаю почему. Вот весь код: #include...


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

Или воспользуйтесь поиском по форуму:
fishec
119 / 119 / 30
Регистрация: 07.09.2013
Сообщений: 338
16.09.2013, 20:08  [ТС]     Создать бинарное дерево #8
Спасибо, буду разбираться.
Да нужно создать новое дерево отдельно, а не переделывать его. Есть функция "НовыйУзел" с аргументом (указатель на узел исходного дерева), создающая узел типа нового дерева, копирует данные, и возвращает указатель на созданный узел. Куда в этом алгоритме создание вставить?
Yandex
Объявления
16.09.2013, 20:08     Создать бинарное дерево
Ответ Создать тему
Опции темы

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