Hope you all have a great summer: here is some light reading to start it off...
http://info.astrian.net/jargon/ The AI Koans are famous... Problem #13 is always a stretch problem. I think that students found the Fall's version to be harder to start: I hope this was something you could at least take some initial steps to solve. There are many ways to solve #13. Hans' solution adds a new variable to the node to hold the col, makes a pass over the tree to set this value, and then uses that value as it makes a second traverse to print things. Other solutions setup an auxiliary store to hold the information as it comes in. The solution below uses no extra storage and no extra passes. It computes the position on the fly, and is quite short. I've given two versions below: the first just prints the nodes, the second uses the same idea to print both. I have not tried to compile or run these: my initial version was off by one in the numbering, and didn't deal correctly with right subtrees. I've tried to fix both issues below. - jeff parker // Our first version just prints the nodes. // After we understand the problem, we return to the full problem // Note that it it possible to discover our position as we print // root - root of our subtree // col - current x position // row - current y position int treePrintNodes(TreeNode root, int col, int row) { if (null == root) return col; col = treePrintNodes(root.left, col, row+1); drawNode(col++, row); return treePrintNodes(root.right, col, row+1); } Typical call is treePrintNodes(root, 0, 0); // We can use the ideas above: we just need to draw the // link from us to our parent, if we have a parent. // We add two new variables: parent, which lets us know // if we have one, and rightSon, which tells us if our // parent is to our left or to our right - that is, if // we should use the original col or a later one // // root - root of our subtree // parent - parent, if we have one. could be replaced with boolean // col - current x position // row - current y position // rightSon - help us decide if are parent is in the col-1 or at our // return value for col // int treePrint(TreeNode root, TreeNode parent, int col, int row, boolean rightSon) { if (null == root) return col; int parentCol = col - 1; col = treePrint(root.left, root, col, row+1, false); drawNode(col++, row); col = treePrint(root.right, root, mycol, row+1, true); if (null != parent) { if (!left) parentcol = col; drawLink(parentcol, row-1, mycol, row); } return col; } Typical call is treePrint(root, null, 0, 0, false); The value of boolean rightSon isn't used on first call. - jeff parker - axiowave networks - All those who believe in psychokinesis, raise my hand.
