imweasel
03-07-2004, 06:15
Đang đọc về binary tree, đến đoạn level order tranversal thì tắc. Hiểu nguyên tắc của nó, dùng thêm một cái queue, nhưng k tài nào implement cái queue đó được :innocent:
// levelOrder : public
void Tree::levelOrder()
{
levelOrderStub(root);
}
// levelOrderStub : private
void Tree::levelOrderStub(Node2 *rt)
{
Tqueue q;
Node2 *p;
q.enqueue(rt);
while ( !q.empty() )
{
p = q.front();
q.dequeue();
cout<<p->getValue()<<' ';
if (p->getLeft() != NULL)
q.enqueue(p->getLeft() );
if (p->getRight() != NULL)
q.enqueue(p->getRight() );
}
cout<<endl;
}
Còn cái queue implement như sau :
//queue.h
class Tqueue {
private :
int size;
int top;
Node2 *headPtr;
public:
Tqueue();
~Tqueue();
Node2 * front();
void enqueue(Node2 *);
void dequeue();
bool empty();
bool full();
};
//queue.cpp
/**
* class Tqueue implementation
*/
#include "queue.h"
Tqueue::Tqueue()
{
size = 10;
top = 0;
headPtr = new Node2[size];
}
Tqueue::~Tqueue()
{
for (int i=0;i<top;i++)
dequeue();
}
void Tqueue::enqueue(Node2 *tempPtr)
{
if ( !full() )
{
headPtr[top]= Node2(tempPtr);
top++;
}
}
void Tqueue::dequeue()
{
if ( !empty() )
{
Node2 *tempPtr;
tempPtr = &headPtr[0];
delete tempPtr;
top--;
for (int i=0;i<top;i++) //shift to head
{
headPtr[i] = headPtr[i+1];
}
}
}
Node2 * Tqueue::front()
{
return &headPtr[0];
}
bool Tqueue::empty()
{
return top==0;
}
bool Tqueue::full()
{
return top == size;
}
Ngoài ra mọi người có thể chỉ ra hộ bug trong cái đống trên không ? Cám ơn mọi người nhiều !
// levelOrder : public
void Tree::levelOrder()
{
levelOrderStub(root);
}
// levelOrderStub : private
void Tree::levelOrderStub(Node2 *rt)
{
Tqueue q;
Node2 *p;
q.enqueue(rt);
while ( !q.empty() )
{
p = q.front();
q.dequeue();
cout<<p->getValue()<<' ';
if (p->getLeft() != NULL)
q.enqueue(p->getLeft() );
if (p->getRight() != NULL)
q.enqueue(p->getRight() );
}
cout<<endl;
}
Còn cái queue implement như sau :
//queue.h
class Tqueue {
private :
int size;
int top;
Node2 *headPtr;
public:
Tqueue();
~Tqueue();
Node2 * front();
void enqueue(Node2 *);
void dequeue();
bool empty();
bool full();
};
//queue.cpp
/**
* class Tqueue implementation
*/
#include "queue.h"
Tqueue::Tqueue()
{
size = 10;
top = 0;
headPtr = new Node2[size];
}
Tqueue::~Tqueue()
{
for (int i=0;i<top;i++)
dequeue();
}
void Tqueue::enqueue(Node2 *tempPtr)
{
if ( !full() )
{
headPtr[top]= Node2(tempPtr);
top++;
}
}
void Tqueue::dequeue()
{
if ( !empty() )
{
Node2 *tempPtr;
tempPtr = &headPtr[0];
delete tempPtr;
top--;
for (int i=0;i<top;i++) //shift to head
{
headPtr[i] = headPtr[i+1];
}
}
}
Node2 * Tqueue::front()
{
return &headPtr[0];
}
bool Tqueue::empty()
{
return top==0;
}
bool Tqueue::full()
{
return top == size;
}
Ngoài ra mọi người có thể chỉ ra hộ bug trong cái đống trên không ? Cám ơn mọi người nhiều !