31

次のように定義されたバイナリツリーデータ構造があるとしましょう

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

次のようなツリーのインスタンスがあります。

let x =
  Node
    (Node (Node (Nil,35,Node (Nil,40,Nil)),48,Node (Nil,52,Node (Nil,53,Nil))),
     80,Node (Node (Nil,82,Node (Nil,83,Nil)),92,Node (Nil,98,Nil)))

ツリーを解釈しやすいものにきれいに印刷しようとしています。できれば、次のようにコンソール ウィンドウにツリーを出力したいと思います。

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

ツリーをその形式で出力する簡単な方法は何ですか?

4

5 に答える 5

33

非常にきれいにしたい場合は、このブログエントリから約25行のコードを盗んで、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
*)
于 2009-11-14T06:07:43.267 に答える
4

頭を横に向けてもかまわない場合は、最初にツリーの深さを出力し、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
>
于 2009-11-14T05:13:02.863 に答える
2

多分これが役立つかもしれません: ML でツリーを描画する

于 2010-07-11T12:37:18.420 に答える
1

これは直感です。クヌースのような誰かが考えていたと思います。確認するのが面倒です。

ツリーを 1 次元構造として見ると、長さ 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/2 要素の代わりに文字列の 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
于 2011-01-13T18:20:36.647 に答える
1

正確な出力ではありませんが、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;")"]
;;
于 2009-11-14T05:22:03.107 に答える