A tree is a non-linear data structure since each element points to one or more elements of the same type; This is given an element, there is no single path to follow. The element that points to another is called the parent, while the pointed element is known as the child. All elements have a parent except the root. It can be said that a tree is made up of subtrees, thus highlighting its recursive nature.
But...
A binary tree is one in which each element points to at most 2 other elements, commonly called left child and right child.
A binary search tree or ABB, is a binary tree in which for every element, the elements larger than it are located in its right branch, while the smaller elements go in its left branch. Each element is stored only once so there are no repeated elements.
With these right definitions about trees, now these are general concepts of what a tree is, in order to implement them in the C++ language we have to have prior knowledge about linked lists and their implementation.
Each element (node) of an ABB tree has three fields:
-
Data (number, letter, word, etc.), in this case we will use a number (integer).
-
Pointer to the right node.
-
Pointer to the left node.
The pointers have to be of the tree type, since they will point to a node of the same type, this would be an example of what the ABB tree type would be like.
First we create the node:
struct nodo{
int dato;
struct nodo *der;
struct nodo *izq;
};
Pointers are variables that will store in memory the address of another variable, in this case that of a structure called a node.
It is the recursive way in which we will go through each node of the tree, there are three ways to go through it:
- In-order: If we visit the left child first, then the father and finally the right child.
- Pre-order: First the parent, then the left child, and finally the right child.
- Post-order: First left child, then right child and finally father.
There are many concepts about ABB trees, for example, level traversals, depth of a tree, etc.
Traducido del español:
Un árbol es una estructura de datos no lineal puesto que cada elemento apunta a uno o varios elementos del mismo tipo; esto es dado un elemento, no hay un único camino a seguir. El elemento que apunta a otro es llamado padre, mientras que el elemento apuntado se conoce como hijo. Todos los elementos tienen un padre a excepción de la raíz. Puede decirse que un árbol esta formado por subárboles resaltando así su naturaleza recursiva.
Pero...
Un árbol binario es aquel es el que cada elemento apunta como máximo a otros 2 elementos, comúnmente llamados hijo izquierdo e hijo derecho.
Un árbol binario de búsqueda o ABB, es un árbol binario en el cual para todo elemento, los elementos mayores a él, se ubican en su rama derecha, mientras que los elementos menores van en su rama izquierda. Cada elemento se almacena una sola vez por lo que no existen elementos repetidos.
Ya con estas definiciones claras sobre arboles, ahora estos son conceptos generales de lo que es un árbol, para poder implementarlos en lenguaje C++ tenemos que tener conocimientos previos sobre listas enlazadas y su implementación.
Cada elemento(nodo) de un árbol ABB cuenta con tres campos:
-
Dato(numero, letra, palabra, etc), en este caso usaremos un numero(entero).
-
Puntero al nodo derecho.
-
Puntero al nodo izquierdo.
Los punteros tienen que ser del tipo árbol, ya que apuntaran a un nodo del mismo tipo, este seria un ejemplo de como se seria el tipo arbol ABB.
Primero creamos el nodo:
struct nodo{
int dato;
struct nodo *der;
struct nodo *izq;
};
Los punteros son variables que guardaran en la memoria la dirección de otra variable en este caso la de una estructura llamado nodo.
Es la manera recursiva como pasaremos por cada nodo del árbol, existen tres formas para recorrerlo:
- En-orden: Si visitamos primero hijo izquierdo, luego el padre y finalmente el hijo derecho.
- Pre-orden: Primero el padre, luego el hijo izquierdo y finalmente el hijo derecho.
- Post-orden: Primero hijo izquierdo, luego el hijo derecho y finalmente el padre.
Existen muchos conceptos sobre árboles ABB por ejemplo, recorridos por nivel, profundidad de un árbol, etc.