|
(This has to be coded in C++)
Given a string and the node to a tree (top most), we have to print out the tree such that it looks nice.
Say, if there are 1, 2, 3, 4, 5, 6, 7 in the tree (in that order), the it should look like
___1___
_2___3_
4_5_6_7
(looks nice eh?)
Now, the problem is that I don't know how to use nodes. Apparently, when we're given the first node, my friends told me that I have to travel down the node using left, right.
Simply put, I'm lost. If I can have the order of the elements of the tree in in-order, then I can finish the program. Unfortunately, I can't even start.
I can post more details about this tomorrow if anyone is willing to help out.
Also, I think it has to run in O(n). Not sure if it was O(log n) or O(n)
|
so the first thing you wanna do is put the elements into in the tree, breadth-first.
1 procedure BFS(Graph,source):
2 create a queue Q
3 enqueue source onto Q
4 mark source
5 while Q is not empty:
6 dequeue an item from Q into v
7 for each edge e incident on v in Graph:
8 let w be the other end of e
9 if w is not marked:
10 mark w
11 enqueue w onto Q
i just grabbed that from the wiki on http://en.wikipedia.org/wiki/Breadth-first_search
that is a search, but you apply the same principle in populating your tree graph
|
You need to use recursion to travel down the nodes.
Something like:
travel(Node node) {
if (node.left != null) travel(node.left);
if (node.right != null) travel(node.right);
}
There are probably a few ways to solve this. I had a quick think and it's not that trivial, but here's a possible solution:
1. Determine the depth of the tree (this is pretty tricky). The depth will help you format your printout.
2. Travel through the node again, but this time print out the numbers. Use the depth to help you format it.
|
First you'll need to get the depth of the tree. There's probably a routine available for you to do this. Then you need to do a breath-order search as rauk mentioned. As you retrieve each item, you'll need to print out the appropriate number of underscores, which should be a function of what depth you're at and the total depth.
Some hints:
You can detect whether you've reached the end of a particular row by checking whether the total number of elements you've printed out in the current row is a power of 2 and more than you printed out in the above row, at which point you'll print a newline.
There are two types of underscore separations: beginning/end of a row, and between elements
Notice that the number of underscores in each corresponding separation section as you move down the tree decreases exponentially.
|
Hyrule18936 Posts
Using the power of 2 check assumes it's a balanced binary tree. If it's unbalanced, that won't work.
|
|
|
|
|
|
EPT
