总体设计
我最终的解决方案涉及创建，合并和打印我要调用的内容稀疏字符串。稀疏字符串只是从行/列对到子字符串的映射。这些子字符串不能包含换行符或彼此重叠。
因此，例如，多行字符串
baz
foo
bar
qux
可以用这种稀疏表示字符串：
{[3 -2] "foo"
[4 -7] "bar"
[2 -6] "baz"
[5 7] "qux"}
注意事项：
空的空间只是由常规空间和换行符填充
第一个坐标是行，第二个坐标是列
第一行和列不必一定为零
打印二叉树的问题然后减少为从中创建稀疏字符串它的左右子树（及其子树的值，将显示在顶部），然后将这些稀疏字符串转移并合并在一起。
使用稀疏字符串表示树时的唯一额外要求是根（或根的中心，如果根宽度大于1个字符）必须位于
[0 0]。考虑下面的树： 4
/ \
2 5
/ \
1 3
它的内存表示形式为
{:value 4
:left {:value 2
:left {:value 1}
:right {:value 3}}
:right {:value 5}}
该树将表示为
{[0 0] "4"
[2 -2] "2"
[4 -4] "1"
[3 -3] "/"
[4 0] "1"
[3 -1] "\"
[1 -1] "/"
[2 2] "5"
[1 1] "\"}
我将其称为树字符串。这样，当我合并多个树字符串以创建更大的树字符串时，可以安全地使用
[0 0]作为要从其移位子树的锚点。代码
(defn end-col
"Returns one plus the maximum column occupied by the sparse string entry x."
[x]
(let [[[_ col] s] x]
(+ col (count s))))
(defn min-corner
"Returns a vector of the minimum non-empty row and column in sparse-string."
[sparse-string]
(mapv #(apply min (map % (keys sparse-string)))
[first second]))
(defn max-corner
"Returns a vector of one plus the maximum non-empty row and column in
sparse-string."
[sparse-string]
(mapv #(apply max (map % sparse-string))
[(comp inc first key) end-col]))
(defn fill
"Returns a string of newlines and spaces to fill the gap between entries x and
y in a sparse string whose minimum corner is corner."
[corner x y]
(let [[_ min-col] corner
[[prev-row _] _] x
[[next-row next-col] _] y]
(apply str (concat (repeat (- next-row prev-row) \newline)
(repeat (- next-col
(if (== prev-row next-row)
(end-col x)
min-col))
\space)))))
(defn sparse-str
"Converts sparse-string to a string."
[sparse-string]
(let [corner (min-corner sparse-string)]
(->> sparse-string
(sort-by key)
(cons [corner ""])
(partition 2 1)
(map (fn [[x y]] (str (fill corner x y) (val y))))
(apply str))))
(defn shift
"Creates and returns a sparse string by adding offset to the position of each
entry in sparse-string."
[offset sparse-string]
(into {} (map (fn [[pos s]]
[(mapv + pos offset) s])
sparse-string)))
(defn vert-gap
"Returns the minimum vertical gap that can be used in combining the left and
right tree strings."
[left right]
(if (and left right)
(max 1 (quot (- (second (max-corner left))
(second (min-corner right)))
2))
1))
(def directions {:left - :right +})
(defn diagonal
"Returns a diagonal sparse string with the top end located at corner."
[direction corner length character]
(let [[first-row first-col] corner]
(into {} (map (fn [n]
[[(+ first-row n)
((directions direction) first-col n)]
(str character)])
(range length)))))
(defn leg
"Returns a sparse string from shifting tree-string according to direction,
vert-gap, and value-height, merged with a diagonal strut."
[direction tree-string vert-gap value-height]
(merge (shift [(+ value-height vert-gap)
((directions direction) (inc vert-gap))]
tree-string)
(diagonal direction
[value-height ((directions direction) 1)]
vert-gap
({:left \/ :right \} direction))))
(defn assemble
"Assembles a complete tree string from the tree strings of a value, left
subtree, and right subtree."
[value left right]
(if (or left right)
(let [[value-height _] (max-corner value)
vert-gap (vert-gap left right)]
(merge value
(when left
(leg :left left vert-gap value-height))
(when right
(leg :right right vert-gap value-height))))
value))
(defn tree-string
"Creates and returns a tree string from node."
[node]
(let [{:keys [value left right]} node
s (str value)]
(apply assemble
{[0 (- (quot (count s) 2))] s}
(map #(when % (tree-string %))
[left right]))))
实施说明
当打印稀疏字符串时，首先需要找到稀疏字符串中最小的行和列。这自然会导致
end-col，min-corner和max-corner函数用于计算稀疏字符串的边界框。现在，如何打印稀疏字符串？基本上，这个问题归结为将空白打印到稀疏字符串条目之间的间隙。一旦完成，实际的
fill实现就非常简单。此外，由于除了创建和打印它们之外，我还将结合稀疏字符串，因此我需要一个函数来现有稀疏字符串的参考点。
现在我们需要的是一种从树的逻辑表示形式转换为文本形式的方法，这是
sparse-str函数的任务。如您所见，大部分工作是通过
shift函数完成的。我们需要做的第一件事是确定要制作连接左子树和右子树的支柱的时间。为简化起见，我们总是使它们具有相同的长度，这意味着由tree-string计算出的支柱的长度将等于assemble树形字符串的底部与vert-gap和value的顶部之间的最终距离树字符串。当然，我们需要
left函数来自己创建支柱。现在我们拥有所有其余部分，这只是一个将它们在一起的问题。
right函数只是一个辅助函数，它将diagonal和assemble组合在一起，然后可以与根合并。示例
如果您要测试此功能自己编写代码，这是一个用于生成随机二叉树的函数：
(defn rand-tree
[weight depth]
(into {:value (int (Math/pow 2 (rand (dec Integer/SIZE))))}
(map #(when (and (pos? depth) (< (rand) weight))
[% (rand-tree weight (dec depth))])
[:left :right])))
所以......
/> ...将打印如下内容：
(println (sparse-str (tree-string (rand-tree 3/4 3))))
#1 楼
首先，在我看来，这两种算法都很好而且有趣，而且代码确实写得很好，分解成易于理解的功能！做得好！
唯一的补充我可以做的是一些辅助功能的特殊情况（及其可能的解决方法）。但是，请注意，从主入口点来看，我没有找到任何触发这些极端情况的方法，因此，从用户的角度来看，即使不进行以下更改，该程序也能正常运行。
Corner案例1
(min-corner {})
(sparse-str {})
都抛出异常，这是由于
min中的min-corner被零参数调用了。为了处理这种情况：(defn min-corner
"Returns a vector of the minimum non-empty row and column in sparse-string."
[sparse-string]
(mapv #(apply min (let [args (map % (keys sparse-string))] (if (empty? args) [0 0] args)))
; (mapv #(apply min (map % (keys sparse-string)))
[first second]))
即，如果参数为空，则使用默认值（在本例中为
min）调用[0 0]。＃2号案例案例
(max-corner {})
类似问题，例如
min-corner，类似的解决方案： >角落＃3 (defn max-corner
"Returns a vector of one plus the maximum non-empty row and column in
sparse-string."
[sparse-string]
(mapv #(apply max (let [args (map % sparse-string)] (if (empty? args) [0 0] args)))
; (mapv #(apply max (map % sparse-string))
[(comp inc first key) end-col]))
这将返回
aab。但是，此处的b放错了位置，因为它应该位于[0 1]的位置，而应该位于[0 2]的位置。 说实话，我真的不知道什么是最好的解决方案。我可以想象以下情况：
保持原样：显示所有输出，其中一些可能在错误的位置。
覆盖第一个的结尾字符串与第二个字符串（即
"ab"）。用第一个字符串覆盖第二个字符串的开头（在本例中为
"aa"）。 ，从主入口点开始，就不可能触发这种情况，因为用户没有提供任何职位。但是，如果要在库中重用辅助函数，则应该解决此问题。案例＃4
(sparse-str {[0 0] "aa" [0 1] "b"})
如果右边的元素的第二个坐标大于左边的第二个坐标，则结果始终为
1。我不确定这是否是设计使然，但如果不是这样，那么我建议确保在这种情况下也可以通过获取差的绝对值而不是差本身来正确计算垂直间隙： (vert-gap {[0 0] "a"} {[4 10] "a"})
拐角案例5
(defn vert-gap
"Returns the minimum vertical gap that can be used in combining the left and
right tree strings."
[left right]
(if (and left right)
(max 1 (quot (Math/abs (- (second (max-corner left))
(second (min-corner right)))
) 2))
1))
对于当前的实现，这将返回空结果：
{}。现在，根据参数length的名称所隐含的语义，这应该是正确的（也许会引发异常，但这仅是细节）。 但是，如果
length的信号可以控制第一个坐标增长的方向，那会不会很好？这样的事情：(diagonal :left [0 0] -2 \a)
这样，上面示例的结果将是：
{[0 0] "a", [-1 -1] "a"}。当然，重命名当然值得考虑
length参数，例如到horizontal-displacement或类似的内容。P.S .：
我为上述更改及其相应的测试用例（以及其他测试）设置了github存储库：
评论
\ $ \ begingroup \ $
感谢您的出色写作！对于角落案例1和角落案例2，我认为最好是sparse-str处理其参数为空（并仅返回“”）的情况，而min-corner和max-corner在他们的文档字符串中，他们的参数必须是非空的，类似于将最小或最大参数传递给非零数量的参数是它的最小和最大契约的一部分。
\ $ \ endgroup \ $
– Sam Estep
17年8月11日在19:14
\ $ \ begingroup \ $
对于角落案例3，我绝对同意当前的行为是不可取的。返回字符串的“尺寸”不应取决于是否存在重叠。在您提出的可能解决方案中，我认为第二个是最好的（用第二个覆盖第一个字符串的末尾）。
\ $ \ endgroup \ $
– Sam Estep
17年8月11日在19:14
\ $ \ begingroup \ $
对于角落案例4，这是一个有趣的行为，一方面您的解决方案可能出于鲁棒性的目的是可取的，但另一方面，在我对“树字符串”的定义中，我指定了根必须在[0 0]处出现，因此{[4 10]“ a”}不符合作为树字符串的条件，并且vert-gap指定其两个参数均为树字符串。
\ $ \ endgroup \ $
– Sam Estep
17年8月11日在19:14
\ $ \ begingroup \ $
对于转角案例5，我喜欢您在长度符号中添加语义的想法！您是否认为这可能也消除了对方向和字符参数的需求？
\ $ \ endgroup \ $
– Sam Estep
17年8月11日在19:14
\ $ \ begingroup \ $
@SamEstep：re＃5：我不认为我们可以将这些信息打包成长度，因为长度的符号现在是垂直方向，而方向是水平方向。除非将长度转换为某种结构，否则IMHO仍将需要所有三段信息。
\ $ \ endgroup \ $
– Attilio
17年8月12日在11:54
评论
为什么2的孩子与238883的孩子处于不同的水平？@Josh因为我的代码将左和右子树分别递归地构建为树字符串，然后将它们组合为整个树的树字符串，所以在该示例中，右子树不知道左子树中支柱的长度，因为它根本不知道左子树是否存在。
但是为什么撑杆的长度不一样？
@Josh因为无法使用树形字符串中的对中函数＃（-（quot（count％）2））使长度为1的支柱的2949729和6不能在同一行上。
@Josh无论如何，如果您认为我的代码可以改进，请提供答案！这就是为什么我首先将其发布在此问题中的原因。