Level order traversal,Binary Tree

[APEJMAN]

would you please help me?
I wrote 3 separate line of code for printing my binary tree, and now I am trying to print the level-order traversal of the tree, where the nodes at each level of the tree are printed on a separate line.
my codes are below,( for printing inorder, preorder and post order)
I have no Idea how I can print them in , level-order traversal
I think I should use a Queue, but how? do you have any code that can help me?
would you please help me?
thanks.

template <typename T>
void Tree<T> :: printInOrder (std::ostream& out, TreeNode<T>* rootNode) {
	if (rootNode != NULL) {
		printInOrder (out, rootNode->left);
		out << (rootNode->data) << " ";
		printInOrder (out, rootNode->right);
	}
	return;
}

template <typename T>
void Tree<T> :: printPostOrder (std::ostream& out, TreeNode<T>* rootNode) {
	if (rootNode != NULL) {
		printPostOrder (out, rootNode->left);
		printPostOrder (out, rootNode->right);
		out << (rootNode->data) << " ";
	}
	return;
}

template <typename T>
void Tree<T> :: printPreOrder (std::ostream& out, TreeNode<T>* rootNode) {
	if (rootNode != NULL) {
		out << (rootNode->data) << " ";
		printPreOrder (out, rootNode->left);
		printPreOrder (out, rootNode->right);
	}
	return;

[Ganon11]

You are right; you need to use a queue. Remember that a queue is a FIFO data structure - what you put in first must come out first. Keeping that in mind, when you traverse a tree, which nodes to you usually encounter first? The ones at the top, or the ones at the bottom?

[APEJMAN]

Thanks
so, I came up with this code, but it dosent work,
would you please help me?
thanks

//level-order traversal 
void Tree<T>::breadthFirst()
{
	/* Temporary queue. */
	Queue queue;
	Tree<T> *traverse;

	/*
	* Gotta put something in the queue initially,
	* so that we enter the body of the loop.
	*/
	queue.insert(root);
	while (!queue.isEmpty()) {
		traverse = queue.leave();

		//Visit the node pointed to by traverse.
		/*
		* If there is a left child, add it
		* for later processing.
		*/
		if (traverse->left!= NULL)
			queue.insert(traverse->left);
		/*
		* If there is a right child, add it
		* for later processing.
		*/
		if (traverse->right != NULL)
			queue.insert(traverse->right);
	}

}

[APEJMAN]

I actually was able to write the code.
I am wondering how I can use the setw function in the iomanip library to print out appropriately spaced values so that the tree looks more "tree-like" rather than left-adjusted.
Would you please help me?

//level-order traversal 
template<typename T> 
void Tree<T> :: level_order_traversal(std::ostream& out, TreeNode<T>* rootNode)
{
	/* Temporary queue. */
	Queue <TreeNode<T>*> queue;
	Tree<T> *traverse;

	/*
	* Gotta put something in the queue initially,
	* so that we enter the body of the loop.
	*/
	int dep; //depth of the node
	int temp=0;
	queue.enter(root);
	while (!queue.isEmpty()) {
		rootNode = queue.leave();
		if( depth(rootNode)!=temp){
		temp=depth(rootNode);
		out<<"\n";
		}
		
		out<<rootNode->data<<" ";

		if (rootNode->left!= NULL)
			queue.enter(rootNode->left);

		if (rootNode->right != NULL){
			queue.enter(rootNode->right);
		}
	}


}

[Ganon11]

Hmm...printing trees nicely is very tough. That's actually something I don't know how to do (that is, I don't have any solution fast at hand).

Maybe you can find out how many levels are in your tree (the height of the tree). Let's say the height is 5. So eventually you may have to print 2^(5-1) = 16 numbers in one line (the bottom line). Assuming 2 digit numbers, you want to use setw(3) to print the numbers. 3 spots * 16 numbers = 48 spaces. So your bottom line will take 2^(height-1) * (spaces_per_num ber) spaces (a.k.a. let:

max_size = pow(2, height-1) * spaces_per_numb er; )

Now, your root should be directly in the center of this value (it'll be at the center of the tree). So you move (max_size - spaces_per_numb er) / 2 spaces, print the root, then print a newline. Each time, you need to halve the amount you skip between numbers.

After this, it should just take a little experimentation to figure out where to print numbers, when to print extra spaces, etc. etc.

[APEJMAN]

Thanks,
but I'm not able to write the code, I have no Idea how to make this work
would you please guid me more? or maybe you have a sample code,
thanks again

[dorongnong]

What is your depth function?
I think your depth function is not property working.