Как жить без call/cc? Посоветуйте алгоритм решения

Кстати, вот, нашел:

(defun btree-enum (btree &key (key #'identity))
  "Enumerate the elements of the binary tree."
  (if (null btree)
      nil
    (enum-append
     (btree-enum (node-l btree))
     (enum-cons
      (funcall key (node-elt btree))
      (btree-enum (node-r btree))))))

(defun btree->seq (btree &key (key #'identity))
  "Return the sequence of elements of the binary tree."
  (make-seq (btree-enum btree :key key)))

Тогда сравнение как побочный эффект от нашего умения обходить дерево:

(defun btree-equal (btree-1 btree-2 &key (test #'eql) (key #'identity))
  "Test two binary trees for equality."
  (seq-equal (btree->seq btree-1)
             (btree->seq btree-2)
             :test test :key key))
   
(defun btree-compare (btree-1 btree-2 test &key (key #'identity))
  "Compare two binary trees."
  (seq-compare (btree->seq btree-1)
               (btree->seq btree-2)
               test :key key))

А это как спасёт? В смысле, что передать в g и fn для обхода по двум деревьям?

Да, у тебя же поддеревья разные. Надо два ацессора передавать (left-tree и right-tree и fn = само дерево)

Это не продолжения. Сопрограммы на стейт машине скорее.

З.Ы. ну и этот автокорректор сафари!

Отключается в системных настройках.

Это тред норкоманов? Сравнение деревьев - простой рекурсивный алгоритм, зачем здесь call/cc?

На Go: http://play.golang.org/p/l4vlUe2qwh

Правда задача чуть-чуть другая, у меня в каждом узле хранятся данные, а не только в «листьях». Тривиально можно сделать и только листья, но так интересней и ближе к реальному миру.

Грубо говоря тут разворачиваются деревья в список и сравниваются списки. Деревья могут быть разные по структуре, но содержать одинаковые данные при обходе в глубину. Задача - сравнить эти данные, а не деревья как таковые. Почитай внимательно код на Scheme, ты походу не понял задачу.

На Java делается итератор, который хранит стек из пар (узел, состояние) и в общем вручную разворачивать рекурсивный алгоритм. Задача не сложная, но нудная, делать не буду, но в целом ясно, как делать.

Можно на Java запустить 2 треда, обходящих дерево по одному узлу, примерно как в Go сделано, это будет красивей, хотя и неразумней.

Понятно.

Можно отказаться от рекурсии в пользу итерации, запоминая текущую позицию в деревьях в двух стеках. Но это C++, на Схеме я не представляю, можно ли.

о нет, ты украл мою идею !!1

Что тут пишутт вообще, я не понимаю, что вы несете? Единственно на питоне показали что-то похожее на вменяемость.

Еще раз, два итератора, которые делаются хранением стейта BFS вне функции. Каждый по очереди дергаешь и сравниваешь.

Что тут пишутт вообще, я не понимаю, что вы несете?

Еще раз, два итератора, которые делаются хранением стейта BFS вне функции. Каждый по очереди дергаешь и сравниваешь.

Именно это и написали.

chan1 := WalkTree(tree1)
chan2 := WalkTree(tree2)

 — два итератора.

for {
	node1 := <-chan1
	node2 := <-chan2
	if node1 == nil && node2 == nil {
		return true
	}
	if node1 == nil || node2 == nil {
		return false
	}
	if !comparator(node1, node2) {
		return false
	}
}

 — дергаются и сравниваются. Что тебе не понятно?

на C# короче выходит кстати

Это библиотека из комплекта quicklisp

Спасибо

Продолжения на питоне симпатичные

в одной из недавних версий запилили

но можно и по старинке в for развернуть