Скажем, у меня есть дерево, определенное в соответствии с рекомендацией в этом сообщении, хотя это вектор в моем случае, который, надеюсь, не должен иметь значения (они являются векторами в Программе Clojure):
(def tree [1 [[2 [4] [5]] [3 [6]]]])
который должен выглядеть примерно так:
1
/ \
2 3
/ \ |
4 5 6
Теперь я хотел бы сделать обход ширины в дереве без каких-либо традиционных средств, таких как очередь, и вместо этого использовать исключительно стек для передачи информации. Я знаю, что это не самый простой маршрут, но я делаю это в основном как упражнение. Также на этом этапе я не планирую возвращать коллекцию (я потом узнаю об этом как упражнение), но вместо этого просто распечатаю узлы, когда я путешествую через них.
Мое текущее решение (только начинать с Clojure, быть хорошим):
(defn breadth-recur
[queue]
(if (empty? queue)
(println "Done!")
(let [collections (first (filter coll? queue))]
(do
; print out nodes on the current level, they will not be wrapped'
; in a [] vector and thus coll? will return false
(doseq [node queue] (if (not (coll? node)) (println node)))
(recur (reduce conj (first collections) (rest collections)))))))
Последняя строка не работает должным образом, и я не понимаю, как ее исправить. Я точно знаю, что хочу: мне нужно очистить каждый слой векторов, а затем объединить результаты, чтобы перейти в recur.
Проблема, которую я вижу, в основном:
IllegalArgumentException Don't know how to create ISeq from: java.lang.Long
В принципе conj не нравится добавлять вектор к длинному, и если я сменю conj для concat, то я терпит неудачу, когда один из двух элементов, конкатенирование не является вектором. И кон, и concat терпят неудачу при столкновении:
[2 [4] [5] [3 [6]]]
Мне кажется, что мне не хватает действительно основной операции здесь, которая будет работать как на векторах, так и на примитивах в обеих позициях.
Любые предложения?
Изменить 1:
На самом деле дерево должно быть (спасибо Joost!):
(def tree [1 [2 [4] [5]] [3 [6]]])
Однако мы еще не нашли ширину - первое решение.