República Bolivariana de Venezuela

Ministerio del Poder Popular para la Educación

Instituto Universitario de Tecnología Antonio José de Sucre
Extensión Barinas

Arboles

Guillermo Yunes
30271612
Procesamiento de Datos
07/02/2024
 Definición instructiva y formal de la estructura de árbol.

Son las estructuras de datos más utilizadas, pero también una de las más
complejas, Los Árboles se caracterizan por almacenar sus nodos en forma
jerárquica y no en forma lineal

Concepto de Árbol binario. Ejemplos

Esta estructura se caracteriza por que cada nodo solo puede tener máximo 2
hijo, dicho de otra manera, es un Árbol n-ario de Grado 2

Un árbol binario se ve de esta manera

1
/\
2 3
/\
4 5

Cada nodo tiene como máximo dos hijos: uno a la izquierda y otro a la derecha.
Cada nodo puede tener cero, uno o dos hijos, lo que lo convierte en un árbol
binario.

Operaciones

1. Búsqueda en un árbol binario: Puedes buscar un valor específico en el árbol

binario y determinar si está presente o no.

2. Inserción en un árbol binario: Puedes insertar un nuevo nodo con un valor

dado en el árbol binario de manera que se mantenga la propiedad de orden del
árbol.

3. Eliminación en un árbol binario: Puedes eliminar un nodo con un valor dado

del árbol binario, manteniendo la estructura de árbol binario.

4. Altura de un árbol binario: Puedes calcular la altura o profundidad del árbol

binario, es decir, la longitud del camino más largo desde la raíz hasta una hoja.

5. Recorridos adicionales: Además de los recorridos preorden, inorden y

postorden, también puedes implementar recorridos como nivel por nivel o en
anchura.

Recorrido del árbol binario: Operaciones con árbol binario.

Los recorridos son algoritmos que nos permiten recorrer un árbol en un orden
especifico, los recorridos nos pueden ayudar encontrar un nodo en el árbol, o
buscar una posición determinada para insertar o eliminar un nodo.
Básicamente podemos catalogar las búsquedas en dos tipos, la búsqueda en
profundidad y la búsqueda en amplitud.

Búsqueda de un elemento dentro de una estructura de árbol.

Las búsquedas no informadas son aquellas en que se realiza el viaje por todo el
árbol sin tener una pista de donde pueda estar el dato deseado. Este tipo de
búsquedas también se conocen como búsquedas a ciegas.

Ordenamiento.

El ordenamiento con árbol binario es un algoritmo de ordenamiento, el cual

ordena sus elementos haciendo uso de un árbol binario de búsqueda. Se basa
en ir construyendo poco a poco el árbol binario introduciendo cada uno de los
elementos, los cuales quedarán ya ordenados.

Creación de un árbol binario

class Node:
def __init__(self, key):
self.left = None
self.right = None
.val = key

