juan_gandhi | Entries tagged with dfs

Некоторые люди полагают, что лазать по дереву нельзя без того, чтобы узлы держали указатели на родителей.

Потому и дерево, собственно. Если у нас меню, и один пункт повторяется в нескольких местах... короче, не получится. А ведь в принципе что, посет и посет.

Люди более продвинутые хранят сокровенное знание - ссылки на верх не имеют права на существование. Я таких встречал на интервью дважды. Они, возможно, не делятся этим знанием, потому что знают, что никто их не поддержит.

Так вот, читая Beautiful Code, я понял кое-что.

Конечно, ссылок на верх не надо. Родитель содержит списки детей, и всё.

Но когда мы браузим, то мы должны помнить, откуда пришли. Это и есть указатель на родителя. Тут вообще можно обобщать на графы (ну там решить вопрос с циклами)... или на категорию, ё.

Но главное, что стек (при dfs) и хранит всю необходимую информацию.

Стек - это же что-то вроде коданных. Codata. Происходит свёртка с данными.

На эту же тему - кванты неплохо бы в начальной школе преподавать. Да некому. Как 10000 лет назад некому было учить детей грамоте (нет ли тут русофобии).

scala> abstract class N[T] defined class N scala> case class L[T](v:T) extends N[T] defined class L scala> case class B[T](kids:List[N[T]]) extends N[T] defined class B scala> val t = B(List(B(List(L("ab"),L("cd"),B(List(L("xy"),L("z"))))),L("middle"))) t: B[java.lang.String] = B(List(B(List(L(ab), L(cd), B(List(L(xy), L(z))))), L(middle))) scala> def scan[T](tree:N[T]):List[T] = tree match { case L(v) => List(v); case B(kids) => kids flatMap (scan(_)) } scan: [T](N[T])List[T] scala> scan(t) res17: List[java.lang.String] = List(ab, cd, xy, z, middle) scala>

S	M	T	W	T	F	S
						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

Observations

Views from Souths

Entries tagged with dfs

о, всё фигня, срочно в жж записать

visitor pattern, scala sample

Profile

November 2025

Syndicate

Most Popular Tags

Page Summary

Active Entries

Style Credit

Expand Cut Tags