如何在REPL中格式化打印二叉搜索树（BST）以清晰展示结构？

我之前也遇到过类似的困扰——CL默认的结构体打印输出太紧凑，完全没法直观看出BST的层级结构。针对你的需求，这里有几个实用的解决方案，适合算法开发时快速查看树结构：

1. 自定义递归打印函数（最推荐） #

原结构体的:print-function参数里的第三个参数d是CL内置的打印深度限制，不是用来控制缩进的，所以没法直接用它实现层级缩进。我们可以单独写一个递归打印函数，手动跟踪缩进级别，输出类XML的格式化结构：

代码实现 #

;; 先定义结构体，默认打印保持简洁（避免嵌套打印时混乱）
(defstruct (node (:print-function (lambda (n s d)
                                    (format s "#<Node ~A>" (node-elt n)))))
  elt (l nil) (r nil))

;; 自定义BST打印函数，支持缩进控制
(defun print-bst (node &optional (indent 0) (stream t))
  (when node
    ;; 打印当前节点的起始标签，带指定缩进
    (format stream "~V@T<node elt=\"~A\">~%" indent (node-elt node))
    ;; 递归打印左子树，缩进增加2个空格
    (print-bst (node-l node) (+ indent 2) stream)
    ;; 递归打印右子树，同样增加缩进
    (print-bst (node-r node) (+ indent 2) stream)
    ;; 打印当前节点的闭合标签，保持和起始标签同一缩进
    (format stream "~V@T</node>~%" indent)))

使用示例 #

先构建你的测试树：

(setf my-tree (make-node :elt 5
                         :l (make-node :elt 4
                                       :l (make-node :elt 2
                                                     :l (make-node :elt 1)
                                                     :r (make-node :elt 3)))
                         :r (make-node :elt 8
                                       :l (make-node :elt 6
                                                     :r (make-node :elt 7))
                                       :r (make-node :elt 9))))

调用(print-bst my-tree)会输出：

<node elt="5">
  <node elt="4">
    <node elt="2">
      <node elt="1">
      </node>
      <node elt="3">
      </node>
    </node>
  </node>
  <node elt="8">
    <node elt="6">
      <node elt="7">
      </node>
    </node>
    <node elt="9">
    </node>
  </node>
</node>

这样层级结构一目了然，完全符合你的需求。

2. 集成到REPL的Pretty Print（可选） #

如果你希望在REPL中直接输入节点对象，就能自动输出结构化格式，可以利用CL的pprint机制定制打印规则：

;; 注册node类型的pprint规则
(set-pprint-dispatch 'node
                     (lambda (stream node)
                       (print-bst node 0 stream)))

之后用(pprint my-tree)就能直接输出格式化后的树结构，不用每次手动调用print-bst。

为什么不修改默认的:print-function？ #

CL的:print-function设计初衷是输出简洁的、可被read解析的对象表示（或者至少是清晰的标识），强行在里面做复杂的缩进打印会有两个问题：

• 第三个参数d是打印深度限制，不是缩进层级，没法用来控制缩进；
• 当节点被嵌套在其他结构（比如列表）中时，递归打印会导致格式混乱，破坏整体输出的可读性。

所以保持默认打印简洁，用专门的函数做结构化打印，是更稳妥的选择。

内容的提问来源于stack exchange，提问作者mwal