Simple breadth first question

Mar 18, 2010 at 3:13pm
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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());

	}

}
Mar 18, 2010 at 3:26pm
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.
Mar 18, 2010 at 3:28pm
Ah, no. scratch this idea. Won't work. Sorry.
Mar 18, 2010 at 3:41pm
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..


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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.
Mar 18, 2010 at 3:50pm
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
Mar 18, 2010 at 5:52pm
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".

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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.
Topic archived. No new replies allowed.