Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.
Apprendre Parcours BST | Graphes
Aperçu des Algorithmes et des Structures de Données

book
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.

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

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.

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

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.

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

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

question mark

Où placer l'instruction append par rapport aux appels récursifs pour implémenter le parcours en ordre?

Select the correct answer

Tout était clair ?

Comment pouvons-nous l'améliorer ?

Merci pour vos commentaires !

Section 4. Chapitre 5

Demandez à l'IA

expand
ChatGPT

Posez n'importe quelle question ou essayez l'une des questions suggérées pour commencer notre discussion

We use cookies to make your experience better!
some-alt