Maison développement back-end Tutoriel Python Comment implémenter la traversée d'arbre binaire à l'aide de Python

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

Jun 09, 2023 pm 09:12 PM
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
Copier après la connexion

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
Copier après la connexion

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
Copier après la connexion

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!

Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn

Outils d'IA chauds

Undresser.AI Undress

Undresser.AI Undress

Application basée sur l'IA pour créer des photos de nu réalistes

AI Clothes Remover

AI Clothes Remover

Outil d'IA en ligne pour supprimer les vêtements des photos.

Undress AI Tool

Undress AI Tool

Images de déshabillage gratuites

Clothoff.io

Clothoff.io

Dissolvant de vêtements AI

AI Hentai Generator

AI Hentai Generator

Générez AI Hentai gratuitement.

Article chaud

R.E.P.O. Crystals d'énergie expliqués et ce qu'ils font (cristal jaune)
4 Il y a quelques semaines By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. Meilleurs paramètres graphiques
4 Il y a quelques semaines By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. Comment réparer l'audio si vous n'entendez personne
4 Il y a quelques semaines By 尊渡假赌尊渡假赌尊渡假赌
WWE 2K25: Comment déverrouiller tout dans Myrise
1 Il y a quelques mois By 尊渡假赌尊渡假赌尊渡假赌

Outils chauds

Bloc-notes++7.3.1

Bloc-notes++7.3.1

Éditeur de code facile à utiliser et gratuit

SublimeText3 version chinoise

SublimeText3 version chinoise

Version chinoise, très simple à utiliser

Envoyer Studio 13.0.1

Envoyer Studio 13.0.1

Puissant environnement de développement intégré PHP

Dreamweaver CS6

Dreamweaver CS6

Outils de développement Web visuel

SublimeText3 version Mac

SublimeText3 version Mac

Logiciel d'édition de code au niveau de Dieu (SublimeText3)

Le plan Python de 2 heures: une approche réaliste Le plan Python de 2 heures: une approche réaliste Apr 11, 2025 am 12:04 AM

Vous pouvez apprendre les concepts de programmation de base et les compétences de Python dans les 2 heures. 1. Apprenez les variables et les types de données, 2. Flux de contrôle maître (instructions et boucles conditionnelles), 3. Comprenez la définition et l'utilisation des fonctions, 4. Démarrez rapidement avec la programmation Python via des exemples simples et des extraits de code.

Python: Explorer ses applications principales Python: Explorer ses applications principales Apr 10, 2025 am 09:41 AM

Python est largement utilisé dans les domaines du développement Web, de la science des données, de l'apprentissage automatique, de l'automatisation et des scripts. 1) Dans le développement Web, les cadres Django et Flask simplifient le processus de développement. 2) Dans les domaines de la science des données et de l'apprentissage automatique, les bibliothèques Numpy, Pandas, Scikit-Learn et Tensorflow fournissent un fort soutien. 3) En termes d'automatisation et de script, Python convient aux tâches telles que les tests automatisés et la gestion du système.

Méthode de Navicat pour afficher le mot de passe de la base de données MongoDB Méthode de Navicat pour afficher le mot de passe de la base de données MongoDB Apr 08, 2025 pm 09:39 PM

Il est impossible de visualiser le mot de passe MongoDB directement via NAVICAT car il est stocké sous forme de valeurs de hachage. Comment récupérer les mots de passe perdus: 1. Réinitialiser les mots de passe; 2. Vérifiez les fichiers de configuration (peut contenir des valeurs de hachage); 3. Vérifiez les codes (May Code Hardcode).

Comment utiliser Aws Glue Crawler avec Amazon Athena Comment utiliser Aws Glue Crawler avec Amazon Athena Apr 09, 2025 pm 03:09 PM

En tant que professionnel des données, vous devez traiter de grandes quantités de données provenant de diverses sources. Cela peut poser des défis à la gestion et à l'analyse des données. Heureusement, deux services AWS peuvent aider: AWS Glue et Amazon Athena.

Comment démarrer le serveur avec redis Comment démarrer le serveur avec redis Apr 10, 2025 pm 08:12 PM

Les étapes pour démarrer un serveur Redis incluent: Installez Redis en fonction du système d'exploitation. Démarrez le service Redis via Redis-Server (Linux / MacOS) ou Redis-Server.exe (Windows). Utilisez la commande redis-Cli Ping (Linux / MacOS) ou redis-Cli.exe Ping (Windows) pour vérifier l'état du service. Utilisez un client redis, tel que redis-cli, python ou node.js pour accéder au serveur.

Comment lire la file d'attente redis Comment lire la file d'attente redis Apr 10, 2025 pm 10:12 PM

Pour lire une file d'attente à partir de Redis, vous devez obtenir le nom de la file d'attente, lire les éléments à l'aide de la commande LPOP et traiter la file d'attente vide. Les étapes spécifiques sont les suivantes: Obtenez le nom de la file d'attente: Nommez-le avec le préfixe de "Fitre:" tel que "Fitre: My-Quyue". Utilisez la commande LPOP: éjectez l'élément de la tête de la file d'attente et renvoyez sa valeur, telle que la file d'attente LPOP: My-Queue. Traitement des files d'attente vides: si la file d'attente est vide, LPOP renvoie NIL et vous pouvez vérifier si la file d'attente existe avant de lire l'élément.

Comment afficher la version serveur de redis Comment afficher la version serveur de redis Apr 10, 2025 pm 01:27 PM

Question: Comment afficher la version Redis Server? Utilisez l'outil de ligne de commande redis-Cli --version pour afficher la version du serveur connecté. Utilisez la commande Info Server pour afficher la version interne du serveur et devez analyser et retourner des informations. Dans un environnement de cluster, vérifiez la cohérence de la version de chaque nœud et peut être vérifiée automatiquement à l'aide de scripts. Utilisez des scripts pour automatiser les versions de visualisation, telles que la connexion avec les scripts Python et les informations d'impression.

Dans quelle mesure le mot de passe de Navicat est-il sécurisé? Dans quelle mesure le mot de passe de Navicat est-il sécurisé? Apr 08, 2025 pm 09:24 PM

La sécurité du mot de passe de Navicat repose sur la combinaison de cryptage symétrique, de force de mot de passe et de mesures de sécurité. Des mesures spécifiques incluent: l'utilisation de connexions SSL (à condition que le serveur de base de données prenne en charge et configure correctement le certificat), à la mise à jour régulièrement de NAVICAT, en utilisant des méthodes plus sécurisées (telles que les tunnels SSH), en restreignant les droits d'accès et, surtout, à ne jamais enregistrer de mots de passe.

See all articles