Python - Arbre binaire

L'arbre représente les nœuds connectés par des arêtes. C'est une structure de données non linéaire. Il a les propriétés suivantes.

• Un nœud est marqué comme nœud racine.
• Chaque nœud autre que la racine est associé à un nœud parent.
• Chaque nœud peut avoir un numéro d'arbitrage de nœud chid.

Nous créons une structure de données arborescente en python en utilisant le concept os node discuté précédemment. Nous désignons un nœud comme nœud racine, puis ajoutons d'autres nœuds en tant que nœuds enfants. Ci-dessous se trouve le programme pour créer le nœud racine.

Créer une racine

Nous créons simplement une classe Node et ajoutons assigner une valeur au nœud. Cela devient un arbre avec seulement un nœud racine.

class Node:

    def __init__(self, data):

        self.left = None
        self.right = None
        self.data = data


    def PrintTree(self):
        print(self.data)

root = Node(10)

root.PrintTree()

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant -

10

Insertion dans un arbre

Pour insérer dans un arbre, nous utilisons la même classe de nœuds créée ci-dessus et y ajoutons une méthode d'insertion La méthode d'insertion compare la valeur du nœud au nœud parent et décide de l'ajouter en tant que nœud gauche ou nœud droit. Enfin, la méthode PrintTree est utilisée pour imprimer l'arborescence.

class Node:

    def __init__(self, data):

        self.left = None
        self.right = None
        self.data = data

    def insert(self, data):
# Compare the new value with the parent node
        if self.data:
            if data < self.data:
                if self.left is None:
                    self.left = Node(data)
                else:
                    self.left.insert(data)
            elif data > self.data:
                if self.right is None:
                    self.right = Node(data)
                else:
                    self.right.insert(data)
        else:
            self.data = data

# Print the tree
    def PrintTree(self):
        if self.left:
            self.left.PrintTree()
        print( self.data),
        if self.right:
            self.right.PrintTree()

# Use the insert method to add nodes
root = Node(12)
root.insert(6)
root.insert(14)
root.insert(3)

root.PrintTree()

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant -

3 6 12 14

Traverser un arbre

L'arbre peut être parcouru en décidant d'une séquence pour visiter chaque nœud. Comme nous pouvons clairement le voir, nous pouvons commencer à un nœud, puis visiter le sous-arbre gauche en premier et le sous-arbre droit ensuite. Ou nous pouvons également visiter le sous-arbre droit en premier et le sous-arbre gauche ensuite. En conséquence, il existe différents noms pour ces méthodes de traversée d'arbre. Nous les étudions en détail dans le chapitre implémentation des algorithmes de parcours d'arbre ici. Algorithmes de traversée des arbres