insert(root, key if root is None:

Node(key)
:
if root.val < key:
root.right = insert(root.right, key)
else:
root.left = insert(root.left, key)
return root

def inorder_traversal(root):
if root:
inorder_traversal(root.left)
print(root.val)
inorder_traversal(root.right)

root = None
keys = [10, 5, 15, 3, 7, 12, 18]

for key in keys:

root = insert(root, key)
 inorder_traversal(root)

En este algoritmo, creamos una clase Node para representar los nodos del
árbol. Luego definimos una función insert para insertar un nuevo nodo en el
árbol de manera ordenada. Finalmente, utilizamos la función inorder_traversal
para imprimir los valores de los nodos en orden ascendente.

Recorrido de un árbol binario

class Node:
def __init__(self, key):
self.left = None
self.right = None
self.val = key

def preorder_traversal(root):
if root:
print(root.val)
preorder_traversal(root.left)
preorder_traversal(root.right)

def inorder_traversal(root):
if root:
inorder_traversal(root.left)
print(root.val)
inorder_traversal(root.right)

def postorder_traversal(root):
if root:
postorder_traversal(root.left)
postorder_traversal(root.right)
print(root.val)

root = None
keys = [10, 5, 15, 3, 7, 12, 18]

for key in keys:

root = insert(root, key)

print("Preorder traversal:")
preorder_traversal(root)

print("\nInorder traversal:")
inorder_traversal(root)
 print("\nPostorder traversal:")
postorder_traversal(root)

En este algoritmo, las funciones preorder_traversal, inorder_traversal y

postorder_traversal se encargan de realizar el recorrido en el árbol en el orden
especificado. Luego creamos un árbol binario con valores de ejemplo y
mostramos los resultados de los tres tipos de recorrido.

Eliminación de un árbol binario

Claro, aquí tienes un ejemplo de un algoritmo de eliminación en un árbol bin:

python
class Node:
__init__(self, key):
self.left = None
self.right = None
self.val key

def minValue(node):
current node
while current.left is not None:
current = current.left
return current

def deleteNode(root, key):

if root is None:
return root

if key < root.val:

root.left = deleteNode(root.left, key)
elif key > root.val:
root.right = deleteNode(root.right, key)
else:
if root.left is None:
temp = root.right
root = None
return temp
elif root.right is None:
temp = root.left
root = None
return temp

temp = minValueNode(root.right)
root.val = temp.val
root.right = deleteNode(root.right, temp.val)

return root
 # Ejemplo de uso
root = Node(10)
root.left = Node(5)
root = Node(20)
root.left.left = Node(3)
root.left.right = Node(7)

print("Árbol original:")
# Recorrer el árbol en orden para imprimir los valores
def inorderTraversal(node):
if node:
inorderTraversal(node.left)
print(node, end=" ")
inorderTraversal(node.right)

inorderTraversal(root)
print("\n")

root = deleteNode(root, 5)

print("Árbol después de eliminar el nodo con valor 5:")

inorder(root)

Este algoritmo de eliminación en un árbol bin elimina un nodo con el valor dado
manteniendo la propiedad de orden del árbol.

Inserción en un árbol binario

python
class Node:
def __init__(self, key):
self.left = None

def insert(root, key):

if root is None:
return Node(key)
else:
if root.val < key:
root.rightpython
class Node:
def _init_(self, key):
self = insert(root.right, key)
else:
root.left = None
 self.right = None
self.val =.left = insert(root.left, key)
return root

# Ejemplo de key

def insert(root, key):

if root is None:
return Node(key uso
root = None
root = insert(root, 10)
insert(root)
else:
if root.val < key:
, 5)
insert(root, 20)

En este root.right = insert(root.right, key)

else:
root.left = insert(root algoritmo, creamos una clase `Node` para
representar.left, key)
return root

# Ejemplo de uso
root = los nodos del árbol y una función `insert` para insertar Node(10)
insert(root, 5)
insert(root, un nuevo nodo con un valor dado en el árbol binario15)
insert(root, 3)
insert(root, 7)

. Luego creamos un árbol binario de ejemplo y en este algoritmo, la función

insert se encarga de insertar elementos realizando algunas inserciones.

Realizar un programa para utilizar árboles. (usar cualquier lenguaje de

programación)

Algoritmo para buscar un elemento en un árbol

class Nodo:
def __init__(self, valor):
self.valor = valor
self.izquierda = None
self.derecha None
 def insertar(raiz, nodo):
ifiz is None:
raiz = nodo
else:
if raiz.valor < nodo.valor:
if raiz.derecha is None:
raiz.derecha = nodo
else:
insertar(raiz.derecha, nodo)
else:
if raiz.izquierda is None:
raiz.izquierda = nodo
else:
insertar(raiz.izquierda, nodo)

def buscar(raiz, valor):

if raiz is None or raiz.valor == valor:
return raiz
if raiz.valor < valor:
return buscar(raiz.derecha, valor)
return buscar(raiz.izquierda, valor)

# Crear un árbol de ejemplo

raiz = Nodo(10)
insertar(raiz, Nodo(5))
insertar(raiz, Nodo(15))
insertar(raiz, Nodo(7)

# Buscar un elemento en el árbol

elemento_buscado = 7
nodo_encontrado = buscar(raiz, elemento_buscado)

if nodo_encontrado:
print(f"Elemento {elemento_buscado} encontrado en el árbol.")
else:
print(f"Elemento {elemento_buscado} no encontrado en el árbol.")

Este algoritmo te permite buscar un elemento específico en un árbol binario de

búsqueda.

Implementación de un árbol en Python:

class Nodo:
def __init__(self, valor):
self.valor = valor
self.izquierda = None
 self.derecha = None

def insertar(raiz, nodo):

if raiz is None:
raiz = nodo
else:
if raiz.valor < nodo.valor:
if raiz.derecha is None:
raiz.derecha = nodo
else:
insertar(raiz.derecha, nodo)
else:
if raiz.izquierda is None:
raiz.izquierda = nodo
else:
insertar(raiz.izquierda, nodo)

def inorder(raiz):
if raiz:
inorder(raiz.izquierda)
print(raiz.valor)
inorder(raiz.derecha)

# Crear un árbol de ejemplo

raiz = Nodo(10)
insertar(raiz, Nodo(5))
insertar(raiz, Nodo(15))
insertar(raiz, Nodo(7))

# Recorrer el árbol en orden

inorder(raiz)

Este programa crea un árbol binario de búsqueda básico en Python y lo recorre

en orden.