Zwalnianie pamięci drzewa
Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?
Zarejestruj się!

Zwalnianie pamięci drzewa

AutorWiadomość
Temat założony przez niniejszego użytkownika
Zwalnianie pamięci drzewa
» 2017-05-10 11:05:46
Cześć, mam takie pytanie, otóż mam stworzone drzewo, z różnymi węzłami, na podstawie struktury:

C/C++
struct node
{
    wezel * right;
    wezel * left;
    int key;
   
    wezel()
        : right( NULL )
         , left( NULL )
    { }
    ~wezel();
}

wezel::~wezel()
{
    //jak zwolnić pamięć
}

int main()
{
    node * root = NULL;
    //wielokrotne wywołanie insert
    insert( root, tmp_key );
   
    // koniec programu
    ~node();
}



stworzyłem drzewo poprzez dodanie dynamicznie kilkunastu węzłów. Kończę program, i jak powinien wyglądać destruktor do tej struktury?
P-160887
» 2017-05-10 12:00:08
Po prostu przejdź przez każdy węzeł drzewa i usuwaj go. Możesz wykorzystać algorytm DFS.
EDIT: w destruktorze usuwasz węzły left, right

Napisane na kolanie w godzinach pracy :> W każdym razie robiłbym w ten sposób:

C/C++
#include <iostream>
using namespace std;

struct wezel
{
    wezel * right;
    wezel * left;
    int key;
   
    wezel()
        : right( NULL )
         , left( NULL )
    { }
    ~wezel();
};

void insert( wezel * r, int tmp_key );
void przejdz_drzewo( wezel * temp );

wezel * root = NULL;

int main()
{
    insert( root, 5 );
    insert( root, 6 );
    insert( root, 4 );
    insert( root, 3 );
    insert( root, 8 );
    insert( root, 1 );
   
    przejdz_drzewo( root );
   
    cout << "usuwam roota " << root->key << endl;
    delete root;
   
}


void insert( wezel * r, int tmp_key )
{
    wezel * temp = r;
    if( temp == NULL )
    {
        root = new wezel;
        root->key = tmp_key;
    }
   
    else if( tmp_key <= temp->key && temp->left == NULL )
    {
        temp->left = new wezel;
        temp->left->key = tmp_key;
    }
   
    else if( tmp_key > temp->key && temp->right == NULL )
    {
        temp->right = new wezel;
        temp->right->key = tmp_key;
    }
    else if( tmp_key <= temp->key )
    {
        temp = temp->left;
        insert( temp, tmp_key );
    }
    else if( tmp_key > temp->key )
    {
        temp = temp->right;
        insert( temp, tmp_key );
    }
}


void przejdz_drzewo( wezel * temp )
{
    if( temp )
    {
        cout << "Wezel: " << temp->key << endl;
        przejdz_drzewo( temp->left );
        przejdz_drzewo( temp->right );
    }
}

wezel::~wezel()
{
    if( left != NULL )
    {
        cout << "Usuwam wezel " << left->key << endl;
        delete left;
    }
    if( right != NULL )
    {
        cout << "Usuwam wezel " << right->key << endl;
        delete right;
    }
}
P-160896
» 2017-05-10 14:32:12
Nie musisz sprawdzać, czy wskaźnik jest różny od null. delete poradzi sobie z null-pointerem bez problemu.
P-160899
» 2017-05-10 14:43:49
No tak, tylko przy próbie wypisywania, który węzeł jest usuwany odwołam się do NULLa i program się wykrzaczy. Jeśli autor zdecyduje się usunąć ify to niech to zrobic razem z coutami :)
P-160900
» 2017-05-10 19:06:09
Takie rozwiązania, opierające się na "lawinowym" usuwaniu, mają ograniczoną poprawność. Drzewo powinno być stosunkowo odporne ale już w przypadku listy ryzyko otrzymania stack overflow, jest duże.

Wywołujesz destruktor korzenia i on nie skończy pracy dopóki nie zwolni swoich dzieci. Na ich rzecz wywołane zostaną destruktory, które również nie skończą pracy dopóki nie zwolnią swoich dzieci ... i tak do końca struktury.

Jeśli twoje drzewo zacznie się degenerować do listy to z punktu widzenia tego sposobu niczym się nie będzie od niej różnić.

Dlatego lepiej prowadzić destrukcję w klasie drzewo niż w klasie węzeł.

Poza tym, przy lawinowym usuwaniu, DFS nie ma tutaj nic z nim wspólnego, bo takie realizuje automatycznie BFS.

DFS należy właśnie zastosować w konstruktorze drzewa.
P-160913
» 2017-05-11 10:18:09
@croppp, można tak, bez ifów:
C/C++
wezel::~wezel()
{
    cout << "Usuwam wezel " << key << '\n';
    delete left;
    delete right;
}
:)
P-160935
« 1 »
 Strona 1 z 1