level order tranversal (breadth-first) code

[imweasel]

Đ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 !

[bete]

Tui thử coi nghen:

1) Trong enqueue():
headPtr[top]= *tempPtr;/* thay vì headPtr[top]= Node2(tempPtr); */

2) Trong dequeue() -> bỏ 3 dòng:

Node2 *tempPtr;
tempPtr = &headPtr[0];
delete tempPtr;

3) Trong ~Tqueue:

delete headPtr; /* thay vì for (int i=0;i<top;i++) dequeue(); */

4) Cái này không phải là bug: trong front():
return &headPtr[0];
==> có thể thay bằng return headPtr;

Nói chung: mình gọi new bao nhiêu lần thì gọi delete chừng đó lần. Trong chương trình của bạn: bạn gọi new 1 lần trong Tqueue() thì bạn gọi delete 1 lần trong ~Tqueue. Các nút khác sẽ được new và delete do phần quản lý cấu trúc cây của bạn

(có gì sai sót mong các bạn chỉ giúp, xin cám ơn trước)

[imweasel]

1 ) cái đấy mình định tạo ra một node mới rồi mới đính vào queue, hic sai luôn về ý tưởng của level order traversal :fear:

2 ) vì cái ý tưởng ban đầu tạo ra node mới rồi cho vào queue đã sai nên cái dequeue sai hết luôn , hic

3 + 4) cách bete đúng là đơn giản hơn hẳn, một phát ăn liền , cái mình luẩn quẩn quá

Bài toán lvl order traversal mình đã giải được rồi, cám ơn bete giúp đỡ. Bài toán này mình cuối cùng giải bằng cách tạo ra một cái struct như sau


struct queueNode
{
Node2 *ptr2TreeNode;
queueNode *ptr2NextQNode;
};


Không hiểu có cách nào hay hơn không :?: