Testare funzioni alberi binari e generici C++

[Xerox]

Per alcune esercitazioni mi sarebbe molto utile poter testare eventuali mie funzioni su alberi binari o generici.Avete qualche codice che implementa magari delle classi su queste strutture dati?
Oppure mi consigliate qualcosa in particolare?

[Tommy_2]

Io ho un template di albero binario che però non si bilancia ma funziona se ci metti i giusti input Se vuoi te lo scrivo con tanto di esempio con classe affina

[Xerox]

Io ho un template di albero binario che però non si bilancia ma funziona se ci metti i giusti input Se vuoi te lo scrivo con tanto di esempio con classe affina

Qualsiasi cosa è ben accetta
Magari vediamo se si capisce anche il problema dei giusti input

[Tommy_2]

Qualsiasi cosa è ben accetta
Magari vediamo se si capisce anche il problema dei giusti input

In teoria l'albero binario si deve bilanciare da solo, io metto un valore e lui deve aggiustare l'albero affinché sia bilanciato. Ecco io, ora come ora, non mi ci sono messo troppo di impegno e non ho sviluppato una funzione del genere. Comunque ti posto l'albero, il main ed una classe creata al volo.
treenode.h

Spoiler:

#ifndef TREENODE_H
#define TREENODE_H
#include <iostream>
using namespace std;

template<class Tipo>
class Tree;

template<class Tipo>
class TreeNode{
    friend class Tree<Tipo>;
public:
    TreeNode(const Tipo);
private:
    TreeNode<Tipo> *leftPtr;
    Tipo data;
    TreeNode<Tipo> *rightPtr;
};


template <class T>
TreeNode<T>::TreeNode (const T d): data(d), leftPtr (NULL), rightPtr(NULL){}
#endif 

tree.h

Spoiler:

#ifndef TREE_H
#define TREE_H

#include "treenode.h"

template<class Tipo>
class Tree{
public:
    Tree();
    void insertNode(const Tipo);
    void inOrder() const;
    void preOrder() const;
    void postOrder() const;
private:
    TreeNode<Tipo> *treePtr;
    void insertNodeHelper(TreeNode<Tipo> ** , const Tipo);
    void inOrderHelper(TreeNode<Tipo> *) const;
    void preOrderHelper(TreeNode<Tipo> *) const;
    void postOrderHelper(TreeNode<Tipo> *) const;
};

template<class T>
Tree<T>::Tree(): treePtr(NULL){}

template<class T>
void Tree<T>::insertNode(const T dato){
    insertNodeHelper(&treePtr, dato);
}

template<class T>
void Tree<T>::inOrder() const {
    inOrderHelper(treePtr);
}

template<class T>
void Tree<T>::postOrder() const {
    postOrderHelper(treePtr);
}

template<class T>
void Tree<T>::preOrder() const {
    preOrderHelper(treePtr);
}

template<class T>
void Tree<T>::insertNodeHelper(TreeNode<T> **ptr , const T dato){
    if ( *ptr == 0 ) {
        try{
            *ptr = new TreeNode<T>(dato);
        }catch(bad_alloc &e){
            cerr << "Memory Error: "<< e.what()<<endl;
        }
    }
    else{
        if (dato < (*ptr)->data)
            insertNodeHelper(&((*ptr)->leftPtr),dato);
        else if (dato > (*ptr)->data)
            insertNodeHelper(&((*ptr)->rightPtr),dato);
        else
            cout << dato << " duplicato!"<<endl;
    }
}

template<class T>
void Tree<T>::inOrderHelper(TreeNode<T> *ptr) const{
    if (ptr != NULL)
    {
        inOrderHelper(ptr->leftPtr);
        cout << ptr->data << ' ';
        inOrderHelper(ptr->rightPtr);
    }
}

template<class T>
void Tree<T>::preOrderHelper(TreeNode<T> *ptr) const {
    if (ptr != NULL)
    {
        cout << ptr->data << ' ';
        preOrderHelper(ptr->leftPtr);
        preOrderHelper(ptr->rightPtr);
    }
}

template<class T>
void Tree<T>::postOrderHelper(TreeNode<T> *ptr) const {
    if (ptr!=NULL)
    {
        postOrderHelper(ptr->leftPtr);
        postOrderHelper(ptr->rightPtr);
        cout << ptr->data << ' ';
    }
}

#endif 

myclass.h

Spoiler:

#ifndef TEST_H
#define TEST_H
#include <iostream>
using namespace std;

class myclass{
    friend ostream &operator<<(ostream&, const myclass &);
public:
    myclass(int);
    bool operator<(const myclass &) const;
    bool operator>(const myclass &) const;
    int getInt() const{return integer;}
private:
    int integer;
};

#endif 

myclass.cpp

Spoiler:

#include "myclass.h"
#include <iostream>
using namespace std;

myclass::myclass(int i)
{
    integer=i;
}


bool myclass::operator<(const myclass &destro)const{
    return (integer<destro.getInt());
}

