-
Formatting Binary trees
Does anyone of an algorithm that will print a binary tree to a file with just the numbers, but it is spaced in the form of the tree, with sapcing adjusting to the size of the tree? I am hoping some of you can, but I kinda doubt it because it was mart of an assignment in a class of mine, and all of our assignments are based at least 10 years ago, and our professor has no idea what he is doing, and neither our book or him, know how to code it, although he claims to. I know that I could just make it up in this class, but I was just hoping someone could know or at least point me in the right direction.
-
It can be done. You will want to do an inorder traversal of the tree so the tree gets "drawn" from the bottom up. Different types of tree traversals are demonstrated here.
You will also want to perform all the "output" in memory before you dump it to a file. Represent this as a vector of strings, where each index represents a level in the tree.
Can you post a sample of what the output file should look like? Does it need to use "ascii art" like "/" and "\" that lead to childeren?
gg
-
Our professor wants just the nodes, so there wouldn't be any lines between the nodes...
50
20 70
10 30 60 80
It should look basically like that.
-
It didn't space it out like I should have...it should look like a tree, but just with the numbers...Sorry it took a while to respond, but my power has been out for 3 days due to an ice storm.
-
The hardest part of doing this is the spacing the output correctly. Before you do any output, you'll want to fine the "widest" node in the tree, and use that to determine the spacing for all nodes. Consider this output:
Code:
|-----|-----|-10--|
|-----|--4--|-----|-20--|
|--1--|-----|-15--|-----|-30--|
|-----|-----|-----|-----|-----|10000|
Here, the widest node is "10000" with 5 characters, which is also the width used for all nodes. You can literally think of this as a table, where each cell is 5 characters wide with a space inbetween each cell (drawn as "|" in the example). As you do your in-order traversal of the tree, maintain the current row and column where node belongs. You will also have to know which cells are already occupied. For instance, if the subtree at 1 also had nodes 2 and 3, and the subtree at 15 also has 14:
Code:
|-----|-----|-10--|
|-----|--4--|-----|-20--|
|--1--|-----|-15--|
|-----|--2--|
|-----|-----|--3--|
When you go to add 14 to a cell, you will detect that the cell is already occupied by 2, so you have to shift over. Since you are using in-order traversal (the items in bold have not been placed yet), this is easily accoplished by following a simple rule: when placeing a left child in a cell, it must be the last cell on that row. With that rule, you'll end up with:
Code:
|-----|-----|-10--|
|-----|--4--|-----|-----|-20--|
|--1--|-----|-----|-15--|-----|-30--|
|-----|--2--|-14--|-----|-----|-----|10000|
|-----|-----|--3--|
Notice that the subtree at 20 has effectively been shifted over to so that the 2 and 14 don't occupy the same cell.
So we have a fairly simple algorithm, but replace the "-" and "|" characters with spaces and you're left with something that doesn't really look like a tree. This can be fixed by inserting some "ascii art" between each row like so:
Code:
|-----|-----|-10--|
/ \
|-----|--4--|-----|-----|-20--|
/ / \
|--1--|-----|-----|-15--|-----|-30--|
\ / \
|-----|--2--|-14--|-----|-----|-----|10000|
\
|-----|-----|--3--|
If a node has a left child, place a "/" on the next line right below the "|", and do the same with "\" if it has a right child. Here's what the final output would look like:
Code:
10
/ \
4 20
/ / \
1 15 30
\ / \
2 14 10000
\
3
This is an overall design that lays out one way this can be done.
gg
-
