El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
HOME Els meus cursos Finalitzats
◄ Anterior
◄

Arbres Binàries

Següent ►
►

Introducció

Un arbre binari és una estructura de dades jeràrquica en la qual cada node té com a màxim dos fills, anomenats fill esquerre i fill dret. Els arbres binaris són fonamentals en la informàtica i s'utilitzen en una àmplia varietat d'aplicacions, com ara la cerca, l'ordenació i la representació d'expressions aritmètiques.

Característiques dels Arbres Binàries

  1. Node: Cada element de l'arbre.
  2. Arrel: El node superior de l'arbre.
  3. Fulla: Un node que no té fills.
  4. Subarbre: Un arbre format per un node i els seus descendents.
  5. Profunditat: La longitud del camí des de l'arrel fins a un node.
  6. Alçada: La longitud del camí més llarg des de l'arrel fins a una fulla.

Tipus d'Arbres Binàries

  1. Arbre Binari Complet: Tots els nivells, excepte possiblement l'últim, estan completament plens, i tots els nodes estan tan a l'esquerra com sigui possible.
  2. Arbre Binari Perfecte: Tots els nivells estan completament plens.
  3. Arbre Binari Degenerat: Cada node té com a màxim un fill. Això fa que l'arbre es comporti com una llista enllaçada.

Operacions Bàsiques

Inserció

La inserció en un arbre binari segueix una sèrie de passos per assegurar que l'arbre es mantingui correcte. A continuació es mostra un exemple d'inserció en un arbre binari:

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

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

# Exemple d'ús
root = Node(50)
root = insert(root, 30)
root = insert(root, 20)
root = insert(root, 40)
root = insert(root, 70)
root = insert(root, 60)
root = insert(root, 80)

Cerca

La cerca en un arbre binari implica recórrer l'arbre per trobar un node amb un valor específic. Aquí teniu un exemple de funció de cerca:

def search(root, key):
    if root is None or root.val == key:
        return root
    if root.val < key:
        return search(root.right, key)
    return search(root.left, key)

# Exemple d'ús
result = search(root, 40)
if result:
    print("Node trobat:", result.val)
else:
    print("Node no trobat")

Recorridos

Hi ha tres tipus principals de recorreguts en un arbre binari:

  1. Preordre: Visita el node arrel, després el subarbre esquerre i finalment el subarbre dret.
  2. Inordre: Visita el subarbre esquerre, després el node arrel i finalment el subarbre dret.
  3. Postordre: Visita el subarbre esquerre, després el subarbre dret i finalment el node arrel.

Exemple de recorreguts:

def preOrder(root):
    if root:
        print(root.val, end=' ')
        preOrder(root.left)
        preOrder(root.right)

def inOrder(root):
    if root:
        inOrder(root.left)
        print(root.val, end=' ')
        inOrder(root.right)

def postOrder(root):
    if root:
        postOrder(root.left)
        postOrder(root.right)
        print(root.val, end=' ')

# Exemple d'ús
print("Preordre:")
preOrder(root)
print("\nInordre:")
inOrder(root)
print("\nPostordre:")
postOrder(root)

Exercici Pràctic

Exercici 1: Inserció i Cerca

  1. Implementa una funció per inserir nodes en un arbre binari.
  2. Implementa una funció per cercar un node en un arbre binari.
  3. Prova les funcions amb un conjunt de dades.

Solució

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

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

def search(root, key):
    if root is None or root.val == key:
        return root
    if root.val < key:
        return search(root.right, key)
    return search(root.left, key)

# Exemple d'ús
root = Node(50)
root = insert(root, 30)
root = insert(root, 20)
root = insert(root, 40)
root = insert(root, 70)
root = insert(root, 60)
root = insert(root, 80)

result = search(root, 40)
if result:
    print("Node trobat:", result.val)
else:
    print("Node no trobat")

Conclusió

En aquesta secció, hem après sobre els arbres binaris, incloent-hi les seves característiques, tipus i operacions bàsiques com la inserció, la cerca i els recorreguts. Els arbres binaris són una estructura de dades fonamental que proporciona una base per a estructures més complexes com els arbres binaris de cerca i els arbres AVL. En el següent mòdul, explorarem els arbres binaris de cerca, que són una extensió dels arbres binaris amb propietats addicionals que faciliten la cerca eficient.

◄ Anterior
◄
Següent ►
►
El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
© Copyright 2024. Tots els drets reservats