sinix

hello all,
i have a question about displaying a binary-tree.
there is a binary tree.we got the root ptr(but we don't know the concrete structure of the tree).
the treeNode is defined as :
//-------------------------------
typedef struct treeNode
{
char value;
struct treeNode* leftChild;
struct treeNode* rightChild;
}treeNode;
//--------------------------------
for example,if the tree structure is:
A
/ \
B C
/ \
D E
the output will be:
A
B C
D E
that is treeNodes in one level will be in one line.
how to implement it?
Someone can help me?thankS Very MUCH~!~!~!~! :o

InfoGeek

It's called Level-Order traversal.
First google result.

__________________
PFO - My daily dose of technology.

Narue

>how to implement it?
As stated (probably without formatting), a level order traversal will do exactly what you want with minimal effort. On the other hand, if you want to actually print out a well spaced textbook structure:
It's harder, but you can use a level order traversal as your starting point. The only tricky part is printing the spaces to the left of subtrees. You need to figure out the height of the subtree and calculate the spaces accordingly.

__________________
Even if the voices aren't real, they have some pretty good ideas.

DaWei

I've used a "template" and I've used "gotoxy" (the latter isn't portable). You can see the results here.

__________________
Abstraction doesn't make it impossible to write bad code; it makes it possible to write superior code.
Contributor's Corner: Grumpy on C++ Exceptions DaWei on Pointers

Narue

>I've used a "template" and I've used "gotoxy" (the latter isn't portable).
I don't even bother and just print it out sideways.

__________________
Even if the voices aren't real, they have some pretty good ideas.

DaWei

Oh hell, half the stuff I do is inside out, one just adopts an appropriate viewpoint :o .

__________________
Abstraction doesn't make it impossible to write bad code; it makes it possible to write superior code.
Contributor's Corner: Grumpy on C++ Exceptions DaWei on Pointers

sinix

thank you.But I still can't got it.When I first got this question ,I thought that I should use level order travesal.but the problem is we do not got the concrete structure of the tree,that is I don't know when is the end of a level.i don't know when to change to the next level.

DaWei

What does that mean? One presumes it is a valid tree, even if incomplete. Write a traversal that carries the level with it. Shoot, add a level variable to the node, if you like.

__________________
Abstraction doesn't make it impossible to write bad code; it makes it possible to write superior code.
Contributor's Corner: Grumpy on C++ Exceptions DaWei on Pointers

sinix

I mean that we know this is a binary tree structured with binary linked list and ONLY got the root ptr without any infomation else.
if i don't add a level tag to the treeNode,can i implement what i want?
thank you.....

The Dark

Write a recursive function that traverse a tree level and pass both a node and the current level in to the function. Inside the function, if you are above the level you want to print, recurse down to the left and right children, if you are on the level you want to print, the print this node. Return back a true or false depending on whether your or one of your children printed something.
At the top level just keep calling the function incrementing the required level by 1 until it retunrs false.

Note that this method will print out the nodes at each level, but will not attempt to space them out as Narue indicated.

Also note that there is probably a more efficient method of doing this, rather than traversing the tree down all the time.