Binary Tree

[swaret]

Hi all! i write because ive a little problem with a c++ binary tree. I wrote all the cose, and the program runs, but i have a dubt: the destructor and the copy constructor. i wrote in 3 files: nodo.h, albero.h and albero.cpp (nodo means node, albero means tree)

template<class T>class Albero;
template<class T>class Nodo
{
	friend class Albero<T>;
private:
	T dato;
	Nodo<T> *destro;
	Nodo<T> *sinistro;

public:
	Nodo(const T &d):destro(0), dato(d), sinistro(0){}
	T getdata() const{return dato;}

};

#ifndef ALBERO_H
#define ALBERO_H
#include "nodo.h"

template<class T>class Albero
{
public:
	Albero();
	~Albero();
	void Cancella();
	void inserisciNodo(const T &);

private:
	Nodo<T> *radice;      ->>>>>>>>>>>>>>>>>>radice = root
	void CancellaAiuto(Nodo<T> *);
	void inserisciNodoAiuto(Nodo<T>**, const T &);
};

template<class T>Albero<T>::Albero()
{
	radice =0;
}


template<class T>Albero<T>::~Albero()
{
	Cancella();
	cout<<"Distruggo l'albero\n";
}



template<class T>void Albero<T>::inserisciNodo(const T &dato)
{
	inserisciNodoAiuto(&radice, dato);
}

template<class T>void Albero<T>::Cancella()
{
	CancellaAiuto(radice);
}


//////////////////////////////////////////////////////////////////////////////////////////////////////
template<class T>void Albero<T>::inserisciNodoAiuto(Nodo<T> **ptr, const T &dato)
{
	if(*ptr==0){
		*ptr = new Nodo<T>(dato);
	}
	else
		if(dato < (*ptr)->dato)
			inserisciNodoAiuto(&((*ptr) ->sinistro), dato);
		else
			if(dato >(*ptr) ->dato)
				inserisciNodoAiuto(&((*ptr) ->destro), dato);
			else
				cout<<dato<<"duplicato!"<<endl;
}

template<class T>void Albero<T>::CancellaAiuto(Nodo<T> *ptr)
{
            if( ptr != NULL )
            {
                CancellaAiuto( ptr->sinistro );
                CancellaAiuto( ptr->destro );
                delete ptr;
            }
}

so my question is if, in your opinion, the destructor i wrote is correct, and if i need a copy constructor in this program. I searched in web, in books but i didn't understand if i need to write it.. the program does a visit (i deleted from the code now) and performs a BST Sort.

P.S. i write from italy, so tell me if i have to transalte some words in the code :) and sorry for my english

[Narue]

>if, in your opinion, the destructor i wrote is correct
It looks fine to me.

>if i need a copy constructor in this program
Yes, unless you're okay with two objects aliasing the same tree. Your two options are writing a full copy constructor that clones the tree, or disallowing the operation by making the copy constructor private. You need to consider the same things with an assignment operator as well.

>sorry for my english
No worries, I didn't have any trouble understanding you or your code.

[swaret]

ok, as i thought :) i wrote something like that, as copy constructor:

Albero(const Albero<T> &) <---in declaration

template<class T>class Albero::Albero(const Albero<T> &o)
{
radice = o.radice;
}

my dubt now is that the copy constructor copies only the root (radice), but not the other nodes.

[Narue]

>my dubt now is that the copy constructor copies
>only the root (radice), but not the other nodes.
It doesn't copy anything but the pointer, but the pointer refers to the tree as a whole. To prove this you can create one tree, create another using that copy constructor, then remove all nodes from either tree and the other tree will reflect those changes. Copying a tree involves physically allocating new nodes.

[swaret]

mm ok, maybe i got it, reading some documentation, but is not an easy concept.. ive to do some exercise. the code i wrote for the copy constructor is ok, for u? is the first i write :) the copy constructor accept as argument an Albero<T> Object, and inizialize it as root = object.root

[Narue]

>the code i wrote for the copy constructor is ok, for u?
It likely doesn't do what you want, so no, it's not okay. If that's all you wanted to do in the copy constructor, you could have just used the default copy constructor. It does the same thing.

[swaret]

mm yes, i tried right now, writing

cout<<"normal construct.." in normal constructor

and

cout<<"copy cons..." in the copy constructor

and running the program. Only "normal constr.." is written on monitor. so the copy constructor is not used, i think. maybe i need to create 2 trees in main
Albero<int> treeA
Albero<int> tree B
and
tree A = tree B ?