Home My Faqts Contributors About Help |
Entry | Add Entry Alert - Edit this Entry |
Oct 28th, 2003 14:43
---------------------------------------------------------------------- --- Knud van Eeden --- 25 October 2003 - 07:56 am -------------------- Datastructure: Tree: Binary: Print: Upright: Pretty: How to pretty print a binary tree upright? --- Method: Overview: The preferred method is currently the following: 1. given a binary tree 2. this given binary tree will be printed in a rectangular area on your computer screen 3. therefore you need to know the horizontal x and vertical y coordinate of each of the strings in the given binary tree, to be able to print that string on the correct position within that rectangular area on your screen (or paper). 4. use 2 passes to pretty print this binary tree upright 5. in the first pass you do an inorder traversal of the given binary tree 1. While traversing, from left to right, you store a pointer to the current node, in a rectangular array 2. While traversing, you store the current sum of the lengths of all the strings on the left of the current node, to be able to know the x-position later. 6. in the second pass you go systematically row by row, and from left to right, through the rectangular array in which you stored your binary tree during inorder traversal. 1. if you find a non empty element on that row it is per definition a parent of some childs on the row below 1. then scan the row below for the children of this parents 1. from left to right you go through the row below. If you find a non empty element, you get its pointer. 2. to know if it is a child of the current parent in the row above, you check if the left pointer or right pointer of the current child element is equal to the pointer of that parent 1. each parent has between 0, 1 and 2 children per definition in a binary tree 2. all children of parents on a given row, will be situated on one and the same row below. Thus if you scan 1 row from left to right you will find all children. 3. in a binary tree, children of a parent will be next to each other on the row below. 4. so you can systematically and independently of the other (because the parent and the children are all on the left together) from left to right, find the parent, its 0, 1, 2 children, and draw connection lines between them 5. if a child is found, then draw some connection lines between parent and child 2. because of the printhead can not return, you have to work and repeat the steps for each single horizontal line you are printing with your printhead. This last step is currently still inefficient, as you have to search over and over again for the same information on the same row, so you might decide to use some storage structure to store this relationship of of parent, children and total amount of spaces --- --- Method: Overview: The preferred method is currently the following: 1. given a binary tree e.g. 'red + black * blue' or thus * + blue red black or thus pretty printed * | +-------+--+ | | + blue | +--+---+ | | red black 2. this given binary tree will be printed in a rectangular area on your computer screen 0 1 2 3 4 5 6 7 8 9 0 1 2 3 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 0| | | | | | | | | |*| | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1| | | | | | | | | ||| | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2| | | |+|-|-|-|-|-|+|-|+| | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3| | | ||| | | | | | | ||| | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4| | | |+| | | | | | |b|l|u|e| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5| | | ||| | | | | | | | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 6| |+|-|+|-|-|+| | | | | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 7| ||| | | | ||| | | | | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 8|r|e|d| |b|l|a|c|k| | | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3. therefore you need to know the horizontal x and vertical y coordinate of each of the strings in the given binary tree, to be able to print that string on the correct position within that rectangular area on your screen (or paper). 4. use 2 passes to pretty print this binary tree upright * | +-------+--+ | | + blue | +--+---+ | | red black 5. in the FIRST PASS you do an inorder traversal of the given binary tree An inorder traversal is used because you want here to show the tree upright. That means so that you want to see the leftmost node on the most left part of the screen, the but leftmost node on the butmost left part of the screen, and so on. * 4 | +-------+--+ | | + 2 blue 5 | +--+---+ | | 1 red black 3 An inorder traversal will visit the nodes in the order: 1. red -> 2. + -> 3. black -> 4. * -> 5. blue During this inorder traversal 1. Store the found nodes in an array 1. It is advised not to store the string value of a given node, like here: node max -----------> | +-+-+-+-+-+ | | | | |*| | | +-+-+-+-+-+ | | |+| | |b| | +-+-+-+-+-+ | |r| |b| | | | +-+-+-+-+-+ v depth max --- but instead store a pointer to that node in that array. This because if you store only the string, you throw information away. In the beginning I only stored the string. That works fine for the simplest casess (e.g. when you print a binary tree with only 1 character strings inside, but as soon as you get longer strings to pretty print, you might find out that more information is needed). So soon I realized to solve this problem in a general way, so handling mosts cases, that I needed more information than that. If you know the pointer, you now also which string, you know its left child, by checking the left pointer, you know its right child, by checking its right pointer and so on. So you might find out that you will need that pointer anyhow to determine later which the childs of this node are, in order to draw connection lines +----+---+ between the parent and its 0, 1 or 2 childs. --- If you have chosen the metod of storing your binary tree in an array, so using an array presentation of pointers, you might store the given binary tree initially in an array like this: --- Given the binary tree with a pointer at each node showing its position in the initial storage array: * [1] | +--------------+------+ | | + [2] blue [3] | +------+------+ | | red [4] black [5] --- Then here is its equivalent representation in the array 'binary tree as an array representation': --- +----+-------------+---------+---------------+ | nr | leftpointer | string | rightpointer | +----+-------------+---------+---------------+ +----+-------------+---------+---------------+ | 1 | 2 | "*" | 3 | +----+-------------+---------+---------------+ | 2 | 4 | "+" | 5 | +----+-------------+---------+---------------+ | 3 | -1 | "blue" | -1 | +----+-------------+---------+---------------+ | 4 | -1 | "red" | -1 | +----+-------------+---------+---------------+ | 5 | -1 | "black" | -1 | +----+-------------+---------+---------------+ --- So in the temporary printing storage array, you do not store the string itself (e.g. 'blue, red, black, ...), but so its pointer (or thus in an array representation of the pointers, you store the ROW number of the initial storage array here). That gives you much more information which is needed later when you have to print out the binary tree in the second pass. --- While traversing, from left to right, you store a pointer to the current node, in a rectangular array So store the tree during the inorder traversal like this, by looking at the position of that given node in the array 'binary tree as an array representation' above, and putting that number (e.g. 1 for '*', 2 for '+', 3 for 'blue', 4 for 'red', 5 for 'black') in the correct x position (as determined by a counter for the total amount of nodes currently processed), and y position as determined by the current depth of the tree currently processed) encountered during inorder traversal in the temporary print storage array node max -----------> | +-+-+-+-+-+ | | | | |1| | | +-+-+-+-+-+ | | |2| | |3| | +-+-+-+-+-+ | |4| |5| | | v +-+-+-+-+-+ depth max 2. To get the vertical y position of the string to be printed Its vertical y position is determined by the depth of the given tree. And this information you store in the temporary array, as you store the information of that node precisely on that vertical row. So by going through that temporary storage array later using e.g. a double for next loop (for row=rowmin to rowmax, for column=columnmin to columnmax), you know for each element in that array its y position, and so you know on which line on the screen you have to print that node. 3. To get the horizontal x position of the string to be printed Use the observation that an inorder traversal gives as an endresult the vertical projection of the given nodes of the given binary tree on an horizontal line. And this in the order from left to right. So also the strings of that binary tree are so projected on that horizontal line. So each node has all proceding strings projected before it on that horizontal line. 1. To know the x-position of the string on the screen while printing, you need to know how much spaces you totally have to print on the left of it. Therefore you need to know the total length of all the strings on the left of a given string in a node. The easiest is if you store this information while doing this inorder traversal. 2. While traversing, you store the current sum of the lengths of all the strings on the left of the current node, to be able to know the x-position later. --- 1. If you store during inorder traversal the sum of the lengths of all string before a given node in some global variable sum, which is updated during the inorder traversal with its current value plus the length of the string of the current node. sum = sum + Length( string in current node ) Because you go during the inorder traversal, per definition, through all the nodes from left to right, and with no skipping, in the given binary tree, then so does this sum variable contain the sum of the lengths of all strings in front of that given node. And that is exactly what you want to be able to know the xposition of any given string in the given binary tree on the screen. --- So given the final output of the upright tree (without the connection lines) you determine the x-coordinate of any string: - by counting the sum of the lengths of all strings on the left before it --- So this will be the final output for the given example: 0 1 2 3 4 5 6 7 8 9 0 1 2 3 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | | | | | | | | |*| | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | | |+| | | | | | |b|l|u|e| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |r|e|d| |b|l|a|c|k| | | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ So, the horizontal x-position of the string 'red' is 0 (or thus the sum of the length of all strings on the left of 'red', which is none, thus "", with a length of 0, thus totally 0) the horizontal x-position of the string '+' is 3 (or thus the sum of the length of all strings on the left of '+', which is 'red', with a length of 3, thus totally 3) the horizontal x-position of the string 'black' is 4 (or thus the sum of the length of all strings on the left of 'black', which is 'red', and '+', with a length of 3 and 1, thus totally 4) the horizontal x-position of the string '*' is 9 (or thus the sum of the length of all strings on the left of '*', which is 'red', and '+' and 'black', with a length of 3, 1, and 5 thus totally 9) the horizontal x-position of the string 'blue' is 10 (or thus the sum of the length of all strings on the left of '*', which is 'red', and '+' and 'black' and '*', with a length of 3, 1, 5, and 1 thus totally 10) --- You will find out that you can do that easy during the left to right inorder traversal of the binary tree. As you work during an inorder traversal systematically from left to right, through all nodes, you meet so first all nodes on the left of any given node first. So you can store the inbetween sum of the lengths of the strings of that nodes in a global variable. So you can store for later use this x-position for all the nodes in another array +----+----------------------------------------------------+ | nr | sum length of all strings to the left current node | +----+----------------------------------------------------+ +----+----------------------------------------------------+ | 1 | 9 (=total amount of spaces before '*') | +----+----------------------------------------------------+ | 2 | 3 (=total amount of spaces before '+') | +----+----------------------------------------------------+ | 3 | 10 (=total amount of spaces before 'blue') | +----+----------------------------------------------------+ | 4 | 0 (=total amount of spaces before 'red') | +----+----------------------------------------------------+ | 5 | 4 (=total amount of spaces before 'black') | +----+----------------------------------------------------+ 6. in the SECOND PASS you go systematically row by row, and from left to right, through the rectangular array in which you stored your binary tree during inorder traversal. node max -----------> | +-+-+-+-+-+ | | | | |1| | | +-+-+-+-+-+ | | |2| | |3| | +-+-+-+-+-+ | |4| |5| | | v +-+-+-+-+-+ depth max 1. if you find a non empty element on that row it is per definition a parent of some childs on the row below node max -----------> | +-+-+-+-+-+ | | | | |1| | | +-+-+-+-+-+ +-+-+-+-+-+ | | |2| | |3| | +-+-+-+-+-+ | |4| |5| | | v +-+-+-+-+-+ depth max For example node 1 is the parent of the children 2 and 3 in the row below. 1. then scan the row below for the children of this parents 1. to know if it is a child of the current parent in the row above, you check if the left pointer or right pointer of the current child element is equal to the pointer of that parent 1. each parent has between 0, 1 and 2 children per definition in a binary tree 2. all children of parents on a given row, will be situated on one and the same row below, by definition in this rectangular array representation. Thus if you scan 1 row below, from left to right, you are sure you will find all children that given parent. That comes handy for drawing the connection lines. Because that asks for the x coordinate of the parent, the x coordinate of the left child and the x coordinate of the right child. 3. in a binary tree, children of a parent will be next to each other on the row below. 4. so you can systematically and independently of the other (because the parent and the children are all on the left together) from left to right, find the parent, its 0, 1, 2 children, and draw connection lines between them 5. if a child is found, then draw some connection lines between parent and child 2. from left to right you go through the row below. If you find a non empty element, you get its pointer. For example: +-+-+-+-+-+ | | | |1| | +-+-+-+-+-+ Starting with node 1 on the first row. You determine its up to 2 children, by noting the value of the left pointer of parent node 1. That gives the pointer to the left child. And the value of the right pointer of node 1. That gives the pointer to the right child. Here these values are 2 and 3. You then check the non empty cells in the row below, working from left to right horizontally. First you find 2. Is that a child of that parent 1? Yes, because the left pointer of that parent equals 2. Then you find 3. Is that a child of that parent 1? Yes, because the right pointer of that parent equals 3. +-+-+-+-+-+ | |2| | |3| +-+-+-+-+-+ |4| |5| | | +-+-+-+-+-+ 2. Now printing the found results, using the found x- coordinates of the parent and the x-coordinates of the left child and the right child There is some complication, and also limitation built in, because of the 'printhead' can not return, you have to work and repeat the steps for each single horizontal line you are printing with your printhead. As the arbitrary constraint is used that the printhead can only move from the left to the right and from top to bottom, but can not move backwards in order to be as general as possible, you will have to do the actions for all children and parents AT ONCE, from left to right, while you are on a given row. This last step is currently still inefficient, as you have to search over and over again (here 3 times, for each vertical connection line you draw) for the same information on the same row, to find the x-position of the parents, so you might decide to use some storage structure to store this relationship of of parent, children and total amount of spaces 1. You draw some arbitrary connection lines between 1 given parent and up 2 childs. Here is chosen a connection like the following: | +------+---+ | | You analyze drawing this structure, by breaking it in 3 parts vertically, that is one part for each of the 3 horizontal lines: On each vertical line, you can draw this figure with minimal input: 1. the x-coordinate of the parent 2. the x-coordinate of the left child 3. the x-coordinate of the right child In order to be able to make the connection in say the symmetric middle of any given string, you will also need the length of this string. 4. the length of the string of the parent 2. the length of the string of the left child 3. the length of the string of the right child So in this simplest case of showing a nice pretty print result, you can draw the connection | +------+---+ | | like this below: . ..............> . . length parent . . . . .....................>[stringparent] . x-parent | . +-------+-----------+ . | | ...............>[stringleft] [stringright] . x-left child . . . ............> ............> . length left .length right . . ..................................>. . x-right child . So to draw this structure, | +------+---+ | | you can split it in 3 steps, by going through this structure from row to row vertically down: First you draw one the first horizontal line '|' Then you go one line down, and you draw '+------+---+' Then you go one line down, and you draw '| |' --- Working this out: 1. First print a character '|' at x-position middle of the parent string, or thus at x-position xparent + half of the (length parent string) 2. Then print a string '+------+---+' 1. starting by printing a '+' followed by a number of hyphens '-', and a '+' at the end, thus '+------+' and print this at x-position middle of the left string, or thus at x-position xchild + half of the (length left child string) until you reach the middle of the parent string 2. continue with printing a '+', followed by a number of hyphens '-', thus '+---+' starting at x-position middle of the parent, or thus at x-position xchild + half of the (length left child string) 7. Working all this ideas out for the given example: 1. Given an expression e.g. 'red + black * blue' 2. This expression shown as a binary tree * + blue red black 3, This binary tree is represented in memory in the following datastructure +----+-------------+---------+---------------+ | nr | leftpointer | string | rightpointer | +----+-------------+---------+---------------+ | +----+-------------+---------+---------------+ | | 1 | 2 | "*" | 3 | | +----+-------------+---------+---------------+ | | 2 | 4 | "+" | 5 | | +----+-------------+---------+---------------+ | | 3 | -1 | "blue" | -1 | | +----+-------------+---------+---------------+ | | 4 | -1 | "red" | -1 | | +----+-------------+---------+---------------+ | | 5 | -1 | "black" | -1 | | +----+-------------+---------+---------------+ V node max 3. After doing the inorder traversal, pointers to your binary tree are stored in a temporary array node max -----------> | +-+-+-+-+-+ | | | | |1| | | +-+-+-+-+-+ | | |2| | |3| | +-+-+-+-+-+ | |4| |5| | | | +-+-+-+-+-+ V depth max 4. Also stored are the x-positions of each node +----+----------------------------------------------------+ | nr | sum length of all strings to the left current node | +----+----------------------------------------------------+ +----+----------------------------------------------------+ | | 1 | 9 (=total amount of spaces before '*') | | +----+----------------------------------------------------+ | | 2 | 3 (=total amount of spaces before '+') | | +----+----------------------------------------------------+ | | 3 | 10 (=total amount of spaces before 'blue') | | +----+----------------------------------------------------+ | | 4 | 0 (=total amount of spaces before 'red') | | +----+----------------------------------------------------+ | | 5 | 4 (=total amount of spaces before 'black') | | +----+----------------------------------------------------+ V node max 5. Using the temporary array as a guide node max -----------> | +-+-+-+-+-+ | | | | |1| | | +-+-+-+-+-+ | | |2| | |3| | +-+-+-+-+-+ | |4| |5| | | | +-+-+-+-+-+ V depth max You start building the final to be printed rectangular array: First row one +-+-+-+-+-+ | | | |1| | +-+-+-+-+-+ You find pointer 1. You get the xposition of this node, by looking in step 4 in row 1. That shows 9 spaces to be printed. Get also the string belonging to pointer 1. You get that by using pointer 1, and going to row 1 in table in step 3, and taking the string out there. That gives you '*'. So print this '*' on x-position 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 0| | | | | | | | | |*| | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ As you are completely finished with the current horizontal line, you can move your 'printhead' to the next line below. Now for each of all of the parents of this line, draw a connection line '|' (while staying on the same horizontal line) between the parents and its childs. 0 1 2 3 4 5 6 7 8 9 0 1 2 3 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 0| | | | | | | | | |*| | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1| | | | | | | | | ||| | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ As you are completely finished with the current horizontal line, you can move your 'printhead' to the next line below. Now for each of all of the parents of this line, draw a connection line '+---+--+' (while staying on the same horizontal line) between the parents and its childs 0 1 2 3 4 5 6 7 8 9 0 1 2 3 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 0| | | | | | | | | |*| | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1| | | | | | | | | ||| | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2| | | |+|-|-|-|-|-|+|-|+| | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ As you are completely finished with the current horizontal line, you can move your 'printhead' to the next line below. Now for each of all of the parents of this line, draw a connection line '|' (while staying on the same horizontal line) between the parents and its childs 0 1 2 3 4 5 6 7 8 9 0 1 2 3 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 0| | | | | | | | | |*| | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1| | | | | | | | | ||| | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2| | | |+|-|-|-|-|-|+|-|+| | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3| | | ||| | | | | | | ||| | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --- You are finished with row 1 in the temporary array. So goto row 2. in the temporary array +-+-+-+-+-+ | |2| | |3| +-+-+-+-+-+ You find first pointer 2. You get the xposition of this node, by looking in step 4 in row 2. That shows 3 spaces to be printed. Get also the string belonging to pointer 2. You get that by using pointer 2, and going to row 2 in table in step 3, and taking the string out there. That gives you '+'. So print this '+' on x-position 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 0| | | | | | | | | |*| | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1| | | | | | | | | ||| | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2| | | |+|-|-|-|-|-|+|-|+| | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3| | | ||| | | | | | | ||| | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4| | | |+| | | | | | | | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Then you find pointer 2. You get the xposition of this node, by looking in step 4 in row 3. That shows 10 spaces to be printed. Get also the string belonging to pointer 3. You get that by using pointer 3, and going to row 3 in table in step 3, and taking the string out there. That gives you 'blue'. 0 1 2 3 4 5 6 7 8 9 0 1 2 3 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 0| | | | | | | | | |*| | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1| | | | | | | | | ||| | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2| | | |+|-|-|-|-|-|+|-|+| | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3| | | ||| | | | | | | ||| | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4| | | |+| | | | | | |b|l|u|e| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Now you are finished with this horizontal line, you can move your 'printhead' to the next line Now for each of all of the parents of this line, draw a connection line '|' (while staying on the same horizontal line) between the parents and its childs. 0 1 2 3 4 5 6 7 8 9 0 1 2 3 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 0| | | | | | | | | |*| | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1| | | | | | | | | ||| | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2| | | |+|-|-|-|-|-|+|-|+| | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3| | | ||| | | | | | | ||| | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4| | | |+| | | | | | |b|l|u|e| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5| | | ||| | | | | | | | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ As you are completely finished with the current horizontal line, you can move your 'printhead' to the next line below. Now for each of all of the parents of this line, draw a connection line '+---+--+' (while staying on the same horizontal line) between the parents and its childs 0 1 2 3 4 5 6 7 8 9 0 1 2 3 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 0| | | | | | | | | |*| | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1| | | | | | | | | ||| | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2| | | |+|-|-|-|-|-|+|-|+| | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3| | | ||| | | | | | | ||| | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4| | | |+| | | | | | |b|l|u|e| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5| | | ||| | | | | | | | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 6| |+|-|+|-|-|+| | | | | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ As you are completely finished with the current horizontal line, you can move your 'printhead' to the next line below. Now for each of all of the parents of this line, draw a connection line '|' (while staying on the same horizontal line) between the parents and its childs 0 1 2 3 4 5 6 7 8 9 0 1 2 3 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 0| | | | | | | | | |*| | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1| | | | | | | | | ||| | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2| | | |+|-|-|-|-|-|+|-|+| | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3| | | ||| | | | | | | ||| | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4| | | |+| | | | | | |b|l|u|e| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5| | | ||| | | | | | | | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 6| |+|-|+|-|-|+| | | | | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 7| ||| | | | ||| | | | | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --- You are finished with row 2 in the temporary array. So goto row 3. in the temporary array +-+-+-+-+-+ |4| |5| | | +-+-+-+-+-+ You find first pointer 4. You get the xposition of this node, by looking in step 4 in row 4. That shows 0 spaces to be printed. Get also the string belonging to pointer 24. You get that by using pointer 4, and going to row 4 in table in step 3, and taking the string out there. That gives you 'red'. So print this 'red' on x-position 0 0 1 2 3 4 5 6 7 8 9 0 1 2 3 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 0| | | | | | | | | |*| | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1| | | | | | | | | ||| | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2| | | |+|-|-|-|-|-|+|-|+| | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3| | | ||| | | | | | | ||| | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4| | | |+| | | | | | |b|l|u|e| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5| | | ||| | | | | | | | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 6| |+|-|+|-|-|+| | | | | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 7| ||| | | | ||| | | | | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 8|r|e|d| | | | | | | | | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Then you find pointer 5. You get the xposition of this node, by looking in step 4 in row 5. That shows 4 spaces to be printed. Get also the string belonging to pointer 5. You get that by using pointer 5, and going to row 5 in table in step 3, and taking the string out there. That gives you 'black'. 0 1 2 3 4 5 6 7 8 9 0 1 2 3 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 0| | | | | | | | | |*| | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1| | | | | | | | | ||| | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2| | | |+|-|-|-|-|-|+|-|+| | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3| | | ||| | | | | | | ||| | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4| | | |+| | | | | | |b|l|u|e| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5| | | ||| | | | | | | | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 6| |+|-|+|-|-|+| | | | | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 7| ||| | | | ||| | | | | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 8|r|e|d| |b|l|a|c|k| | | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Now you are finished with this horizontal line, you can move your 'printhead' to the next line As you are on the last line, so per definition you have no more lines below, thus no more childs to check for, you are ready. or thus pretty printed * | +-----+-+ | | + blue | +-+--+ | | red black --- --- Note: This 2 pass process is also a kind of a pattern, as you use the same method to run through the data of creating a graph to determine the minimum and maximum values, after which you can scale that graph correctly in the second pass. --- So you might generalize this idea in saying: Given any graphical representation which needs some kind of a transformation (e.g. scaling) might need 2 passes, one first pass for determining its scaling information (position, minimum, maximum, ...), and the second pass for showing the result of it. --- --- Internet: see also: --- BBCBASIC: Datastructure: Tree: Binary: Print: Upright: How print binary tree upright? Array: Pretty http://www.faqts.com/knowledge_base/view.phtml/aid/26049/fid/768 --- BBCBASIC: Datastructure: Tree: Binary: Print: Upright: How print binary tree upright? Array: String http://www.faqts.com/knowledge_base/view.phtml/aid/26033/fid/768 --- Datastructure: Tree: Binary: Print: Upright: How print binary tree with strings different lengths? http://www.faqts.com/knowledge_base/view.phtml/aid/26017/fid/1266 --- Datastructure: Tree: Binary: Print: Upright: How to print a binary tree upright? http://www.faqts.com/knowledge_base/view.phtml/aid/25819/fid/1266 --- Datastructure: Tree: Binary: Traversal: Walk: Order: How to walk in order a binary tree? http://www.faqts.com/knowledge_base/view.phtml/aid/25844/fid/1266 ----------------------------------------------------------------------
© 1999-2004 Synop Pty Ltd