Comment implémenter la traversée d'arbre binaire à l'aide de Python

En tant que structure de données couramment utilisée, les arbres binaires sont souvent utilisés pour stocker des données, rechercher et trier. La traversée d’un arbre binaire est l’une des opérations les plus courantes. En tant que langage de programmation simple et facile à utiliser, Python dispose de nombreuses méthodes pour implémenter la traversée d'arbres binaires. Cet article expliquera comment utiliser Python pour implémenter le parcours en pré-ordre, dans l'ordre et après-ordre d'un arbre binaire.

Bases des arbres binaires

Avant d'apprendre à parcourir un arbre binaire, nous devons comprendre les concepts de base des arbres binaires. Un arbre binaire est constitué de nœuds, chaque nœud a une valeur et deux enfants (enfant de gauche et enfant de droite). Les enfants d'un nœud peuvent être vides.

Traversée d'arbre binaire

La traversée d'arbre binaire fait référence à la visite de tous les nœuds de l'arbre binaire dans un certain ordre. Il existe trois méthodes de parcours couramment utilisées : le parcours pré-ordre, le parcours dans l'ordre et le parcours post-ordre.

Parcours de pré-commande

L'ordre de parcours de pré-commande est le nœud racine, le sous-arbre gauche et le sous-arbre droit. Dans une implémentation spécifique, vous pouvez d'abord afficher la valeur du nœud racine, puis parcourir de manière récursive le sous-arbre gauche et le sous-arbre droit.

Ce qui suit est l'implémentation du code Python :

class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def preorderTraversal(root: TreeNode): if root is None: return [] res = [root.val] res += preorderTraversal(root.left) res += preorderTraversal(root.right) return res

Parcours dans l'ordre

L'ordre du parcours dans l'ordre est le sous-arbre gauche, le nœud racine et le sous-arbre droit. Dans une implémentation spécifique, il est nécessaire de parcourir de manière récursive le sous-arbre de gauche, d'afficher la valeur du nœud racine, puis de parcourir de manière récursive le sous-arbre de droite.

Ce qui suit est l'implémentation du code Python :

def inorderTraversal(root: TreeNode): if root is None: return [] res = [] res += inorderTraversal(root.left) res.append(root.val) res += inorderTraversal(root.right) return res

Traversée post-commande

L'ordre de traversée post-commande est le sous-arbre gauche, le sous-arbre droit et le nœud racine. Dans une implémentation spécifique, il est nécessaire de parcourir récursivement le sous-arbre gauche et le sous-arbre droit, et enfin de générer la valeur du nœud racine.

Ce qui suit est l'implémentation du code Python :

def postorderTraversal(root: TreeNode): if root is None: return [] res = [] res += postorderTraversal(root.left) res += postorderTraversal(root.right) res.append(root.val) return res

Résumé

En Python, lors de l'utilisation du parcours d'arbre binaire, le parcours en pré-ordre, dans l'ordre et après l'ordre peut être réalisé par récursivité. En plus de la récursivité, il peut également être implémenté à l'aide de méthodes telles que la recherche par pile et en largeur. Maîtriser la méthode de parcours d'arbre binaire sera très utile pour le travail de programmation quotidien.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!