El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència

HOME

En aquesta secció, posarem en pràctica els conceptes apresos sobre arbres. Els exercicis estan dissenyats per reforçar la comprensió de les estructures d'arbres, incloent arbres binaris, arbres binaris de cerca, arbres AVL i arbres B. Cada exercici inclou una solució detallada per ajudar-te a verificar el teu treball i entendre millor els conceptes.

Exercici 1: Creació d'un Arbre Binari

Enunciat

Crea una estructura d'arbre binari en Python. Implementa les operacions bàsiques següents:

Inserir un node.
Recórrer l'arbre en preordre, inordre i postordre.

Solució

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

# Funció per inserir un nou node
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

# Funció per recórrer l'arbre en preordre
def preOrder(root):
    if root:
        print(root.val, end=" ")
        preOrder(root.left)
        preOrder(root.right)

# Funció per recórrer l'arbre en inordre
def inOrder(root):
    if root:
        inOrder(root.left)
        print(root.val, end=" ")
        inOrder(root.right)

# Funció per recórrer l'arbre en postordre
def postOrder(root):
    if root:
        postOrder(root.left)
        postOrder(root.right)
        print(root.val, end=" ")

# 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)

print("Recorregut en preordre:")
preOrder(root)

print("\nRecorregut en inordre:")
inOrder(root)

print("\nRecorregut en postordre:")
postOrder(root)

Explicació

Node Class: Defineix un node amb atributs per als fills esquerre i dret i el valor del node.
Insert Function: Insereix un nou node en l'arbre binari. Si el node arrel és None, crea un nou node. Si no, compara el valor del node arrel amb el valor a inserir i decideix si ha d'anar a l'esquerra o a la dreta.
Traversal Functions: Les funcions preOrder, inOrder i postOrder recorren l'arbre en preordre, inordre i postordre respectivament, imprimint els valors dels nodes.

Exercici 2: Verificar si un Arbre és un Arbre Binari de Cerca (BST)

Enunciat

Escriu una funció que verifiqui si un arbre donat és un arbre binari de cerca (BST).

Solució

def isBST(root, left=None, right=None):
    if root is None:
        return True

    if left is not None and root.val <= left.val:
        return False

    if right is not None and root.val >= right.val:
        return False

    return isBST(root.left, left, root) and isBST(root.right, root, right)

# 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)

print("És un BST?", isBST(root))

Explicació

isBST Function: Aquesta funció comprova si un arbre és un BST. Utilitza els paràmetres left i right per mantenir el rang de valors permès per als nodes fills. Si el valor del node actual no compleix les condicions del BST, retorna False. Si tots els nodes compleixen les condicions, retorna True.

Exercici 3: Rotacions en un Arbre AVL

Enunciat

Implementa les rotacions simples (esquerra i dreta) en un arbre AVL per mantenir l'equilibri.

Solució

class AVLNode:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key
        self.height = 1

def getHeight(node):
    if not node:
        return 0
    return node.height

def rightRotate(y):
    x = y.left
    T2 = x.right

    x.right = y
    y.left = T2

    y.height = max(getHeight(y.left), getHeight(y.right)) + 1
    x.height = max(getHeight(x.left), getHeight(x.right)) + 1

    return x

def leftRotate(x):
    y = x.right
    T2 = y.left

    y.left = x
    x.right = T2

    x.height = max(getHeight(x.left), getHeight(x.right)) + 1
    y.height = max(getHeight(y.left), getHeight(y.right)) + 1

    return y

# Exemple d'ús
root = AVLNode(30)
root.left = AVLNode(20)
root.left.left = AVLNode(10)

print("Abans de la rotació:")
print("Arrel:", root.val)
print("Esquerra:", root.left.val)
print("Esquerra de l'esquerra:", root.left.left.val)

root = rightRotate(root)

print("\nDesprés de la rotació:")
print("Arrel:", root.val)
print("Dreta:", root.right.val)
print("Esquerra:", root.left.val)

Explicació

AVLNode Class: Defineix un node AVL amb atributs per als fills esquerre i dret, el valor del node i l'alçada del node.
getHeight Function: Retorna l'alçada d'un node.
rightRotate Function: Implementa la rotació a la dreta. Actualitza les alçades dels nodes afectats i retorna el nou node arrel.
leftRotate Function: Implementa la rotació a l'esquerra. Actualitza les alçades dels nodes afectats i retorna el nou node arrel.

Exercici 4: Inserció en un Arbre B

Enunciat

Implementa la inserció en un arbre B de grau mínim t.

Solució

class BTreeNode:
    def __init__(self, t, leaf=False):
        self.t = t
        self.leaf = leaf
        self.keys = []
        self.children = []

def insertNonFull(node, key):
    i = len(node.keys) - 1

    if node.leaf:
        node.keys.append(None)
        while i >= 0 and key < node.keys[i]:
            node.keys[i + 1] = node.keys[i]
            i -= 1
        node.keys[i + 1] = key
    else:
        while i >= 0 and key < node.keys[i]:
            i -= 1
        i += 1
        if len(node.children[i].keys) == 2 * node.t - 1:
            splitChild(node, i)
            if key > node.keys[i]:
                i += 1
        insertNonFull(node.children[i], key)

def splitChild(parent, i):
    t = parent.children[i].t
    y = parent.children[i]
    z = BTreeNode(t, y.leaf)
    parent.children.insert(i + 1, z)
    parent.keys.insert(i, y.keys[t - 1])

    z.keys = y.keys[t:(2 * t - 1)]
    y.keys = y.keys[0:(t - 1)]

    if not y.leaf:
        z.children = y.children[t:(2 * t)]
        y.children = y.children[0:t]

def insert(root, key):
    if len(root.keys) == 2 * root.t - 1:
        s = BTreeNode(root.t, False)
        s.children.append(root)
        splitChild(s, 0)
        insertNonFull(s, key)
        return s
    else:
        insertNonFull(root, key)
        return root

# Exemple d'ús
t = 3
root = BTreeNode(t, True)
keys = [10, 20, 5, 6, 12, 30, 7, 17]

for key in keys:
    root = insert(root, key)

print("Claus en l'arrel després de les insercions:", root.keys)

Explicació

BTreeNode Class: Defineix un node d'un arbre B amb atributs per al grau mínim t, si és una fulla, les claus i els fills.
insertNonFull Function: Insereix una clau en un node que no està ple.
splitChild Function: Divideix un node fill ple en dos nodes i ajusta el node pare.
insert Function: Gestiona la inserció d'una clau en l'arbre B, creant una nova arrel si l'arrel actual està plena.

Conclusió

Aquests exercicis cobreixen una varietat d'operacions amb arbres, incloent la creació, recorregut, verificació de propietats i manteniment de l'equilibri. Practicar aquests exercicis t'ajudarà a consolidar els teus coneixements sobre arbres i a preparar-te per a aplicacions més avançades.

Exercicis amb Arbres

Exercici 1: Creació d'un Arbre Binari

Enunciat

Solució

Explicació

Exercici 2: Verificar si un Arbre és un Arbre Binari de Cerca (BST)

Enunciat

Solució

Explicació

Exercici 3: Rotacions en un Arbre AVL

Enunciat

Solució

Explicació

Exercici 4: Inserció en un Arbre B

Enunciat

Solució

Explicació

Conclusió

Curs d'Estructures de Dades

Mòdul 1: Introducció a les Estructures de Dades

Mòdul 2: Llistes

Mòdul 3: Piles

Mòdul 4: Cues

Mòdul 5: Arbres

Mòdul 6: Grafs

Mòdul 7: Conclusions i Recursos Addicionals