use queue to Level traverse a tree

[gskbond]

Following is my logic to traverse level by level an mway search tree....

(Yeah I finally used templates to implement a queue... :) )

void mWayTree:: TraverseLevelOr der(Node *root,int lvl)
{
int i;
int level;
Dq<Node *> Q;
Node *tmp;
Node *tmpPush,*tmpPo p;
tmp = new Node(mway);
tmpPop = new Node(mway);

if(root != NULL)
{
level = lvl;
Q.Add(root);
while(!Q.IsEmpt y())
{

tmp = Q.First();
//Visit keys in first node
cout<<"\nKeys at level "<<level++<<":" ;
for(i = 0; i < tmp->noofKeys; i++)
{
cout<<tmp->keys[i]<<",";
}
//Push children of node at rear of queue;
//TODO check logic to increment level number
for(i = 0; i< tmp->noofKeys + 1 ; i++)
{
tmpPush = new Node(mway);
if(tmp->childPointer[i] != NULL)
{
tmpPush = tmp->childPointer[i];
//Q.Add(tmpPush);
TraverseLevelOr der(tmpPush,lev el);
}

}

//Delete first visited node from queue
Q.Delete(tmpPop );

}
}
}

The code for queue is :

template<class T>
class QNode{ //Node in the queue which will contain one BTree node as data
public:
T data;
QNode<T> *link;
};

template<class T>
class Dq { //Queue manager class to add and delete elements from queue
public:
Dq() {front = rear = NULL;}
~Dq();
bool IsEmpty() const
{return ((front==NULL) ? true: false);}
T First() const;
Dq<T>& Add(const T& x);
Dq<T>& Delete(T& x);
private:
QNode<T> *front;
QNode<T> *rear;
};

template <class T>
Dq<T>::~Dq()
{
//Delete all nodes in queue
QNode<T> *next;
while (front) {
next = front->link;
delete front;
front = next;
}
}


template<class T>
T Dq<T>::First() const
{
// Get first element of queue.
if (!IsEmpty())
{
return front->data;
}
}

template<class T>
Dq<T>& Dq<T>::Add(cons t T& x)
{
// Add x to rear of queue.
// create QNode for new element x
QNode<T> *p = new QNode<T>;
p->data = x;
p->link = NULL;

// add new QNode to rear of queue
if (front) rear->link = p; // if(not empty)
else front = p; // if(empty)
rear = p;

return *this;
}

template<class T>
Dq<T>& Dq<T>::Delete(T & x)
{
// Delete first element if queue is non empty and put it in x.
if (!IsEmpty())
{
// save element in first node
x = front->data;

// delete first node
QNode<T> *p = front;
front = front->link;
delete p;

return *this;
}
}

Now the problem here is that :

When actually tree is like :

4
2 6,8
1 3 5 7 9

Now acc to above level traverse method output is :

Keys at level 0 : 4
Keys at level 1: 2
Keys at level 2: 1
Keys at level 2: 3
Keys at level 1: 6,8
Keys at level 2: 5
Keys at level 2: 7
Keys at level 2: 9

This output format which I think does not really look like a level order traversal which I really want....

I want to show out put this way:

Key at level 0 : 4
Keys at level 1: 2,6,8
Keys at level 2: 1,3,5,7,9

I know there is something logically wrong in above code...But I can not find where? Or is this approach correct?

[newb16]

Let's suppose you just printed node '2' and want to skip to next node on this level instead of printing its children. You need to provide an additional argument to Traverse() function so that it will print only nodes with given level and won't traverse deeper than this level, and then call it for all levels (stop when there are no nodes at some level)

[gskbond]

I still did not get what you are trying to say....this is supposed to be a recursive algorithm...... and I cant figure out whether there is a way to find out which nodes are at same level....any other suggestions?

[gskbond]

Hello any other advise??? I did not get above advise...please reply

[newb16]

Add one more parameter to your traverse function (displaylevel), and print the data only if current level is equal to displaylevel. Make the function return false if nothing is printed for this node or any of its children. Then in main program loop with increasing displaylevel until function returns false.

[gskbond]

I used following code:

bool BTree::AnotherT raverseLevelOrd er(Node *root,int lvl,int displaylevel)
{
int i;
int level;
Dq<Node *> Q;
Node *tmp;
Node *tmpPush,*tmpPo p;
tmp = new Node(mway);
tmpPop = new Node(mway);

if(root != NULL)
{
level = lvl;
Q.Add(root);
while(!Q.IsEmpt y())
{

tmp = Q.First();
//Visit keys in first node
if(level == displaylevel)
{
cout<<"\nKeys at level "<<level + 1<<":";
for(i = 0; i < tmp->noofKeys; i++)
{
cout<<tmp->keys[i]<<",";
}
}
else return false;
//Push children of node at rear of queue;
//TODO check logic to increment level number
for(i = 0; i< tmp->noofKeys + 1 ; i++)
{
tmpPush = new Node(mway);
if(tmp->childPointer[i] != NULL)
{
tmpPush = tmp->childPointer[i];
//Q.Add(tmpPush);
AnotherTraverse LevelOrder(tmpP ush,level+1,lev el+1);
}
else level++;
}

//Delete first visited node from queue
Q.Delete(tmp);
if(Q.IsEmpty()) return false;
}
}
return false;
}

int main(int argc,char* argv[])
{

mWayTree myTree(3);
myTree.Insert(1 );
myTree.Insert(2 );
myTree.Insert(3 );
myTree.Insert(4 );
myTree.Insert(5 );
myTree.Insert(6 );
myTree.Insert(7 );
myTree.Insert(8 );
myTree.Insert(9 );
int i=0;
bool falseIndicator = true;

for(i=0; falseIndicator != false; i++)
falseIndicator = myTree.AnotherT raverseLevelOrd er(myTree.root, 0,i);

getchar();
return 1;
}


But still it is giving out put in same format :
Keys at level 1 : 4
Keys at level 2: 2
Keys at level 3: 1
Keys at level 4: 3
Keys at level 2: 6,8
Keys at level 3: 5
Keys at level 3: 7
Keys at level 3: 9

Please help....its not working

[newb16]

AnotherTraverse LevelOrder(tmpP ush,level+1,lev el+1) ;

this is wrong. Why is it setting displaylevel to current level?

To debug, try first to run the function for some level , e.g. 2 and ensure it works for it. Then add loop by level.