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

Introducció als Arbres

Següent ►
►

Què és un Arbre?

Un arbre és una estructura de dades jeràrquica que consisteix en nodes connectats per arestes. Cada arbre té un node especial anomenat arrel, des del qual es poden accedir a tots els altres nodes. Els nodes poden tenir fills, que són altres nodes connectats a ells. Els nodes sense fills es diuen fulles.

Característiques d'un Arbre:

  • Arrel (Root): El node superior de l'arbre.
  • Node: Cada element de l'arbre.
  • Fulla (Leaf): Un node que no té fills.
  • Pare (Parent): Un node que té un o més fills.
  • Fill (Child): Un node que té un pare.
  • Subarbre: Un arbre format per un node i tots els seus descendents.
  • Profunditat (Depth): La longitud del camí des de l'arrel fins a un node.
  • Alçada (Height): La longitud del camí més llarg des d'un node fins a una fulla.

Terminologia Bàsica

Termini Descripció
Arrel El node inicial de l'arbre.
Node Un element de l'arbre.
Fulla Un node sense fills.
Pare Un node que té fills.
Fill Un node que té un pare.
Subarbre Un arbre format per un node i tots els seus descendents.
Profunditat La longitud del camí des de l'arrel fins a un node.
Alçada La longitud del camí més llarg des d'un node fins a una fulla.

Tipus d'Arbres

Hi ha diversos tipus d'arbres, cadascun amb les seves pròpies característiques i aplicacions. Alguns dels més comuns són:

  1. Arbre Binari: Cada node té com a màxim dos fills.
  2. Arbre Binari de Cerca (BST): Un arbre binari on cada node segueix la propietat de l'ordre (els fills esquerres són menors i els fills drets són majors que el node pare).
  3. Arbre AVL: Un arbre binari de cerca autobalancejat.
  4. Arbre B: Un arbre balancejat utilitzat en bases de dades i sistemes de fitxers.

Representació d'un Arbre

Els arbres es poden representar de diverses maneres en la programació. Una de les formes més comunes és utilitzar nodes i referències. A continuació es mostra un exemple de com es podria representar un arbre binari en Python:

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

# Crear l'arrel
root = Node(1)

# Afegir nodes
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

En aquest exemple, hem creat un arbre binari amb una arrel i alguns nodes fills.

Operacions Bàsiques en Arbres

Les operacions més comunes que es poden realitzar en arbres inclouen:

  1. Inserció: Afegir un nou node a l'arbre.
  2. Eliminació: Eliminar un node existent de l'arbre.
  3. Cerca: Trobar un node amb un valor específic.
  4. Recorregut: Visitar tots els nodes de l'arbre en un ordre específic (preordre, inordre, postordre).

Exemple d'Inserció en un Arbre Binari de Cerca (BST)

class BSTNode:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.value = key

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

# Crear l'arrel
root = BSTNode(50)

# Inserir nodes
root = insert(root, 30)
root = insert(root, 20)
root = insert(root, 40)
root = insert(root, 70)
root = insert(root, 60)
root = insert(root, 80)

En aquest exemple, hem creat un arbre binari de cerca i hem inserit diversos nodes seguint la propietat de l'ordre.

Exercici Pràctic

Exercici 1: Crear un Arbre Binari

Objectiu: Crear un arbre binari i implementar una funció per realitzar un recorregut en preordre.

Instruccions:

  1. Defineix una classe Node per representar els nodes de l'arbre.
  2. Implementa una funció preorder_traversal que realitzi un recorregut en preordre de l'arbre.
class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.value = key

def preorder_traversal(root):
    if root:
        print(root.value, end=" ")
        preorder_traversal(root.left)
        preorder_traversal(root.right)

# Crear l'arrel
root = Node(1)

# Afegir nodes
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

# Realitzar el recorregut en preordre
preorder_traversal(root)

Solució:

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

def preorder_traversal(root):
    if root:
        print(root.value, end=" ")
        preorder_traversal(root.left)
        preorder_traversal(root.right)

# Crear l'arrel
root = Node(1)

# Afegir nodes
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

# Realitzar el recorregut en preordre
preorder_traversal(root)

Conclusió

En aquesta secció, hem introduït els conceptes bàsics dels arbres, incloent-hi la seva terminologia, tipus i operacions bàsiques. També hem vist com es poden representar i manipular arbres en Python. En els següents mòduls, aprofundirem en tipus específics d'arbres i les seves aplicacions.

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