bool myclass::operator>(const myclass &destro)const{
    return(destro < *this);
}


ostream &operator<<(ostream& op, const myclass &c){
    op << c.integer;
    return op;
} 

main.cpp

Spoiler:

#include "tree.h"
#include "myclass.h"

int main(){
    Tree<int> prova;
    int val, i=0;
    for (i;i<10;i++){
        cin >> val;
        prova.insertNode(val);
    }
    cout << "Inorder: ";
    prova.inOrder();
    cout <<endl << "Preorder: ";
    prova.preOrder();
    cout <<endl << "Postorder: ";
    prova.postOrder();
    cout << endl;
    myclass i1(50),i2(25),i3(75),i4(12),i5(33),i6(67),i7(88),i8(6),i9(13),i10(68);
    Tree<myclass> test;
    test.insertNode(i1);test.insertNode(i2);test.insertNode(i3);test.insertNode(i4);test.insertNode(i5);test.insertNode(i6);test.insertNode(i7);
    test.insertNode(i8);test.insertNode(i9);test.insertNode(i10);
    cout << "Inorder: ";
    test.inOrder();
    cout <<endl << "Preorder: ";
    test.preOrder();
    cout <<endl << "Postorder: ";
    test.postOrder();
    cout << endl;
    system("PAUSE");
    return 0;
} 

Se come input del cin metti questi valori in questo ordine, avrai lo steso output, sia per l'albero di interi che per l'albero di myclass: 50 25 75 12 33 67 88 6 13 68

[Xerox]

Ti ringrazio.Ora in questi 2 giorni lo guarderò con maggior attenzione perchè oggi non mi è possibile.Comunque dando una breve occhiata non ho visto alcun distruttore...Non ti crea alcun problema?

[Tommy_2]

Ti ringrazio.Ora in questi 2 giorni lo guarderò con maggior attenzione perchè oggi non mi è possibile.Comunque dando una breve occhiata non ho visto alcun distruttore...Non ti crea alcun problema?

Per i semplici test e programmini che ci ho fatto sopra mi basta il distruttore di default del compilatore

[QuasarLex]

Per i semplici test e programmini che ci ho fatto sopra mi basta il distruttore di default del compilatore

guarda che hai problemi di memory leak senza distruttore

[CorralX]

guarda che hai problemi di memory leak senza distruttore

Credo indendesse che poichè in quel programmino di esempio i distruttori vengono chiamati solo quando il programma termina, non è necessario scriverli perchè di leak non c'e ne sono.
Quando il leak si genera, viene anche terminato il programma.

[QuasarLex]

Credo indendesse che poichè in quel programmino di esempio i distruttori vengono chiamati solo quando il programma termina, non è necessario scriverli perchè di leak non c'e ne sono.
Quando il leak si genera, viene anche terminato il programma.

scusa ma non bisogna deallocare i nodi dell' albero?

[devilheart]

Il sistema operativo rilascerà comunque la memoria. Resta il fatto che è un pessimo modo di procedere

[QuasarLex]

Il sistema operativo rilascerà comunque la memoria. Resta il fatto che è un pessimo modo di procedere

in che senso scusa?

[devilheart]

in che senso scusa?

Nel senso che si dovrebbe sempre rilasciare esplicitamente la memoria allocata dinamicamente

[QuasarLex]

no intendo, in che senso l' SO rilascerà cmq la memoria? Se è vero questo allora quand' è che si ha davvero memory leak?

Cmq questo albero senza distruttore è riportato anche sul deitel, mi meraviglio

[CorralX]

Quando un processo viene creato, gli viene assegnata una zona di memoria chiamata spazio degli indirizzi del processo.
Al suo interno vengono inizializzate tutte le strutture dati necessarie per il cosidetto supporto a runtime (tra cui lo stack).
Quando allochi qualcosa finisce in questo spazio di memoria (e non potrebbe essere altrove visto che il processo non vede niente al di fuori del suo spazio degli indirizzi).
Ovviamente quando il processo termina lo spazio degli indirizzi torna al sistema operativo che lo dara al prossimo processo che ne fa richiesta, eliminando ogni cosa allocata e quindi pulendo la memoria.

Il memory leak si ha durante l'esecuzione del processo, quando non si ha piu un puntatore valido a una zona di memoria allocata che quindi e inutilizzabile dal processo stesso. Ma ovviamente nella pulizia generale del sistema operativo alla chiusura del processo quwsta viene ritornata (allocata o non).

Quello che si intendeva e che per esercizi cosi semplici che terminano subito il distruttore non serve perche non c'e leak, anche se sarebbe buona regola scriverlo sempre...

[QuasarLex]

ah capisco, io pensavo che la memoria non deallocata venisse liberata solo con lo shutdown dell' alimentazione.... però giustamente come dici tu bisogna comunque liberarla sempre...

La cosa che mi fa strano come ho scritto è che sul deitel l' albero è implementato senza distruttore e non riesco a spiegarmi perchè...