用Clojure表示一棵树

Question

如何在Clojure中以习惯用语的方式表示树？例如：

     A
    / \
   B   C
  /\    \
 D  E    F

性能不重要，而且树的元素数量不会超过1000个。

- Hamza Yerlikaya

---

你们这些人到底怎么回事啊，每次有人不喜欢问题就关闭它。stackoverflow曾经是一个非常好的学习平台，现在却变成了像digg一样充满了许多白痴。如果你不喜欢这个问题，那就用“down vote”（踩）啊。 - Hamza Yerlikaya

因为这是一个完全重复的内容，所以他们投票决定关闭它。 - Rayne

同意；这不是关于喜欢这个问题；正如你所说的学习某些东西-也许可以从上次有人问同样的问题中学习？ - Marc Gravell

适当的做法是给他们投反对票并留言指出原因。如果您足够关心社区去做前者，那么您也应该做后者。否则你只是在存心刁难。 - Carl Smotricz

@MarcGravell - 重复在哪里？对我来说，这是刚刚在Google上搜索“clojure trees”后的最高结果。请问您能否提供更多信息？ - Kenny Evitt

Answer 1

'(A (B (D) (E)) (C (F)))

- user21037

Answer 2

使用仅 cons 的可怕方法：

(defn mktree 
  ([label l r] (cons label (cons l r))) 
  ([leaf] (cons leaf (cons nil nil))))
(defn getlabel [t] (first t))
(defn getchildren [t] (rest t))
(defn getleft [t] (first (getchildren t)))
(defn getright [t] (rest (getchildren t)))

请注意，children并不是一个列表；它是一对。如果您的树不仅仅是二叉树，您可以将其制作成列表。当没有左孩子或右孩子时，请使用nil。

否则，请参见this answer。

您图片中的树：

(mktree 'A (mktree 'B (mktree 'D) (mktree 'E)) (mktree 'C nil (mktree 'F)))

- Jonathan Graehl

---

它在car cdr的位置上有first和rest。 - Hamza Yerlikaya

Common Lisp 两者都有。我会编辑一下。不过它确实有 'cons' 吗？ - Jonathan Graehl

我认为你应该编辑一下，改成“我只会普通Lisp”。Common Lisp不是‘Lisp’。它是Lisp之一。 - Rayne

Answer 3

树在Clojure中几乎贯穿了所有内容，因为它们非常适合持久数据结构中的结构共享。映射和向量实际上是具有高分支因子的树，以使它们具有有界的查找和插入时间。所以我能给出的最短答案（虽然并不真正有用）是我强烈推荐Purely functional data structures by Chris Okasaki来回答这个问题。此外，Rich Hickey在blip.tv上关于Clojure数据结构的视频也很值得一看。

(set 'A 'B 'C)

- Arthur Ulfeldt