漂亮的树

如果你想让它非常漂亮,你可以从 this blog entry 用WPF绘制。

但我很快也会编写一个ASCII解决方案。

编辑

好吧,哇,那太难了。

我不确定这是完全正确的,我忍不住认为可能有更好的抽象。但是无论如何…享受吧!

(有关相当漂亮的大型示例,请参见代码末尾。)

type 'a tree =    
    | Node of 'a tree * 'a * 'a tree
    | Nil

(*
For any given tree
     ddd
     / \
   lll rrr  
we think about it as these three sections, left|middle|right (L|M|R):
     d | d | d
     / |   | \
   lll |   | rrr  
M is always exactly one character.
L will be as wide as either (d's width / 2) or L's width, whichever is more (and always at least one)
R will be as wide as either ((d's width - 1) / 2) or R's width, whichever is more (and always at least one)
     (above two lines mean 'dddd' of even length is slightly off-center left)
We want the '/' to appear directly above the rightmost character of the direct left child.
We want the '\' to appear directly above the leftmost character of the direct right child.
If the width of 'ddd' is not long enough to reach within 1 character of the slashes, we widen 'ddd' with
    underscore characters on that side until it is wide enough.
*)

// PrettyAndWidthInfo : 'a tree -> string[] * int * int * int
// strings are all the same width (space padded if needed)
// first int is that total width
// second int is the column the root node starts in
// third int is the column the root node ends in
// (assumes d.ToString() never returns empty string)
let rec PrettyAndWidthInfo t =
    match t with
    | Nil -> 
        [], 0, 0, 0
    | Node(Nil,d,Nil) -> 
        let s = d.ToString()
        [s], s.Length, 0, s.Length-1
    | Node(l,d,r) ->
        // compute info for string of this node's data
        let s = d.ToString()
        let sw = s.Length
        let swl = sw/2
        let swr = (sw-1)/2
        assert(swl+1+swr = sw)  
        // recurse
        let lp,lw,_,lc = PrettyAndWidthInfo l
        let rp,rw,rc,_ = PrettyAndWidthInfo r
        // account for absent subtrees
        let lw,lb = if lw=0 then 1," " else lw,"/"
        let rw,rb = if rw=0 then 1," " else rw,"\\"
        // compute full width of this tree
        let totalLeftWidth = (max (max lw swl) 1)
        let totalRightWidth = (max (max rw swr) 1)
        let w = totalLeftWidth + 1 + totalRightWidth
(*
A suggestive example:
     dddd | d | dddd__
        / |   |       \
      lll |   |       rr
          |   |      ...
          |   | rrrrrrrrrrr
     ----       ----           swl, swr (left/right string width (of this node) before any padding)
      ---       -----------    lw, rw   (left/right width (of subtree) before any padding)
     ----                      totalLeftWidth
                -----------    totalRightWidth
     ----   -   -----------    w (total width)
*)
        // get right column info that accounts for left side
        let rc2 = totalLeftWidth + 1 + rc
        // make left and right tree same height        
        let lp = if lp.Length < rp.Length then lp @ List.init (rp.Length-lp.Length) (fun _ -> "") else lp
        let rp = if rp.Length < lp.Length then rp @ List.init (lp.Length-rp.Length) (fun _ -> "") else rp
        // widen left and right trees if necessary (in case parent node is wider, and also to fix the 'added height')
        let lp = lp |> List.map (fun s -> if s.Length < totalLeftWidth then (nSpaces (totalLeftWidth - s.Length)) + s else s)
        let rp = rp |> List.map (fun s -> if s.Length < totalRightWidth then s + (nSpaces (totalRightWidth - s.Length)) else s)
        // first part of line1
        let line1 =
            if swl < lw - lc - 1 then
                (nSpaces (lc + 1)) + (nBars (lw - lc - swl)) + s
            else
                (nSpaces (totalLeftWidth - swl)) + s
        // line1 right bars
        let line1 =
            if rc2 > line1.Length then
                line1 + (nBars (rc2 - line1.Length))
            else
                line1
        // line1 right padding
        let line1 = line1 + (nSpaces (w - line1.Length))
        // first part of line2
        let line2 = (nSpaces (totalLeftWidth - lw + lc)) + lb 
        // pad rest of left half
        let line2 = line2 + (nSpaces (totalLeftWidth - line2.Length))
        // add right content
        let line2 = line2 + " " + (nSpaces rc) + rb
        // add right padding
        let line2 = line2 + (nSpaces (w - line2.Length))
        let resultLines = line1 :: line2 :: ((lp,rp) ||> List.map2 (fun l r -> l + " " + r))
        for x in resultLines do
            assert(x.Length = w)
        resultLines, w, lw-swl, totalLeftWidth+1+swr
and nSpaces n = 
    String.replicate n " "
and nBars n = 
    String.replicate n "_"

let PrettyPrint t =
    let sl,_,_,_ = PrettyAndWidthInfo t
    for s in sl do
        printfn "%s" s

let y = Node(Node (Node (Nil,35,Node (Node(Nil,1,Nil),88888888,Nil)),48,Node (Nil,777777777,Node (Nil,53,Nil))),     
             80,Node (Node (Nil,82,Node (Nil,83,Nil)),1111111111,Node (Nil,98,Nil)))
let z = Node(y,55555,y)
let x = Node(z,4444,y)

PrettyPrint x
(*
                                   ___________________________4444_________________
                                  /                                                \
                      ________55555________________                         ________80
                     /                             \                       /         \
            ________80                      ________80             _______48         1111111111
           /         \                     /         \            /        \            /  \
   _______48         1111111111    _______48         1111111111 35         777777777  82   98
  /        \            /  \      /        \            /  \      \             \       \
35         777777777  82   98   35         777777777  82   98     88888888      53      83
  \             \       \         \             \       \            /
  88888888      53      83        88888888      53      83           1
     /                               /
     1                               1
*)     

如果你不介意把你的头转向一边,你可以先打印树的深度,一个节点到一行,递归地将深度传递到树上,然后打印 depth*N 节点前的行上有空格。

以下是Lua代码:

tree={{{nil,35,{nil,40,nil}},48,{nil,52,{nil,53,nil}}},
      80,{{nil,82,{nil,83,nil}},92 {nil,98,nil}}}

function pptree (t,depth) 
  if t ~= nil
  then pptree(t[3], depth+1)
    print(string.format("%s%d",string.rep("  ",depth), t[2]))
    pptree(t[1], depth+1)
  end
end

> pptree(tree,4)
        98
      92
          83
        82
    80
          53
        52
      48
          40
        35
> 

这篇文章看起来不错 http://llimllib.github.com/pymag-trees/

也许这可以帮助: Drawing Trees in ML

虽然输出不完全正确,但我在 http://www.christiankissig.de/cms/files/ocaml99/problem67.ml :

(* A string representation of binary trees

Somebody represents binary trees as strings of the following type (see example opposite):

a(b(d,e),c(,f(g,)))

a) Write a Prolog predicate which generates this string representation, if the tree 
is given as usual (as nil or t(X,L,R) term). Then write a predicate which does this 
inverse; i.e. given the string representation, construct the tree in the usual form. 
Finally, combine the two predicates in a single predicate tree_string/2 which can be 
used in both directions.

b) Write the same predicate tree_string/2 using difference lists and a single 
predicate tree_dlist/2 which does the conversion between a tree and a difference 
list in both directions.

For simplicity, suppose the information in the nodes is a single letter and there are 
no spaces in the string. 
*)

type bin_tree = 
    Leaf of string
|   Node of string * bin_tree * bin_tree
;;

let rec tree_to_string t =
    match t with
            Leaf s -> s
    |       Node (s,tl,tr) -> 
                    String.concat "" 
                            [s;"(";tree_to_string tl;",";tree_to_string tr;")"]
;;

这是直觉,我相信像克努斯这样的人有这个想法,我太懒了。 检查。

如果你把你的树看作一维结构,你会得到一个数组 长度l的(或矢量) 当树不平衡时,必须进行一些计算来填补间隙。

2尺寸

                    _______ 80 _______
                   /                  \
                _ 48 _              _ 92 _
               /      \            /      \
             35       52         82       98
               \       \        /
                40      53    83

1维度:

             35 40 48   52 53 80 83 82    92    98   
           0 1  2  3  4  5  6  7  8  9 10 11 12 13 14 

可以使用此数组生成漂亮的打印树 (可能是递归的) 首先使用L/2位置的值,X位置是 L/2值*默认长度(此处为2个字符)

                              80

    then (L/2) - (L/4)  and  (L/2) + (L/4) 

                   48                    92
    then L/2-L/4-L/8, L/2-L/4+L/8, L/2+L/4-L/8 and L/2+L/4+L/8 

              35        52         82          98

    ...

添加漂亮的分支将导致更多的位置运算,但在这里它是微不足道的

您可以将值串联到字符串中,而不是使用数组,串联将 事实上,计算最佳X位置,并允许不同的值大小, 做一棵更紧凑的树。 在这种情况下,必须对字符串中要提取的单词进行计数。 价值观。例如:对于使用字符串的l/2th字的第一个元素 数组的l/2元素。字符串中的X位置在树中相同。

N 35 40 48 N 52 53 80 83 82 N 92 N 98 N 
                   80
        48                    92
  35         52          82        98
     40         53    83