Форум программистов, компьютерный форум, киберфорум
Haskell
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.54/13: Рейтинг темы: голосов - 13, средняя оценка - 4.54
0 / 0 / 0
Регистрация: 09.12.2009
Сообщений: 4
1

Бинарные деревья: выделить метку вершины дерева, имеющую наибольшее число вхождений

11.05.2011, 13:35. Просмотров 2444. Ответов 3
Метки нет (Все метки)

Добрый день.
Помогите, пожалуйста, написать программу на Haskell.

Выделить метку вершины дерева, имеющую наибольшее число вхождений.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
11.05.2011, 13:35
Ответы с готовыми решениями:

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

Деревья: загрузка дерева из файла, добавление вершины, удаление вершины
Помогите разработать программу, для работы с двоичными деревьями. Реализовать следующие функции:...

Бинарные деревья, глубина (высота) дерева
Есть дерево, состоящее из целых чисел , читаемых из файла. С выводом и нахождением высоты дерева...

Бинарные деревья. Нахождение высоты дерева
Добрый день. Помогите пожалуйста с задачами. 1) Используя бинарное дерево поиска,которое должно...

3
Эксперт С++
5811 / 3462 / 356
Регистрация: 08.02.2010
Сообщений: 7,448
14.05.2011, 16:44 2
Додумался только до такого:
Haskell
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
data BinTree a = Nil
               | Node a (BinTree a) (BinTree a)
                 deriving (Eq, Show)
 
maxLabel :: (Eq a) => BinTree a -> Maybe a
maxLabel Nil = Nothing
maxLabel tree = Just ml
    where (ml, _) = foldl1 maxLabelOcc . countLabels . labels $ tree
          maxLabelOcc l1@(_, c1) l2@(_, c2) =
              if c1 > c2 then l1 else l2
 
          labels :: BinTree a -> [a]
          labels Nil = []
          labels (Node x l r) = x : labels l ++ labels r
 
          countLabels :: (Eq a) => [a] -> [(a, Int)]
          countLabels list = map cnt list
              where cnt x = (x, foldl (\acc el -> acc + if x == el then 1 else 0) 0 list)
1
0 / 0 / 0
Регистрация: 09.12.2009
Сообщений: 4
17.05.2011, 13:56  [ТС] 3
Я его подправил, но что-то не то =(

Haskell
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
data BinTree a = Nil  | Node a (BinTree a) (BinTree a) | Leaf a
 
maxLabel :: (Eq a) => BinTree a -> Maybe a
maxLabel Nil = Nothing
maxLabel tree = Just ml
    where (ml, _) = foldl1 maxLabelOcc . countLabels . labels $ tree
          maxLabelOcc l1@(_, c1) l2@(_, c2) =
              if c1 > c2 then l1 else l2
 
          labels :: BinTree a -> [a]
          labels Nil = []
          --labels (Leaf x) = x
          labels (Node x l r) = x : labels l ++ labels r
 
          countLabels :: (Eq a) => [a] -> [(a, Int)]
          countLabels list = map cnt list
              where cnt x = (x, foldl (\acc el -> acc + if x == el then 1 else 0) 0 list)
 
tree = Node "alpha" (Leaf "alpha") (Node "beta" (Leaf "gamma") (Leaf "delta"))
 
main = print $ maxLabel tree
помогите подправить
0
Эксперт С++
5811 / 3462 / 356
Регистрация: 08.02.2010
Сообщений: 7,448
17.05.2011, 17:31 4
Цитата Сообщение от mad123 Посмотреть сообщение
Я его подправил, но что-то не то =(
а вот не надо было ничего подправлять. Функция maxLabel работала именно с моей структурой дерева (как видишь, там не было конструктора Leaf).
Вот "подправленная" версия (плюс печать дерева в удобном виде):
Haskell
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
data BinTree a = Nil
               | Node a (BinTree a) (BinTree a)
                 deriving (Eq)
 
maxLabel :: (Eq a) => BinTree a -> Maybe a
maxLabel Nil = Nothing
maxLabel tree = Just ml
    where (ml, _) = foldl1 maxLabelOcc . countLabels . labels $ tree
          maxLabelOcc l1@(_, c1) l2@(_, c2) =
              if c1 > c2 then l1 else l2
 
          labels :: BinTree a -> [a]
          labels Nil = []
          labels (Node x l r) = x : labels l ++ labels r
 
          countLabels :: (Eq a) => [a] -> [(a, Int)]
          countLabels list = map cnt list
              where cnt x = (x, foldl (\acc el -> acc + if x == el then 1 else 0) 0 list)
 
tree :: BinTree String                  
tree = Node "alpha" (Node "alpha" Nil (Node "delta" Nil (Node "alpha" Nil Nil))) (Node "beta" (Node "gamma" Nil Nil) (Node "delta" Nil Nil))
 
showBinTree :: Show a => BinTree a -> String
showBinTree Nil = "\n"
showBinTree (Node x l r) = show x ++ "\n" ++ show' 2 l ++ show' 2 r
    where show' :: Show a => Int -> BinTree a -> String
          show' cnt Nil = ""
          show' cnt (Node x l r) = arr cnt ++ show x ++ "\n" ++ show' cnt' l ++ show' cnt' r
              where cnt' = cnt + 5
                    arr :: Int -> String
                    arr cnt = take cnt lp ++ "|--"
                    lp = "  |  " ++ lp
                                                            
instance Show a => Show (BinTree a) where                           
  show = showBinTree
 
main :: IO ()         
main = do putStrLn "Дерево: "
          print tree
          putStrLn $ case maxLabel tree of
                       Nothing    -> "Дерево пусто "
                       Just label -> "Метка вершины дерева" ++
                                    ", имеющая наибольшее число вхождений: " ++
                                    show label
Или лист дерева не считается за вершину?
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
17.05.2011, 17:31

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

Бинарные деревья, вывод дерева на экран
Создание бинарное дерево, помогите с выводом дерева на экран #include <iostream> #include...

Бинарные деревья: найти минимум, распечатать элементы дерева
1. Написать функцию, которая находит наименьший элемент дерева. 2. Написать процедуру, которая...

Бинарные деревья. Напечатать все элементы дерева Т по уровням
Всем привет. Помогите написать программу или хотя бы функцию, условие следующее: Напечатать все...

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


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

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

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