0 / 0 / 0
Регистрация: 23.11.2014
Сообщений: 20
Записей в блоге: 2
1

Исходное бинарное дерево превратить в бинарное дерево поиска, при этом сохранив его структуру

29.03.2015, 00:29. Показов 5083. Ответов 2
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Помогите, не могу понять!(
Нужно исходное бинарное дерево превратить в бинарное дерево поиска, при этом сохранив его структуру.
вот пример вход:
Исходное бинарное дерево превратить в бинарное дерево поиска, при этом сохранив его структуру

вот выход:
Исходное бинарное дерево превратить в бинарное дерево поиска, при этом сохранив его структуру

вот как подается входной файл:
Исходное бинарное дерево превратить в бинарное дерево поиска, при этом сохранив его структуру

Узел 10 является листом, поэтому чтобы обозначить это во входном файле указывается, что оба его потенциальных потомки отсутствуют - после 10 идет два нуля (0 0). Далее в файле идет еще один 0, который указывает на отсутствие правого потомка для узла 6.
0
29.03.2015, 00:29
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
29.03.2015, 00:29
Ответы с готовыми решениями:

Преобразовать идеальное бинарное дерево в бинарное дерево поиска
Всем привет, я создал идельное бинарное дерево и написал к нему функции. Как мне теперь можно преобразовать его в бинарное дерево поиска?...

Данные из массива структур Date передать в бинарное дерево поиска и вывести его при помощи обратного обхода
Доброго времени суток! Задание:Данные из массива структур Date передать в бинарное дерево поиска и вывести его при помощи обратного...

Бинарное дерево. Ссылка на структуру
Строю бинарное дерево. Узлы - структуры. Сортировка будет по номеру рейса. Как сделать ссылку на структуру внутри этой же структуры? Ссылки...

2
_Ivana
29.03.2015, 14:54
  #2

Не по теме:

Haskell
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
data Tree a = Z | N (Tree a) a (Tree a) deriving Show
 
l2t = fst . go where
    go []     = (Z, [])
    go (0:xs) = (Z, xs)
    go (x:xs) = (N l x r, xr) where (l,xl) = go xs; (r,xr) = go xl
 
t2l Z         = [0]
t2l (N l a r) = a : t2l l ++ t2l r
 
lftCnt Z         = Z
lftCnt (N l a r) = N (lftCnt l) (leaves l) (lftCnt r) where
    leaves Z         = 0
    leaves (N l a r) = 1 + leaves l + leaves r
 
bld _ Z         = Z
bld v (N l a r) = N (bld vl l) (head vr) (bld (tail vr) r) where (vl, vr) = splitAt a v
 
res l = t2l . bld (sort . filter (/=0) $ l) . lftCnt . l2t $ l
 
main = print $ res [1,4,6,10,0,0,0,7,0,8,0,0,2,5,0,0,3,9,0,0,0]
[6,3,2,1,0,0,0,4,0,5,0,0,8,7,0,0,10,9,0,0,0]

Небольшой апдейт - считать количество листьев лучше сразу при построении дерева, а не потом пробегаясь по нему снова. И кот короче.
Haskell
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
data Tree a = Z | N (Tree a) a (Tree a) deriving Show
 
l2t = (\(t,_,_) -> t) . go where
    go (0:xs) = (Z, xs, 0)
    go (x:xs) = (N l nl r, xr, nl+nr+1) where (l,xl,nl) = go xs; (r,xr,nr) = go xl
 
t2l Z         = [0]
t2l (N l a r) = a : t2l l ++ t2l r
 
bld _ Z         = Z
bld v (N l a r) = N (bld vl l) h (bld vr r) where (vl, h:vr) = splitAt a v
 
res l = t2l . bld (sort . filter (/=0) $ l) . l2t $ l
 
main = print $ res [1,4,6,10,0,0,0,7,0,8,0,0,2,5,0,0,3,9,0,0,0]

0
Супер-модератор
Эксперт Pascal/DelphiАвтор FAQ
 Аватар для volvo
33069 / 21371 / 8210
Регистрация: 22.10.2011
Сообщений: 36,688
Записей в блоге: 9
30.03.2015, 10:23 3
Евгений2395, здесь было: http://www.geeksforgeeks.org/b... onversion/
0
30.03.2015, 10:23
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
30.03.2015, 10:23
Помогаю со студенческими работами здесь

Бинарное дерево поиска
Дали такую задачу: Дан набор попарно не равных целых чисел, по ним строится бинарное дерево поиска. Нужно осуществить обход дерева и...

Бинарное дерево поиска
Напечатать элементы дерева с указанием их уровня в порядке возрастания уровней

Бинарное дерево поиска
#include "iostream" #include "math.h" #include "windows.h" using namespace std; struct Node { char info; int k; ...

Бинарное дерево поиска
Необходимо реализовать структуру данных "бинарное дерево поиска" для целых чисел без балансировки. Реализация включает функции: ...

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


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

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему

Редактор формул (кликните на картинку в правом углу, чтобы закрыть)
Опции темы

Новые блоги и статьи
Пользуясь нейросетью возвращаюсь к вопросу альтернативных приводов поступательного движения.
Hrethgir 14.02.2025
Описание тут https:/ / habr. com/ ru/ articles/ 778118/ . Вопрос ответ You Привет. Скажи, есть-ли вещества, которые могут менять жидкое состояние на желеобразное под воздействием ультразвука? . . .
Ошибка "Another git process seems to be running in this repository"
hw_wired 14.02.2025
При работе с git можно столкнуться с довольно раздражающей ошибкой "Another git process seems to be running in this repository". Эта ситуация возникает, когда система контроля версий пытается. . .
Ошибка "java.lang.NoCl­assDefFou­ndErro­r: javax/xml/bind/JAXBException"
hw_wired 14.02.2025
Как разработчики Java-приложений, мы сталкиваемся с разными ошибками, но одна из них - java. lang. NoClassDefFoundError: javax/ xml/ bind/ JAXBException - стала особенно актуальной после выхода Java 9. . . .
Отличия for-in от for-of в JavaScript
hw_wired 14.02.2025
Когда-то единственным способом перебора элементов массива или свойств объекта был классический цикл for с счетчиком. Да, он отлично справлялся с задачей, но код получался громоздким и не очень. . .
Отличия implementation, api и compile в Gradle
hw_wired 14.02.2025
Управление зависимостями - одна из ключевых задач при разработке современных приложений на Java и Kotlin. Система сборки Gradle предоставляет гибкие и мощные средства для работы с зависимостями,. . .
Что лучше: require или import/export в JavaScript
hw_wired 14.02.2025
Модульность в JavaScript прошла долгий путь эволюции, и сегодня у разработчиков есть два основных способа организации модулей: старый добрый require из системы CommonJS и современные import/ export из. . .
Ошибка "Uncaught SyntaxError: Cannot use import statement outside a module"
hw_wired 14.02.2025
Думаю, многие разработчики сталкивались с ошибкой "Uncaught SyntaxError: Cannot use import statement outside a module" при попытке использовать современный синтаксис импорта в JavaScript. Эта. . .
Ошибка Docker "Got permission denied while trying to connect to the Docker daemon socket at"
hw_wired 14.02.2025
Разработка с использованием Docker может иногда преподносить неожиданные сюрпризы, и одним из самых распространенных камней преткновения становится ошибка с отказом в доступе к демону Docker. . . .
Ошибка "No 'Access-Control-Allow-Origin' header is present on the requested resource"
hw_wired 14.02.2025
При разработке современных веб-приложений нередко сталкиваешься с ошибкой "No 'Access-Control-Allow-Origin' header is present on the requested resource". Эта проблема возникает из-за политики. . .
Как закрыть порт в Linux
hw_wired 14.02.2025
Управление сетевыми портами в Linux - непростая, но важная задача для обеспечения безопасности системы. Каждый открытый порт - это потенциальная уязвимость, через которую злоумышленики могут. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru