| 1 |
.PS |
| 2 |
# BtreeDPV.m4 |
| 3 |
# One way to draw a binary tree using pic macros |
| 4 |
gen_init(svg_font(sans-serif,11bp__)) |
| 5 |
sinclude(tst.dim) |
| 6 |
s_init(Btree) |
| 7 |
maxpswid = 12 |
| 8 |
Btree: [ |
| 9 |
circlerad = 0.35 |
| 10 |
|
| 11 |
define n { [C: circle fill_(0.9) $1 |
| 12 |
if "$2" != "" then { |
| 13 |
L: $2 with .ne at C.s-(circlerad/20, circlerad/2) |
| 14 |
line from C to L.C chop } |
| 15 |
if "$3" != "" then { |
| 16 |
R: $3 with .nw at C.s+(circlerad/20,-circlerad/2) |
| 17 |
line from C to R.C chop } |
| 18 |
] } |
| 19 |
|
| 20 |
# Redrawn from T. A. Standish, "Data Structure Techniques," Addison-Wesley 1980. |
| 21 |
# Node data: |
| 22 |
define Sirius { n("Sirius",Canopus,Vega) } |
| 23 |
define Canopus { n("Canopus",AlphaCentauri,Capella) } |
| 24 |
define AlphaCentauri { n("Alpha" "Centauri",Achernar,Arcturus) } |
| 25 |
define Arcturus { n("Arcturus",Betelgeux) } |
| 26 |
define Betelgeux { n("Betelgeux",BetaCentauri) } |
| 27 |
define Capella { n("Capella",Rigel) } |
| 28 |
define Rigel { n("Rigel",Procyon) } |
| 29 |
define Achernar { n("Achernar") } |
| 30 |
define BetaCentauri { n("Beta" "Centauri") } |
| 31 |
define Procyon { n("Procyon") } |
| 32 |
define Vega { n("Vega") } |
| 33 |
|
| 34 |
# Build the tree from the root |
| 35 |
S: Sirius |
| 36 |
|
| 37 |
command "</g>" # end font |
| 38 |
] |
| 39 |
Ttree: [ |
| 40 |
# TtreeDPV.m4 |
| 41 |
svg_font(sans-serif,10bp__) |
| 42 |
|
| 43 |
# `Node(no in row, head [location], |
| 44 |
# displacement of top of body (.n) wrt head, |
| 45 |
# body Node 1, body Node 2, ...) ' |
| 46 |
define(`Node',` |
| 47 |
Head`$1': `$2' |
| 48 |
ifelse(`$3',,,` Body`$1': [ |
| 49 |
Loopover_(`v',`v; define(`m4ct',m4Lx)',shift(shift(shift($@)))) |
| 50 |
] with .n at Head`$1' + `$3' |
| 51 |
connect(`$1',m4ct)')') |
| 52 |
|
| 53 |
define(`connect',`Bot: move from Head$1.sw-(0,5bp__) to Head$1.se-(0,5bp__) |
| 54 |
for_(1,`$2',1, |
| 55 |
`Top: move from Body$1.Head`'m4x.nw+(0,2bp__) \ |
| 56 |
to Body$1.Head`'m4x.ne+(0,2bp__) |
| 57 |
Mov: move from Head$1 to Body$1.Head`'m4x |
| 58 |
if Bot.len*Top.len*Mov.len > 0 then { |
| 59 |
line from Intersect_(Mov,Top) to Intersect_(Mov,Bot)}')') |
| 60 |
|
| 61 |
vsep = 0.75 |
| 62 |
define(`txw',`wid `$1'mm__')dnl scaled by 14/12 for 14 pt type |
| 63 |
|
| 64 |
Node(1,"svg_it(h(h(h(x`'svg_sub(1),x`'svg_sub(2))," \ |
| 65 |
+ "h(x`'svg_sub(3),x`'svg_sub(4))),h(h(x`'svg_sub(5),x`'svg_sub(6))," \ |
| 66 |
+ "h(x`'svg_sub(7),x`'svg_sub(8)))))" txw(70) , |
| 67 |
(0,-vsep), |
| 68 |
Node(1,"svg_it(h(h(x`'svg_sub(1),x`'svg_sub(2)),h(x`'svg_sub(3)," \ |
| 69 |
+ "x`'svg_sub(4))))" txw(32) , |
| 70 |
(0,-vsep), |
| 71 |
Node(1,"svg_it(h(x`'svg_sub(1),x`'svg_sub(2)))" txw(14) , |
| 72 |
(0,-vsep), |
| 73 |
Node(1,"svg_it(x`'svg_sub(1):=((A,pk`'svg_sub(A)),h`'svg_sub(1)))" \ |
| 74 |
txw(29) ), |
| 75 |
Node(2,"svg_it(x`'svg_sub(2):=((B,pk`'svg_sub(B)),h`'svg_sub(2)))" \ |
| 76 |
txw(29) with .n at last "".ne+(0.2,-vsep*2/3))), |
| 77 |
Node(2,"svg_it(h(x`'svg_sub(3),x`'svg_sub(4)))" txw(14) \ |
| 78 |
with .nw at Head1.ne+(Body1.wid/2+0.1,0), |
| 79 |
(0,-vsep), |
| 80 |
Node(1,"svg_it(x`'svg_sub(3):=" \ |
| 81 |
+ "((A,pk`'svg_prime`'svg_sub(A,,,-0.5ex)),h`'svg_sub(3)))" \ |
| 82 |
txw(29)), |
| 83 |
Node(2,"svg_it(x`'svg_sub(4):=((D,pk`'svg_sub(D)),h`'svg_sub(4)))" \ |
| 84 |
txw(29) with .n at last "".ne+(0.2,-vsep*2/3)))), |
| 85 |
Node(2,"svg_it(h(h(x`'svg_sub(5),x`'svg_sub(6)),h(x`'svg_sub(7)," \ |
| 86 |
+ "x`'svg_sub(8))))" txw(29) with .nw at Head1.ne+(Body1.wid/2,0), |
| 87 |
(0,-vsep), |
| 88 |
Node(1, "svg_it(h(x`'svg_sub(5),x`'svg_sub(6)))" txw(14) , |
| 89 |
(0,-vsep*5/4), |
| 90 |
Node(1,"svg_it(x`'svg_sub(5):=((E,pk`'svg_sub(E)),h`'svg_sub(5)))" \ |
| 91 |
txw(29) ), |
| 92 |
Node(2,"svg_it(x`'svg_sub(6):=((H,pk`'svg_sub(H)),h`'svg_sub(6)))" \ |
| 93 |
txw(29) with .n at last "".ne+(0.2,-vsep*2/3))), |
| 94 |
Node(2,"svg_it(h(x`'svg_sub(7),x`'svg_sub(8)))" txw(14) \ |
| 95 |
with .nw at Head1.ne+(Body1.wid/2+0.1,0), |
| 96 |
(0,-vsep*5/4), |
| 97 |
Node(1,"svg_it(x`'svg_sub(7):=" \ |
| 98 |
+ "((D,pk`'svg_prime`'svg_sub(D,,,-0.5ex)),h`'svg_sub(7)))" \ |
| 99 |
txw(29) ), |
| 100 |
Node(2,"svg_it(x`'svg_sub(8):=((K,pk`'svg_sub(K)),h`'svg_sub(8)))" \ |
| 101 |
txw(29) with .n at last "".ne+(0.2,-vsep*2/3); \ |
| 102 |
move right 0.2)), |
| 103 |
Node(3,"svg_it(h(x`'svg_sub(9)))" txw(8) \ |
| 104 |
at 0.5 between Head1 and Head2))) |
| 105 |
|
| 106 |
] with .w at last [].e+(-1,0) |
| 107 |
|
| 108 |
command "</g>" # end font |
| 109 |
.PE |