Little by little, I am trying ( as I asked the other day ) to understand the binary tree class. If I ask a lot about it, it is for this reason, excuse me if I ask too much.
I leave you the class (without the function headers):
#ifndef ABIN_H
#define ABIN_H
#include <cassert>
using namespace std;
template <typename T> class Abin {
struct celda; //declaración adelantada privada
public:
typedef celda* nodo;
static const nodo NODO_NULO;
Abin();//constructor
void crearRaizB(const T& e);
void insertarHijoIzqdoB(nodo n, const T& e);
void insertarHijoDrchoB(nodo n, const T& e);
void eliminarHijoIzqdoB(nodo n);
void eliminarHijoDrchoB(nodo n);
void eliminarRaizB();
~Abin(); //destructor
bool arbolVacioB() const;
T elemento(nodo n) const; //acceso a elto, lectura
T& elemento(nodo n); //acceso a elto, lectura/escritura
nodo raizB() const;
nodo padreB(nodo n) const;
nodo hijoIzqdoB(nodo n) const;
nodo hijoDrchoB(nodo n) const;
Abin(const Abin<T>& a); // ctor. de copia
Abin<T>& operator =(const Abin<T>& a); //asignación de árboles
private:
struct celda{
T elto;
nodo padre, hizq, hder;
celda(const T& e, nodo p = NODO_NULO): elto(e), padre(p), hizq(NODO_NULO), hder(NODO_NULO) {}
};
nodo r; //nodo raíz del árbol
void destruirNodos(nodo& n);
nodo copiar(nodo n);
};
At the moment, the questions that assail me are:
1) The cell structure within the class itself, I don't understand this very well, I know that an object of type (class) binary tree will have several structures (which are cells) and each one its attributes (parent pointer, children pointer... ) But in reality a structure, being practically a class, is it as if a class were inside another, right?
If you could explain this to me a little more I would appreciate it.
2) The following line:
celda(const T& e, nodo p = NODO_NULO): elto(e), padre(p), hizq(NODO_NULO), hder(NODO_NULO) {}
This is, if I'm not mistaken, a constructor that initializes its attributes, the e being a constant is mandatory to use the initialization syntax, but the node o ( NODO_NULO = 0
), what exactly is it doing with that pointer? assigns an empty address? Wouldn't that be done with NULL
instead of 0
? Here is its definition:
template <typename T>
const typename Abin<T>::nodo Abin<T>::NODO_NULO(0);
It's not like he's inside , he's inside . One of the principles of encapsulation is to keep hidden (or inaccessible) what an object uses for itself and to keep accessible what is necessary for the object to be manipulated.
As an analogy, imagine a car: the body hides the internal elements such as the engine, the battery, the gearbox, the axles, etc...
Hmm...wonder what will happen if I lick the trowel joint.
You don't need to know that those items are there to use the car (you don't even need to see them) all you need to know is where the pedals, gear lever and ignition are.
In fact, it is likely that you or anyone who uses the car will be tempted to tamper with the elements that are accessible to you, with the possibility of misusing them, the more things that can be tampered with, the more likely they are to be tampered with incorrectly.
Your class
Abin
is encapsulating the objectcelda
because it is a data structure that does not make sense to be used outside said class, defining it as an internal object in the private zone prevents us from instantiating it:But keep in mind that what is private is the identifier, you are making said identifier accessible through the alias
nodo
, you will be able to instantiate objectscelda
outside asAbin
long as you do not use the identifier:In both cases, as long
c
as theyd
are of typeAbin::celda
even though it is an internal type! That is, the alias has broken the encapsulation ofAbin::celda
.You are clear about some concepts and others, however, somewhat confused. The line you highlight is effectively a constructor; you're using what's known as a " constructor initialization list ", which is C++'s utility for initializing an object's sub-objects before the object begins its lifecycle. It is also true that this utility is needed to initialize constant sub-objects:
But none of this is applicable to your structure
celda
since it has no constant members, the following code is equivalent to the one with 1 :Regarding assigning
0
to pointers, it is common practice to indicate that said pointer does not point to anything. But it often causes confusion, for example:One of the variables in the code above is a pointer, but it is difficult to know which one is because it is being used the same as an integer. To avoid this problem, the macro is usually used,
NULL
which (depending on the implementation) can be0
or0L
.But the use of this macro only solves the readability problem, at a functional level it is still confusing:
To avoid this problem, C++11 introduced the null pointer literal
nullptr
:It is effectively a class declared inside another. Since the class
celda
is declared in the partprivate
, you canAbin
onlyAbin
create and use objects of this type.If the class
celda
was declared in the public part ofAlbin
you could create type objects ascelda
follows:Which would be equivalent behavior if it
Abin
were a namespace:Correct
This statement is no longer so correct.
e
is not a constant but a constant reference . References are used to avoid unnecessary copying. Ife
it wasn't a reference, creating an object of typecelda
would create a temporary object of typeT
and then copy its value toelto
... whereas with a reference you avoid the temporary object.A pointer is a variable that stores memory addresses...plain and simple. A very common problem when working with pointers is that they point to invalid regions of memory (they do not point to valid application data) and the standard adopted to detect when a pointer is invalid is to make it point to the region of memory 0x0000.
Thus it is quite common to see pointer initializations such that:
Or checks of the type:
NULL
is a macro defined instddef.h
the following way:Then it is indifferent to use
NULL
or 0 since a 0 will go to the final binary in any of the two cases.Why use
NULL
then? for readability. If it is customary to useNULL
when working with pointers it will be easy to identify them in the code:With C++11 (standard dating from 2011),
nullptr
. Since then it is recommended to abandonNULL
and0
when working with pointers:For what reason?
Because
nullptr
it has a type that prevents it from being used with objects that are not pointers:It also has the advantage that it avoids unexpected behavior when working with overloaded functions: