NetNews Usenet Archive 1992 #27/NN_1992_27.iso/spool/comp/lang/c/16658

Text File | 1992-11-17 | 4.9 KB | 215 lines

Newsgroups: comp.lang.c
Path: sparky!uunet!europa.asd.contel.com!emory!sol.ctr.columbia.edu!ira.uka.de!math.fu-berlin.de!news.netmbx.de!Germany.EU.net!olymp!uran!hermann
From: [e-mail] (Hermann Stamm)
Subject: Re: Printing out trees
Message-ID: <[e-mail]>
Keywords: Printing of trees, PostScript-Output
Sender: [e-mail]
Reply-To: [e-mail] (Hermann Stamm)
Organization: Praktische Informatik III
Date: Tue, 17 Nov 1992 09:40:08 GMT
Lines: 202

/*

Hello all!

In article <[e-mail]> you write:
|> Does anyone have code for printing out arbitrary binary trees,
|> ie, not necessarily full, can have 0, 1 or 2 children?
|>
|> Any sort of method or strategy would be nice, doesn't even
|> really have to be code.  I'm just stumped for a nice, efficient
|> way to do it--everything I've tried has been ugly.
|>
|> -rick

The below function calc is very short and does a good job
for the above problem. It is called initially "calc(v,0,0)"
and generates coordinates for the placement of all nodes of
the tree with root v (in the components x and y).
The range of the coordinates are 0<=x<=number_of_nodes-1
and 0<=y<=depth(v)-1.
It does simply the following:

The y-coordinate of node w is simply its level in the tree
(root has level 0).

The root v gets x-coordinate "number of nodes in left tree",
such that the left subtree will be placed with x-coordinates
in the range 0..v->x-1 and the right subtree in the range
v->x+1..number_of_nodes-1.

The below demo-program generates a random-tree, determines
the coordinates for the layout by the use of calc, and then
generates a PostScript-file with the embedding as output to
stdout.

To use it just do

  demo | lpr -PLASER

to print it on a laser-printer with name LASER or

  demo >x.ps ; gs x.ps    (or "demo | gs -")

for viewing it using GhostScript.


Hope this helps,

   Hermann.


P.S.:  Try "demo 1000 | lpr" ; its fine!

*/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef struct node
  {
  struct node  *left;
  struct node  *right;
  int        x;
  int        y;
  }
* node;

/*----------------------------------------------------------------------------*/

int calc(node v, int height, int offset)
  {
  int count_left;

  if (v==NULL)
    return(0);
  else
    {
    v->y = height++;
    count_left = calc(v->left,height,offset);

    return( count_left + 1 + calc(v->right,height,(v->x=count_left+offset)+1) );
    }
  }

/*----------------------------------------------------------------------------*/

int MAX(int a, int b)
  {
  return(a>b ? a : b);
  }

int depth(node v)
  {
  if (v==NULL)
    return(0);
  else
    return( 1 + MAX(depth(v->left),depth(v->right)) );
  }

node random_tree(int n)
  {
  node v;
  int  nodes_left;

  if (n==0)
    return(NULL);
  else
    {
    nodes_left    = random() % n;
    v        = malloc(sizeof(*v));
    v->left    = random_tree(nodes_left);
    v->right    = random_tree(n-nodes_left-1);
    return(v);
    }
  }

/*----------------------------------------------------------------------------*/

#define ps_translate(x,y)    printf("%f %f translate\n",x,y)
#define ps_rotate(w)        printf("%f rotate\n",w)
#define ps_scale(sx,sy)        printf("%f %f scale\n",sx,sy)
#define ps_setlinewidth(l)    printf("%f setlinewidth\n",l)
#define ps_showpage()        printf("showpage\n")

#define ps_rectangle(x,y,dx,dy)    printf("%f %f moveto %f 0 rlineto 0 %f rlineto ",x,y,dx,dy); \
                                printf("%f 0 rlineto closepath\n",-dx);                      \
                                printf("gsave 0.9 setgray fill grestore stroke\n");

#define ps_circle(x,y,r)    printf("%f %f %f 0 360 arc fill\n",x,y,r)
#define ps_line(x1,y1,x2,y2)    printf("%f %f moveto %f %f lineto stroke\n",x1,y1,x2,y2)

#define ps_node(v)        ps_circle((float) v->x,(float) v->y,0.2)
#define ps_edge(v,w)        ps_line((float) v->x,(float) v->y,(float) w->x,(float) w->y)

void ps_TREE(node v)
  {
  node son;

  if (v!=NULL)
    {
    if ((son=v->left)!=NULL)
      {
      ps_edge(v,son);
      ps_TREE(son);
      }
    if ((son=v->right)!=NULL)
      {
      ps_edge(v,son);
      ps_TREE(son);
      }
    ps_node(v);
    }
  }

void ps_tree(node v, int width, int height)
  {
  if (v!=NULL)
    {
    ps_rectangle(20.0,30.0,536.0,732.0);
    ps_translate(38.0,46.0);
    ps_rotate(-90.0);
    ps_scale(-700.0/(width-1),500.0/(height-1));
    ps_setlinewidth(0.02);
    ps_TREE(v);
    ps_showpage();
    }
  }

/*----------------------------------------------------------------------------*/

void show_tree(node v)
  {
  if (v!=NULL)
    {
    show_tree(v->left);
    printf("%d %d\n",v->x,v->y);
    show_tree(v->right);
    }
  }

/*----------------------------------------------------------------------------*/

int main(int argc, char *argv[])
  {
  node T;
  int  size;

  srandom(time(NULL));

  T = random_tree( (argc<2) ? 10+(random()%100) : atoi(argv[1]) );

  ps_tree(T,calc(T,0,0),depth(T));

/*
  show_tree(T);
*/

  return(0);
  }