Following is my logic to traverse level by level an mway search tree....
(Yeah I finally used templates to implement a queue... :) )
void mWayTree:: TraverseLevelOrder(Node *root,int lvl)
{
int i;
int level;
Dq<Node *> Q;
Node *tmp;
Node *tmpPush,*tmpPop;
tmp = new Node(mway);
tmpPop = new Node(mway);
if(root != NULL)
{
level = lvl;
Q.Add(root);
while(!Q.IsEmpty())
{
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);
TraverseLevelOrder(tmpPush,level);
}
}
//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(const 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?
