Farel321
07-30-2009, 11:14 AM
Hello, my issue is pretty complex but it all boils down to getting the level-order of a tree. Level-order is basically going down the the tree then printing the nodes based on their level/left to right.
For instance
A
C B
Level order : A C B
I've got the algorithm figured out for a binary tree but not for a regular tree. Basically the node structure i'm going for is LeftMostChild and RightSibling where for tree
A
C B
A's LeftMostChild = C, RightSibling = Null
C's LeftMostChild = Null, RightSibling = B etc...
Code is in no specific language right now for binary tree(I plan on translating it later)
"rc" = Right Child
"lc" = Left Child
print_level_order_binary_tree(n)
{
tree = [];
tree.enqueue(n);
while (tree.length > 0)
{
inner_root = tree[0];
print inner_root.value;
tree.dequeue();
if (inner_root != null && inner_root.lc != null)
tree.enqueue(inner_root.lc);
if (inner_root != null && inner_root.rc != null)
tree.enqueue(inner_root.rc);
}
}
Anyone have an idea for this to work with LeftMostChild and RightSibling?
For instance
A
C B
Level order : A C B
I've got the algorithm figured out for a binary tree but not for a regular tree. Basically the node structure i'm going for is LeftMostChild and RightSibling where for tree
A
C B
A's LeftMostChild = C, RightSibling = Null
C's LeftMostChild = Null, RightSibling = B etc...
Code is in no specific language right now for binary tree(I plan on translating it later)
"rc" = Right Child
"lc" = Left Child
print_level_order_binary_tree(n)
{
tree = [];
tree.enqueue(n);
while (tree.length > 0)
{
inner_root = tree[0];
print inner_root.value;
tree.dequeue();
if (inner_root != null && inner_root.lc != null)
tree.enqueue(inner_root.lc);
if (inner_root != null && inner_root.rc != null)
tree.enqueue(inner_root.rc);
}
}
Anyone have an idea for this to work with LeftMostChild and RightSibling?