I can not understand the structure that I expose below on a binary tree.
Abin header file
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);
};
I understand that we have a cell structure with four elements:
elto
: element (type informationchar
,int
...) that will contain our node.- nodes
padre
,hizq
,hder
: stores an integer in each field that corresponds to the position in which the element is located.
My doubts:
typedef celda* nodo;
What exactly is that line? On which line is the node type defined?
If you had any link to understand it better I would appreciate it because with all this at once, I know the theory, but in practice I get lost.
It is effectively
celda
a structure with four member variables, whereelto
the type to be used by the template (int
,char
, etc) is spatialized.However
padre
,hizq
andhder
are not integers but pointers .The class
Albin
is creating a map of nodes (each node is of typecelda
), where each of these nodes knows both its parent and its left and right nodes. This layout allows you to move bidirectionally within the tree (up and down and vice versa).That line defines an alias, and that alias acts exactly as its name implies. An alias is not a new type but a reference to a given type. In this case, a named alias is being created
nodo
that replaces the typecelda*
.In case you're wondering, aliases serve to improve code readability... when used judiciously. A very clear example can be found when dealing with function pointers:
The syntax gets uglier and uglier the more complex the call to
func
. This code can be much cleaner if an alias is used:In this way, no matter how complex the definition of the function pointer is, the function declaration
ejecutaFuncion
not only remains constant but is also easy to understand.We have already seen that it
nodo
is an alias and that you are defining it in that same line.That is the minor problem of the code that you have shared, but we will start by solving that doubt. That line is a declaration
typedef
that according to the C++ standard (translation and highlights mine):So your line
typedef celda* nodo;
is creating a synonym for the typecelda*
with namenodo
, in other words: to the compilernodo
and pointer tocelda
(celda*
) will be exactly the same.This type of synonym declaration is considered confusing because it doesn't follow the format of other C++ constructs, so a different way of defining synonyms was added in the C++11 standard:
The previous instruction is equivalent to tu
typedef
and is easier to understand because it follows the usual assignment format to which the language has accustomed us, instead it does not allow multiple definitions (as we see in the example oftypedef
the standard), but on the other hand it allows make template synonyms.There is no encapsulation.
The code you share is a terrible design that completely ignores encapsulation principles by giving internal implementation details via the public interface. On the other hand, it does not contain a single search method using a stored type (
T
) but in all cases it expects to receive anodo
to do any operation; in my opinion you should go through the whole implementation and see other examples of binary trees.The type
nodo
is not defined as such, what you have is a pointer to the structcelda
.That is,
nodo
it is the same ascelda
, but it assigns the word/aliasnodo
that is used in the rest of the code so that when it is used in the tree it is easier to understand. For example, it is more visible to putnodo padre
than if I putcelda padre
.typedef
In C++ there are two ways to define an alias, the first that is inherited from C, is with typedef:
typedef tipo_dato_existente alias_de_tipo_dato
and the other way that is already C++,
using alias_de_tipo_dato = tipo_dato_existente
.What are the benefits of using an alias, there are several, one of many is that you separate your data types from the architecture of your PC and the operation of the Operating System, for example the data type
int
is a 32-bit data type in processors of 32 bits, but in a 64bit processor, it is usually 32 or 64bit and this can affect the operation of your program, if it is cross-platform, so you can create an alias for the data type that is needed depending on the system, without the need to change your entire program, you simply change the data type that the alias points to and that's it.what that line does is define an alias called
nodo
which is a pointer to a structure calledcelda
.