Như tiêu đề bài viết, thuật toán tính chiều cao của cây của em chạy quá lâu, fail ở 1 vài test unit. Mong mọi người giúp đỡ, cải thiện thuật toán này. Em cám ơn.
Mô tả: tính chiều cao của 1 cây bất kì( số con của 1 nút tùy ý)
Đây là code của em:
class node {
private:
int data;
node* child;
node *sibling;
public:
node() {
data = 0;
child = NULL;
sibling = NULL;
}
int getData() {
return data;
}
void setData(int key) {
data = key;
}
node * getChild() {
return child;
}
void setChild(node* _child)
{
child = _child;
}
node* getSibling() {
return sibling;
}
void setSibling(node *_sibling)
{
sibling = _sibling;
}
};
class tree {
// root
// /
// child 1st -> child 2nd ->child 3rd ....
// ...
private:
node *root;
public:
tree()
{
root = NULL;
}
void constructTheTree(int *p, int n) {
node *temp = new node[n];
std::cout << "constructing..." << std::endl;
for (int i = 0; i < n; i++)
{
temp[i].setData(p[i]);
if (p[i] == -1)
{
root = &temp[i];
}
else {
if (temp[p[i]].getChild() == NULL)
{
temp[p[i]].setChild(&temp[i]);
}
else {
node* posSibling = temp[p[i]].getChild();
while (posSibling->getSibling() != NULL)
{
posSibling = posSibling->getSibling();
}
posSibling->setSibling(&temp[i]);
}
}
}
std::cout << "constructed!" << std::endl;
}
void display(node *n)
{
if (n->getChild() == NULL)
{
std::cout << n->getData() << " ";
}
else {
node *sibling = n->getChild();
display(sibling);
std::cout << n->getData() << " ";
while (sibling->getSibling() != NULL)
{
display(sibling->getSibling());
sibling = sibling->getSibling();
}
}
}
node *getRoot() {
return root;
}
int height(node* n)
{
if (n->getChild() == NULL)
{
return 1;
}
else
{
int heightChild = -1;
node* pos = n->getChild();
while (pos!= NULL)
{
heightChild = (heightChild < height(pos)) ? height(pos) : heightChild;
pos = pos->getSibling();
}
return 1 + heightChild;
}
}
};
Bài này cách dựng cây của nó khá đặc biệt. Cho 1 mảng số gồm n -1 số từ -1 đến n-1, phần tử -1 trong dãy sẽ là Root, phần tử thứ i có giá trị là value[i] sẽ là con của phần tử thứ value[i].
Ví dụ dãy 4 -1 4 1 1. đánh số từ 0 đến 4.
Phần tử thứ 1 là gốc, phần tử thứ 0 và thứ 2 là con của phần tử thứ 4, và phần tử thứ 3 và thứ 4 là 2 con của phần tử thứ 1.
Bài cho 24 test unit. Thuật toán của em tính đúng, nhưng có vẻ quá phức tạp nên bị time limited, ở các test số 7, số 10, …
Mô tả bài toán trong file PDF, problem 2, tree height. Test và code của em trong file .rar.
À mn thử thì nhớ dẫn đường dẫn cho file ở các vị trí em đã comment nhé.
thớt chưa hiểu về DFS rồi.
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?