Witam,
mam taką oto klasę:
class node
{
public:
int data;
node* left;
node* right;
int sum; // przechowuje sume elementow
node();
node(int);
~node();
};
Potrzebuję napisać funkcję Suma(), która policzy mi sumę elementów w danym drzewie BST w czasie średnim O(logn) (czyli rekurencja po całym drzewie odpada). Moja prowadząca powiedziała, żeby przechowywać sumę elementów w osobnym polu klasy jednak nie wiem w jaki sposób miałoby to pomóc i bynajmniej jak to zrobić.
Mam do dyspozycji jeszcze funkcję insert:
void insert(node* root, int val)
{
node* p;
node* r;
r = root; p = NULL;
while(r != NULL)
{
if(r -> data == val) return;
p = r;
if(r -> data < val) r = r -> right;
else r = r -> left;
}
r = new node;
r -> data = val;
if(p == NULL) root = r;
else
{
if(p -> data < val) p -> right = r;
else p -> left = r;
}
}
Napisałem taką metodę:
void node::setSum()
{
int s = 0;
if(left != NULL) s += left->data;
if(right != NULL) s += right->data;
sum = s;
}
Ale nie działa poprawnie, bo wywołanie root->setSum() sumuje mi nie to co potrzebuję :/
Byłbym wdzięczny za pomoc,
pozdrawiam