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

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

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

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

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

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

Узел 10 является листом, поэтому чтобы обозначить это во входном файле указывается, что оба его потенциальных потомки отсутствуют - после 10 идет два нуля (0 0). Далее в файле идет еще один 0, который указывает на отсутствие правого потомка для узла 6.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
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
29932 / 19678 / 7695
Регистрация: 22.10.2011
Сообщений: 34,303
Записей в блоге: 6
30.03.2015, 10:23 3
Евгений2395, здесь было: http://www.geeksforgeeks.org/b... onversion/
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
30.03.2015, 10:23

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

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

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

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

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

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

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


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

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

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