考虑一棵树,它由以下递归定义确定:
一棵树应该是一个包含两个元素的向量:第一个元素是数字,第二个元素是树列表或空值。
下面的Clojure数据结构就是一个例子:
我想到了这个解决方案:
并且,事实上:
一棵树应该是一个包含两个元素的向量:第一个元素是数字,第二个元素是树列表或空值。
下面的Clojure数据结构就是一个例子:
(def tree '[9 ([4 nil]
[6 nil]
[2 ([55 nil]
[22 nil]
[3 ([5 nil])])]
[67 ([44 nil])])])
这个结构应该转换成一个所有可能的向下连接的列表,可以从任何节点到其子节点进行连接。 连接应表示为包含父节点值后跟子节点值的向量。 顺序不重要:
(def result '([9 4]
[9 6]
[9 2]
[2 55]
[2 22]
[2 3]
[3 5]
[9 67]
[67 44])
我想到了这个解决方案:
(defn get-connections [[x xs]]
(concat (map #(vector x (first %)) xs)
(mapcat get-connections xs)))
并且,事实上:
(= (sort result)
(sort (get-connections tree)))
;; true
然而,有没有更好的方法只使用Clojure来实现呢? 在这个方法中,我遍历了每个节点的两个子节点,这应该被避免。在这种情况下,尾递归并不是必要的,因此一个简单的递归版本就可以了。
此外,我对哪些更高级的抽象方法用于解决这个问题很感兴趣。Zipper或Clojure/Walk怎么样?最后:这些技术中哪些也适用于ClojureScript?