Un árbol es una estructura de datos popular que no es lineal por naturaleza. A diferencia de otras estructuras de datos como array, pila, cola y lista enlazada que son de naturaleza lineal, un árbol representa una estructura jerárquica. La información de pedido de un árbol no es importante. Un árbol contiene Nodes y 2 punteros. Estos dos punteros son el hijo izquierdo y el hijo derecho del Node padre. Entendamos los términos de árbol en detalle.
- Raíz: La raíz de un árbol es el Node superior del árbol que no tiene un Node padre. Solo hay un Node raíz en cada árbol.
- Edge: Edge actúa como un enlace entre el Node principal y el Node secundario.
- Hoja: Un Node que no tiene hijos se conoce como el Node hoja. Es el último Node del árbol. Puede haber múltiples Nodes de hoja en un árbol.
- Profundidad: la profundidad del Node es la distancia desde el Node raíz hasta ese Node en particular.
- Altura: La altura del Node es la distancia desde ese Node hasta el Node más profundo del árbol.
- Altura del árbol: La Altura del árbol es la altura máxima de cualquier Node.
árbol
—-
j <– raíz
/ \
f k
/ \ \
a h z <– hojas
¿Por qué usar árboles?
1. Una razón para usar árboles podría ser porque desea almacenar información que naturalmente forma una jerarquía. Por ejemplo, el sistema de archivos en una computadora:
sistema de archivos
———–
usuario <– raíz
/ \
. . . inicio
/ \
curso de ugrad
/ / | \
. . . cs101 cs112 cs113
2. Los árboles (con cierto orden, por ejemplo, BST) proporcionan acceso/búsqueda moderados (más rápido que la Lista enlazada y más lento que las arrays).
3. Los árboles proporcionan una inserción/eliminación moderada (más rápida que las arrays y más lenta que las listas enlazadas desordenadas).
4. Al igual que las listas enlazadas y, a diferencia de las arrays, los árboles no tienen un límite superior en el número de Nodes, ya que los Nodes se enlazan mediante punteros.
Las principales aplicaciones de los árboles incluyen:
- Manipular datos jerárquicos.
- Haga que la información sea fácil de buscar (consulte el recorrido del árbol).
- Manipular listas ordenadas de datos.
- Como un flujo de trabajo para componer imágenes digitales para efectos visuales.
- Algoritmos de enrutador
- Forma de toma de decisiones en varias etapas (ver ajedrez empresarial).
Árbol binario: Un árbol cuyos elementos tienen como máximo 2 hijos se llama árbol binario. Dado que cada elemento en un árbol binario puede tener solo 2 hijos, normalmente los llamamos hijo izquierdo y derecho.
Representación de árbol binario: un árbol se representa mediante un puntero al Node superior del árbol. Si el árbol está vacío, el valor de la raíz es NULL.
Un Node de árbol contiene las siguientes partes.
- Datos
- Puntero al niño izquierdo
- Puntero al niño derecho
En C, podemos representar un Node de árbol usando estructuras. En otros idiomas, podemos usar clases como parte de su característica OOP. A continuación se muestra un ejemplo de un Node de árbol con datos enteros.
C
// Structure of each node of the tree
struct node
{
int data;
struct node* left;
struct node* right;
};
C++
//Use any below method to implement Nodes of tree
// Method 1: Using "struct" to make
// user-define data type
struct node
{
int data;
struct node* left;
struct node* right;
};
// Method 2: Using "class" to make
// user-define data type
class Node
{
public:
int data;
Node* left;
Node* right;
};
Python
# A Python class that represents # an individual node in a Binary Tree class Node: def __init__(self,key): self.left = None self.right = None self.val = key
Java
// Class containing left and right child
// of current node and key value
class Node
{
int key;
Node left, right;
public Node(int item)
{
key = item;
left = right = null;
}
}
C#
// Class containing left and right child
// of current node and key value
class Node
{
int key;
Node left, right;
public Node(int item)
{
key = item;
left = right = null;
}
}
Javascript
<script>
/* Class containing left and right child of current
node and key value*/
class Node
{
constructor(item)
{
this.key = item;
this.left = this.right = null;
}
}
// This code is contributed by umadevi9616
</script>
Operación básica en el árbol binario:
- Insertar un elemento.
- Eliminación de un elemento.
- Buscando un elemento.
- Atravesando un elemento. Hay tres tipos de recorridos en un árbol binario que se discutirán más adelante.
Operación auxiliar en árbol binario:
- Encontrar la altura del árbol.
- Encuentra el nivel del árbol.
- Encontrar el tamaño de todo el árbol.
Aplicaciones del árbol binario:
- En los compiladores, se utilizan árboles de expresión, que es una aplicación de árbol binario.
- Los árboles de codificación de Huffman se utilizan en algoritmos de compresión de datos.
- Priority Queue es otra aplicación de árbol binario que se utiliza para buscar el máximo o el mínimo en la complejidad de tiempo O (logN).
Recorridos de árboles binarios:
- PreOrder Traversal: Aquí, el recorrido es: raíz – hijo izquierdo – hijo derecho. Significa que primero se recorre el Node raíz, luego su hijo izquierdo y finalmente el hijo derecho.
- InOrder Recorrido: Aquí, el recorrido es: hijo izquierdo – raíz – hijo derecho. Significa que primero se recorre el hijo izquierdo, luego su Node raíz y finalmente el hijo derecho.
- PostOrder Traversal: Aquí, el recorrido es: hijo izquierdo – hijo derecho – raíz. Significa que primero se recorre el hijo izquierdo, luego el hijo derecho y finalmente su Node raíz.
Recorramos el siguiente árbol con los tres métodos de recorrido:
Tree
________________
1 //Root Node
/ \
2 3
/ \ / \
4 5 6 7 //Leaf Nodes
PreOrder Recorrido del árbol anterior: 1-2-4-5-3-6-7
InOrder Recorrido del árbol anterior: 4-2-5-1-6-3-7
PostOrder Recorrido del árbol anterior: 4-5 -2-6-7-3-1
Primer árbol simple
Vamos a crear un árbol simple con 4 Nodes. El árbol creado sería el siguiente.
tree
----
1 <-- root
/ \
2 3
/
4
C++
#include <bits/stdc++.h>
using namespace std;
class Node {
public:
int data;
Node* left;
Node* right;
// Val is the key or the value that
// has to be added to the data part
Node(int val)
{
data = val;
// Left and right child for node
// will be initialized to null
left = NULL;
right = NULL;
}
};
int main()
{
/*create root*/
Node* root = new Node(1);
/* following is the tree after above statement
1
/ \
NULL NULL
*/
root->left = new Node(2);
root->right = new Node(3);
/* 2 and 3 become left and right children of 1
1
/ \
2 3
/ \ / \
NULL NULL NULL NULL
*/
root->left->left = new Node(4);
/* 4 becomes left child of 2
1
/ \
2 3
/ \ / \
4 NULL NULL NULL
/ \
NULL NULL
*/
return 0;
}
C
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node* left;
struct node* right;
};
/* newNode() allocates a new node
with the given data and NULL left
and right pointers. */
struct node* newNode(int data)
{
// Allocate memory for new node
struct node* node
= (struct node*)malloc(sizeof(struct node));
// Assign data to this node
node->data = data;
// Initialize left and
// right children as NULL
node->left = NULL;
node->right = NULL;
return (node);
}
int main()
{
/*create root*/
struct node* root = newNode(1);
/* following is the tree after above statement
1
/ \
NULL NULL
*/
root->left = newNode(2);
root->right = newNode(3);
/* 2 and 3 become left and right children of 1
1
/ \
2 3
/ \ / \
NULL NULL NULL NULL
*/
root->left->left = newNode(4);
/* 4 becomes left child of 2
1
/ \
2 3
/ \ / \
4 NULL NULL NULL
/ \
NULL NULL
*/
getchar();
return 0;
}
Java
// Class containing left and right child
// of current node and key value
class Node {
int key;
Node left, right;
public Node(int item)
{
key = item;
left = right = null;
}
}
// A Java program to introduce Binary Tree
class BinaryTree {
// Root of Binary Tree
Node root;
// Constructors
BinaryTree(int key) { root = new Node(key); }
BinaryTree() { root = null; }
public static void main(String[] args)
{
BinaryTree tree = new BinaryTree();
// create root
tree.root = new Node(1);
/* following is the tree after above statement
1
/ \
null null */
tree.root.left = new Node(2);
tree.root.right = new Node(3);
/* 2 and 3 become left and right children of 1
1
/ \
2 3
/ \ / \
null null null null */
tree.root.left.left = new Node(4);
/* 4 becomes left child of 2
1
/ \
2 3
/ \ / \
4 null null null
/ \
null null
*/
}
}
Python
# Python program to introduce Binary Tree # A class that represents an individual node # in a Binary Tree class Node: def __init__(self, key): self.left = None self.right = None self.val = key if __name__ == '__main__': # Create root root = Node(1) ''' following is the tree after above statement 1 / \ None None''' root.left = Node(2) root.right = Node(3) ''' 2 and 3 become left and right children of 1 1 / \ 2 3 / \ / \ None None None None''' root.left.left = Node(4) '''4 becomes left child of 2 1 / \ 2 3 / \ / \ 4 None None None / \ None None'''
C#
// A C# program to introduce Binary Tree
using System;
// Class containing left and right child
// of current node and key value
public class Node {
public int key;
public Node left, right;
public Node(int item)
{
key = item;
left = right = null;
}
}
public class BinaryTree {
// Root of Binary Tree
Node root;
// Constructors
BinaryTree(int key) {
root = new Node(key);
}
BinaryTree() {
root = null;
}
// Driver Code
public static void Main(String[] args)
{
BinaryTree tree = new BinaryTree();
// Create root
tree.root = new Node(1);
/* Following is the tree after above statement
1
/ \
null null */
tree.root.left = new Node(2);
tree.root.right = new Node(3);
/* 2 and 3 become left and right children of 1
1
/ \
2 3
/ \ / \
null null null null */
tree.root.left.left = new Node(4);
/* 4 becomes left child of 2
1
/ \
2 3
/ \ / \
4 null null null
/ \
null null
*/
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
/* Class containing left and right child of current
node and key value*/
class Node {
constructor(val) {
this.key = val;
this.left = null;
this.right = null;
}
}
// A javascript program to introduce Binary Tree
// Root of Binary Tree
var root = null;
/*create root*/
root = new Node(1);
/* following is the tree after above statement
1
/ \
null null */
root.left = new Node(2);
root.right = new Node(3);
/* 2 and 3 become left and right children of 1
1
/ \
2 3
/ \ / \
null null null null */
root.left.left = new Node(4);
/* 4 becomes left child of 2
1
/ \
2 3
/ \ / \
4 null null null
/ \
null null
*/
// This code contributed by umadevi9616
</script>
Resumen: Tree es una estructura de datos jerárquica. Los usos principales de los árboles incluyen el mantenimiento de datos jerárquicos, proporcionando acceso moderado y operaciones de inserción/eliminación. Los árboles binarios son casos especiales de árboles en los que cada Node tiene como máximo dos hijos.
A continuación se muestran el conjunto 2 y el conjunto 3 de esta publicación.
Propiedades del árbol binario
Tipos de árbol binario
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA