6_5.hs

{--
Задача 6-5
Одеров Роман, 545 гр.
--}

data Tree = Empty
			| Node Integer Tree Tree
			deriving Eq

{-	Функция minHeight вызывает ф-цию bfs, реализующую
	обычный поиск в ширину с целью найти первый попавшийся лист и
	выдать высоту этого листа.

	С отсечением по высоте как-то не хотелось делать... :-)
-}
minHeight Empty = 0
minHeight (Node i l r) = bfs 0 [(Node i l r)]

{- 	bfs - поиск в ширину
	Заключается в "поуровневом" просмотре вершин дерева, начиная с корня.
	Ведется подсчет текущей высоты дерева, т.е. при переходе на след.уровень
	высота увеличивается на 1 (такого рода аккумулирующий параметр)

	h - высота текущего уровня
	ns - список вершин на текущем уровне
-}
bfs h ns = 	if check ns	-- если среди соседних вершин текущего уровня есть лист,
			then h 		-- то нужно закончить и выдать высоту h
			else bfs (h+1) (childs ns) 	--иначе, если листа не нашлось, искать на след.уровне,
										--увеличив высоту на 1.

{- 	Поиск листа в массиве вершин
	Лист - если оба потомка у него пустые.
-}
check [] = False
check ((Node _ l r):ns)
	|l == Empty && r == Empty = True
	|otherwise = check ns

{-	Составление списка детей от всех текущих узлов дерева
	Включаем в список детей, очевидно, только непустые узлы.
-}
childs [] = []
childs ((Node _ l r):ns)
	|l /= Empty && r /= Empty = l:r:childs ns
	|l /= Empty = l:childs ns
	|r /= Empty = r:childs ns

{-
	Возможная оптимизация, видимо, заключается в том, чтобы 
	не делать два прохода по списку вершин (внутри ф-ций check и childs),
	а сразу при проверке в check давать массив "детей".
-}