program printtrees; {program to print binary trees using a 2 dimensional array. use to show the mirror tree as well as the tree itself. M. Overton, April 26, 2000} {for a binary tree of height n, without slashes marking branches, we will need rowmax = n and colmax = 2^n (2 to the power n). (We won't actually use the last column.) This assumes the height of a tree consisting of a single node is 1. If we want to include slashes, we will need rowmax = 2n and colmax = 2^(n+1).} {const rowmax = 6; colmax = 64; slash = false;} {for height 6} const rowmax = 10; colmax = 64; slash = true; {for height 5} {\$R+} type picture = array[1..rowmax,1..colmax] of char; type tree = ^node; node = record info : char; left, right : tree; end; {\$I Tree} {Activates: BinaryTree} procedure tree2pic( t : tree; row, col, width: integer; var pic: picture); var sub_width : integer; {Make a picture of tree t in the two dimensional array pic, with the root at position row, col. Width specifies the number of columns available in the array for this tree} begin if (t <> nil ) and (row <= rowmax) and (col <= colmax) then {otherwise do nothing} if not slash then begin {simpler without slashes marking branches} pic[row,col] := t^.info; {store the root info} sub_width := width div 2; {only half the width for the subtrees} {put the left subtree in the left half of the picture} tree2pic(t^.left, row + 1, col - sub_width div 2, sub_width, pic); {put the right subtree in the right half of the picture} tree2pic(t^.right, row + 1, col + sub_width div 2, sub_width, pic); end else {a little more complicated with the slashes} begin pic[row,col] := t^.info; {store the root info} sub_width := width div 2; {only half the width for the subtrees} {put the left subtree in the left half of the picture} pic[row + 1, col - sub_width div 4] := '/'; tree2pic(t^.left, row + 2, col - sub_width div 2, sub_width, pic); {put the right subtree in the right half of the picture} pic[row + 1, col + sub_width div 4] := '\'; tree2pic(t^.right, row + 2, col + sub_width div 2, sub_width, pic); end end; {tree2pic} procedure init(var pic : picture); {initialize the picture to all blanks} var i,j : integer; begin for i := 1 to rowmax do for j := 1 to colmax do pic[i,j] := ' '; end; { init } procedure display(pic : picture); {display the picture in the output} var i,j : integer; begin for i := 1 to rowmax do begin for j := 1 to colmax do write(pic[i,j]); writeln; end; end; { display } function mirror(t : tree): tree; { recursively create the mirror image of the tree that t points to} var mtree: tree; begin if t = nil then mirror := nil else begin new(mtree); {get new node for the mirror tree} mtree^.info := t^.info; mtree^.left := mirror(t^.right); {put the MIRROR of the right} mtree^.right := mirror(t^.left); {mirror of the left goes on the right} mirror := mtree; {this is the value returned by the mirror function} end {else part} end;{mirror} var pic : picture; t, mt: tree; dir : char; begin {main} init(pic); {initialize picture} Binary_Tree(t); {get a tree} writeln('binary search tree'); tree2pic(t, 1, colmax div 2, colmax, pic); {make the picture} display(pic); {display it} writeln; writeln('mirror image of tree'); mt := mirror(t); {get the mirror of the original tree} init(pic); {initialize picture again} tree2pic(mt, 1, colmax div 2, colmax, pic); {make picture of mirror tree} display(pic); {display it} readln end.