common-lisp - 在 REPL 中打印 BST？

Question

我正在尝试获取二叉搜索树的结构打印函数，如下所示，以 xml 风格打印出节点(及其子节点，递归地)。这个想法是添加适当的缩进应该可以更容易地看到 BST 的结构。

我目前拥有的是:

(defstruct
  (node (:print-function
          (lambda (n s d)      
            (format s "#<~A ~A ~A>" (node-elt n) (node-l n) (node-r n)))))
  elt (l nil) (r nil))

这会打印出 BST，例如:

#<5 #<4 #<2 #<1 NIL NIL> #<3 NIL NIL>> NIL> #<8 #<6 NIL #<7 NIL NIL>> #<9 NIL NIL>>>

但我想要一些可以更轻松地可视化树结构的​​东西。

我有这样的想法:

#<5 
 #<4 
  #<2 
   #<1 NIL NIL> 
   #<3 NIL NIL>> NIL> 
 #<8 
  #<6 NIL 
   #<7 NIL NIL>> 
  #<9 NIL NIL>>>

假设我的目标是好的，每行的缩进深度必须取决于递归的深度。我不确定如何在上面的 format 表单中执行此操作。

实际上，也许这毕竟不是一个很好的显示方式。

如果没有，有什么好方法可以在 REPL 中打印出一棵(当然是小的)二叉搜索树，以便人们可以轻松地看到它的结构？ (作为帮助算法开发的工具)。

谢谢。

Answer 1

您可以使用逻辑 block 。

(defstruct
    (node
      (:constructor bst (elt &optional l r))
      (:print-function
         (lambda (n s d)
           (declare (ignore d))
           (format s
                   "(~s ~@<~s ~_~s ~_~s)~:>"
                   'bst
                   (node-elt n) (node-l n) (node-r n)))))
  elt (l nil) (r nil))

当您调用PPRINT-LOGICAL-BLOCK时，正在使用的流变成 pretty-printing stream在 block 的范围内(如果它还不是一个)。以 pprint- 开头的函数(如 pprint-newline 或 pprint-indent)尊重缩进级别、逻辑 block 等。常见函数如 terpri 或 fresh-line 则不然。

上面的格式在bst之后定义了一个逻辑 block ，并在每个元素之间打印条件换行符。该特定打印机的附加值(value)在于它可以清晰地打印表格。

输入

感谢 :constructor 选项，我们可以编写 BST 如下:

(bst t
     (bst 1 (bst :x) (bst :y))
     (bst 2 (bst :a) (bst :b)))

打印结果

评估时，生成的树会以可以读回以生成等效树的方式打印。

(BST T
     (BST 1 (BST :X NIL NIL) (BST :Y NIL NIL))
     (BST 2 (BST :A NIL NIL) (BST :B NIL NIL)))

替代打印机

您还可以定义一个仅使用中间列表打印表单的打印机。这编写起来更简单，并且依赖于现有的 pretty-print 函数。

(defstruct
        (node
          (:constructor bst (elt &optional l r))
          (:print-function
             (lambda (n s d)
               (declare (ignore d))
               (princ (list 'bst
                            (node-elt n)
                            (node-l n)
                            (node-r n))
                      s))))
      elt (l nil) (r nil))

修改打印机的输出

(BST T (BST 1 (BST X NIL NIL) (BST Y NIL NIL))
     (BST 2 (BST A NIL NIL) (BST B NIL NIL)))