This content has been marked as final.
Show 12 replies

1. Re: Level order (breadthfirst) traversal in a binarygeneral tree
beders Jul 29, 2009 9:51 PM (in response to 807588)Your algorithm is correct, but your tree is painted in a funny way.
Is 2 and 6 on the same level in the second diagram?
If this is a binary tree, 6 is one level down and can't be on the same level as 2.
The same is true for 4.
So given that the lines between your nodes imply childparent relationship, your code and output is absolutely correct.
If you suspect a different output, you can't use a binary tree... 
2. Re: Level order (breadthfirst) traversal in a binarygeneral tree
796440 Jul 29, 2009 11:06 PM (in response to 807588)jssutton11 wrote:
Eh? How is that a binary tree? That statement is not even internally consistent. If a node has one sibling, then its parent has two children. But you seem to be saying that any given node can have only one child (which is more a list than a tree).
Hi, I have a program that converts a general tree into a binary tree that has nodes of one left child and one right sibling.
>
Yeah, seriously, how is that a binary tree?. 1 / 2  6 / / 3  4 7  8  9 / 5

3. Re: Level order (breadthfirst) traversal in a binarygeneral tree
beders Jul 30, 2009 12:34 AM (in response to 796440)jverd, if you assume a line means parent>kid, why should this not be a binary tree? It might be unbalanced, still a binary tree datastructure will do just fine creating such a tree.
If this line connecting nodes means something else, you may be right. 
4. Re: Level order (breadthfirst) traversal in a binarygeneral tree
807588 Jul 30, 2009 3:04 AM (in response to beders)It is a binary tree because each node is only linked to two other nodes, which would normally be called the children, but in this layout it has a left child and a right sibling, or one of them.
The problem is that i have to put out the nodes in the order that I showed you, the odd looking binary tree. 2 and 6 on the same level, and 3 4 7 8 9 on the next level. Does anyone know how I can modify my code to do that? 
5. Re: Level order (breadthfirst) traversal in a binarygeneral tree
EJP Jul 30, 2009 3:59 AM (in response to 807588)in this layout it has a left child and a right sibling, or one of them.
No. The left child has zero or one right siblings. The parent node has one or two children, a left and/or a right. 
6. Re: Level order (breadthfirst) traversal in a binarygeneral tree
796440 Jul 30, 2009 5:35 AM (in response to beders)beders wrote:
I considered that, but it still didn't look right. Maybe I'm just too used to seeing it the normal way. After another look, it seems like it might be okay.
jverd, if you assume a line means parent>kid,
If this line connecting nodes means something else, you may be right.
He did say something about nodes having a sibling, but at the same time seemed to say that a given parent would only have one child, which is impossible. 
7. Re: Level order (breadthfirst) traversal in a binarygeneral tree
796440 Jul 30, 2009 5:36 AM (in response to 807588)jssutton11 wrote:
Well, if you want to invent your own terminology to distinguish between a left and right child, and ignore the usual use of sibling, that's your prerogative, but then I'm outta here.
It is a binary tree because each node is only linked to two other nodes, which would normally be called the children, but in this layout it has a left child and a right sibling, or one of them. 
8. Re: Level order (breadthfirst) traversal in a binarygeneral tree
807588 Jul 30, 2009 4:04 PM (in response to 796440)jverd wrote:
It's not a different terminology. This code takes a general tree and converts it to a binary tree. The only simple way to do this is to take a parent node, and turn it's multiple children into one leftmost child, and that child will have a right sibling, and that right sibling will also have a right sibling. Again, for example:jssutton11 wrote:
Well, if you want to invent your own terminology to distinguish between a left and right child, and ignore the usual use of sibling, that's your prerogative, but then I'm outta here.
It is a binary tree because each node is only linked to two other nodes, which would normally be called the children, but in this layout it has a left child and a right sibling, or one of them.
converts to. 1 /  \ 2 3 4
Hopefully that clears things up. If anyone still has some constructive advice, I'd greatly appreciate it. Thanks.. 1 / 2  3  4

9. Re: Level order (breadthfirst) traversal in a binarygeneral tree
796440 Jul 30, 2009 5:10 PM (in response to 807588)jssutton11 wrote:
This is where you're inventing your own terminology. If a node has a sibling, then those two nodes have the same parent, and that parent has both of those nodes as children. So you've redefined one or more of sibling, parent, child, and, as a consequence, you're now also redefining binary tree.jverd wrote:
It's not a different terminology. This code takes a general tree and converts it to a binary tree. The only simple way to do this is to take a parent node, and turn it's multiple children into one leftmost child, and that child will have a right sibling,jssutton11 wrote:
Well, if you want to invent your own terminology to distinguish between a left and right child, and ignore the usual use of sibling, that's your prerogative, but then I'm outta here.
It is a binary tree because each node is only linked to two other nodes, which would normally be called the children, but in this layout it has a left child and a right sibling, or one of them.
Edited by: jverd on Jul 30, 2009 10:09 AM 
10. Re: Level order (breadthfirst) traversal in a binarygeneral tree
796440 Jul 30, 2009 5:11 PM (in response to EJP)ejp wrote:
And, following along, the right child also has zero or one left siblings, and both siblings share the same parent, and that parent's children are those siblings.in this layout it has a left child and a right sibling, or one of them.
No. The left child has zero or one right siblings. The parent node has one or two children, a left and/or a right. 
11. Re: Level order (breadthfirst) traversal in a binarygeneral tree
807588 Jul 30, 2009 5:26 PM (in response to 807588)The terminology makes sense in the context of the first (nonbinary) tree. The second tree has its own left/right children, but they represent leftmost child and right sibling from the first tree.
Instead of enqueuing just rt.right, you need to enqueue all of the node's siblings before enqueuing rt.left. This would be easier if you knew whether a node was the leftmost child and only enqueing its siblings in that case.
It could help if you posted most code including the creation of a sample tree 
12. Re: Level order (breadthfirst) traversal in a binarygeneral tree
807588 Jul 30, 2009 6:15 PM (in response to 807588)fgb wrote:
Thanks, that actually did it right there, I should have realized that.
Instead of enqueuing just rt.right, you need to enqueue all of the node's siblings before enqueuing rt.left. This would be easier if you knew whether a node was the leftmost child and only enqueing its siblings in that case.
The modified code is this, for anyone interested:
if(rt != null) { queue.enqueue(rt); while(!queue.isEmpty()) { rt = (Node)queue.dequeue(); left = rt.left; if(left != null && left.right != null) right = left.right; else right = null; visit(rt); if(left != null) { queue.enqueue(left); while(right != null) { queue.enqueue(right); if(right.right != null) right = right.right; else right = null; } } } }