Parcours BST

Fondamentalement, il existe trois méthodes de parcours d'arbre : le parcours pré-ordre, en ordre, et post-ordre. La différence entre les trois méthodes réside dans l'ordre des éléments. Voyons comment nous réalisons cela dans le code.
Dans ce chapitre, nous travaillerons avec l'arbre suivant :

Le parcours pré-ordre

Le parcours pré-ordre donne l'ordre naturel. Tout d'abord, nous visitons le nœud racine, puis récursivement les sous-arbres gauche et droit de chaque sous-arbre.


              12345678910111213141516171819202122232425262728293031323334353637
            
class Tree:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

root = Tree(26, 
            left=Tree(12, 
                      left=Tree(7), 
                      right=Tree(24)), 
            right=Tree(52, 
                       left=Tree(39), 
                       right=Tree(85)))

# The pre-order traversal yields the natural ordering of the elements in the tree
def pre_order_traversal(subtree_root):
    # Initialize an empty string to store the node values
    nodes = []

    # Define the recursive function to traverse the tree
    def traverse(node):
        # If the node is not None, append its value to the list
        if node is not None:
            nodes.append(str(node.value))
            # Recursively traverse the left and right subtrees
            traverse(node.left)
            traverse(node.right)

    # Start the traversal from the root
    traverse(subtree_root)

    # Join the node values with the arrow separator
    result = ' -> '.join(nodes)
    return result

# Perform pre-order traversal and print the result
print(pre_order_traversal(root))

Nous plaçons l'instruction append avant les appels récursifs pour y parvenir.

Le parcours en ordre

Le parcours en ordre est probablement le plus courant, car il donne l'ordre trié des éléments dans l'arbre.


              12345678910111213141516171819202122232425262728293031323334353637383940
            
class Tree:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

root = Tree(26, 
            left=Tree(12, 
                      left=Tree(7), 
                      right=Tree(24)), 
            right=Tree(52, 
                       left=Tree(39), 
                       right=Tree(85
                       )))

# The in-order traversal yields the sorted order of the elements in the tree
def in_order_traversal(subtree_root):
    # Initialize an empty string to store the node values
    nodes = []

    # Define the recursive function to traverse the tree
    def traverse(node):
        # If the node is not None, recursively traverse the left subtree
        if node.left:
            traverse(node.left)
        # Append the node value to the list
        nodes.append(str(node.value))
        # If the node is not None, recursively traverse the right subtree
        if node.right:
            traverse(node.right)

    # Start the traversal from the root
    traverse(subtree_root)

    # Join the node values with the arrow separator
    result = ' -> '.join(nodes)
    return result

# Perform in-order traversal and print the result
print(in_order_traversal(root))

Lors de l'implémentation d'un parcours en ordre, nous plaçons l'instruction append au milieu entre deux appels récursifs sur les sous-arbres gauche et droit.

Le parcours en post-ordre

La troisième façon de parcourir un arbre binaire de recherche est d'utiliser le parcours en post-ordre. L'algorithme de parcours en post-ordre visite d'abord le sous-arbre gauche et le sous-arbre droit, puis visite le nœud racine pour chaque sous-arbre dans l'arbre initial.


              1234567891011121314151617181920212223242526272829303132333435363738394041
            
class Tree:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

root = Tree(26, 
            left=Tree(12, 
                      left=Tree(7), 
                      right=Tree(24)), 
            right=Tree(52, 
                       left=Tree(39), 
                       right=Tree(85
                       )))

# The post-order traversal prints the elements in order from bottom to the top
# from left to the right
def post_order_traversal(subtree_root):
    # Initialize an empty string to store the node values
    nodes = []

    # Define the recursive function to traverse the tree
    def traverse(node):
        # If the node is not None, recursively traverse the left subtree
        if node.left:
            traverse(node.left)
        # If the node is not None, recursively traverse the right subtree
        if node.right:
            traverse(node.right)
        # Append the node value to the list
        nodes.append(str(node.value))

    # Start the traversal from the root
    traverse(subtree_root)

    # Join the node values with the arrow separator
    result = ' -> '.join(nodes)
    return result

# Perform post-order traversal and print the result
print(post_order_traversal(root))

Nous ajoutons les nœuds après les appels récursifs pour implémenter le parcours en post-ordre.

Tout était clair ?

Merci pour vos commentaires !

Section 4. Chapitre 5