Simple breadth first question

[myoung34]

I've got a working Binary Tree class, and a working breadth first traversal (using stl queue), but just need someone to help me implement a level feature.
for example, a tree with root 'a' and two children 'b' and 'c' on my program outputs a b c, where i would like it to output
a
b c

Heres my code for breadthfirst

void Tree::breadthfirst(Tree *t) {

	queue<Tree> q;

	q.push(*t);
	while (!q.empty()) {

		*t=q.front();

		q.pop();

		cout << t->RootData() << " ";

		if (t->Left() != NULL)

			q.push(*t->Left());

		if (t->Right() != NULL)

			q.push(*t->Right());

	}

}

[imi]

I haven't tested it, but I think if you insert a "if (q.empty()) cout << endl;" in line 11 (after the pop) this should do the trick.

Ciao, Imi.

[imi]

Ah, no. scratch this idea. Won't work. Sorry.

[imi]

Ok, next shot:

The basic idea: You count the number of items in the next level (variable "next") while you decrease the "current" level until you reach the end. Then you know that you are at a "level border" and the next level's count becomes current count and you start counting children again..

void Tree::breadthfirst(Tree *t) {
	queue<Tree> q;

	q.push(*t);
	int current = 1, next = 0;

	while (!q.empty()) {

		*t=q.front();
		q.pop();

		cout << t->RootData() << " ";
		if (!--current)
		{
			cout << endl;
			current = next;
			next = 0;
		}

		if (t->Left() != NULL)
		{
			q.push(*t->Left());
			++next;
		}

		if (t->Right() != NULL)
		{
			q.push(*t->Right());
			++next;
		}
	}
}

It's completely untested, so excpect some bugs. Hope the general idea works this time *g*.

Ciao, Imi.

[myoung34]

Almost, but it fails on larger trees such as
a
b c
d e f

on that tree, it outputs:
a
b c d e f

[imi]

Even the second version? Hm..

Well, what you could also do, is to insert some "end of level" marker (e.g. null pointer) into the queue every time you reached the last "end of line".

void Tree::breadthfirst(Tree *t) {
	queue<Tree> q;

	q.push(*t);
	q.push(0);

	while (q.size() > 1) { // one nullptr will always remain in the list. So test for size>1

		*t=q.front();
		q.pop();
		if (!t) { cout << endl; q.push(0); continue; }

		cout << t->RootData() << " ";

		if (t->Left() != NULL)
			q.push(*t->Left());

		if (t->Right() != NULL)
			q.push(*t->Right());
	}
}

Ciao, Imi.