Write a routine to list out the nodes of a binary tree in le

Write a routine to list out the nodes of a binary tree in level-order. List the root, then nodes at depth 1, followed by nodes at depth 2, and so on. You must do this in linear time. Prove your time bound.

Assume that what is meant by \"list out\" is that the method returns a java.util.List<Integer> containing the data from the tree in level order. Add a new method to your BinaryTree class named levelOrder(). You will need to maintain a data structure to help you control the traversal. You should use something from java.util, but make a good choice that is well-suited to the task at hand. In the comment for levelOrder(), write a brief statement justifying your decision. Test thoroughly.

This is in Java.

Sorry this is a lot - but even an answer to just the first part would be incredibly beneficial.

Solution

typedef struct TreeNode *PtrToNode;

typedef PtrToNode Tree;

struct TreeNode

{

ElementType Element;

Tree Left;

Tree Right;

}

#define MaxElements 100

void Level_order(Tree T)

{

Queue;

if(!T)

return;

Q=createQueue(MaxElements);

Enque(T,Q);

while(!IsEmpty(Q))

{

T=FrontAndDequeue(Q);

ListOut(T);

if(T>Left)

Enqueue(T>Left,Q);

if(T>Right)

Enqueue(T>Right,Q);

}

}