Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.67/6: Рейтинг темы: голосов - 6, средняя оценка - 4.67
Евгений2395
0 / 0 / 0
Регистрация: 23.11.2014
Сообщений: 20
Записей в блоге: 2
#1

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

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

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

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

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

Узел 10 является листом, поэтому чтобы обозначить это во входном файле указывается, что оба его потенциальных потомки отсутствуют - после 10 идет два нуля (0 0). Далее в файле идет еще один 0, который указывает на отсутствие правого потомка для узла 6.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.03.2015, 00:29
Ответы с готовыми решениями:

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

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

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

Бинарное дерево поиска
Вот задали лабораторною работу. Сделал бинарное дерево поиска. Выдает ошибку...

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

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
volvo
Супер-модератор
Эксперт Pascal/DelphiАвтор FAQ
25966 / 17410 / 6906
Регистрация: 22.10.2011
Сообщений: 30,655
Записей в блоге: 6
30.03.2015, 10:23 #3
Евгений2395, здесь было: http://www.geeksforgeeks.org/binary-...ee-conversion/
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.03.2015, 10:23

Бинарное дерево поиска
Всем привет! Не могу понять одну вещь. Есть вот такой код для заполнения...

Бинарное дерево поиска:
Всем добрый вечер) Подскажите пж новичку из-за чего вылетает программа? Я как...

Бинарное дерево поиска
Решил написать бинарное дерево поиска, но что-то пошло не так, дерево не...


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

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

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