Hi, i made a display()function that uses level-order traversal of the tree to display nodes level-by-level.I was told that I needed to put a queue class in my project. the hint was to put the queue in the root, do regular traversal but when we meet the marker, get() the marker from the queue and break the line. Thanks can anyone help me to fix this.
I need to get the something like this in my output
40
30 50
20 35 45 55
here is my code

#include<iostream>
using namespace std;

class ST
{
private:
	struct node
	{ int item;
	node *l, *r;
	node(int x)
	{ 
		item = x; l = 0; r = 0; }
	};

typedef node *link;
link head;

int searchR(link h, int v)
{	if (h == 0) return -55;
	int t = h->item;
	if (v == t) return h->item;
	if (v < t) return searchR(h->l, v); //looking in the left subtree
	else return searchR(h->r, v); // looking in the right subtree
}

void insertR(link& h, int x)
{
	if (h == 0)
	{
	h = new node(x);
	return;
	}
	if (x < h->item)
	insertR(h->l, x);
	else insertR(h->r, x);
}
//display function
void display(node *link)
{
	Queue <node* > q;
	node* marker=link;
	q.put(h);
	while(!q.empty())
	{
		visit(h=q.get());
		if(h->l != 0) q.put(h->l);
		if(h->r != 0) q.put(h->r);
	}
}
public:
	ST()
	{ head = 0; }
	int search(int v)
	{ return searchR(head, v); }
	void insert(int x)
	{ insertR(head, x); }

	void levelOrder()
	{ display(head); }
	
};

int main()
{
	ST tree;
	char oneMore;
	int num;
	do{
		cout<<"Enter an integer:";
		cin>>num;
		tree.insert(num);
		cout<<"Enter 'y' to enter another integer:";
		cin>>oneMore;
	}while(oneMore== 'y');
	tree.traverse();

	tree.levelOrder();

	system("pause");
	return 0;
}

You are recursively traversing the tree right. In each stage you must push the element into a particular queue based on its level. So if the depth of the tree is 3, you'll have 3 queues.
40
30 50
20 35 40 45
you'll be at root at first
when 40 comes, push it in queue 1. Keep a variable to count the stage of recursion. Use your own traversal methods to store 30,50 in queue 2 and 20,35,40,45 in queue 3.

This article has been dead for over six months. Start a new discussion instead.