Comment implémenter un arbre binaire en Python
Python implémente un arbre binaire
Python peut implémenter un arbre binaire en utilisant une programmation orientée objet en définissant une classe de nœuds d'arbre binaire. Chaque nœud contient un élément de données, des pointeurs de nœuds enfants gauche et droit et certaines méthodes de fonctionnement, telles que l'insertion de nœuds, la recherche de nœuds, la suppression de nœuds, etc.
Ce qui suit est un exemple simple d'implémentation d'arbre binaire :
class Node: def __init__(self, data): self.data = data self.left = None self.right = None def insert(self, data): 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 def find(self, data): if data < self.data: if self.left is None: return str(data) + " Not Found" return self.left.find(data) elif data > self.data: if self.right is None: return str(data) + " Not Found" return self.right.find(data) else: return str(self.data) + " is found" def inorder_traversal(self, root): res = [] if root: res = self.inorder_traversal(root.left) res.append(root.data) res = res + self.inorder_traversal(root.right) return res
Dans le code ci-dessus, la classe Node définit un nœud, y compris les données de l'élément de données, et les pointeurs de nœud enfant gauche et droit gauche et droit. La méthode insert est utilisée pour insérer des nœuds dans un arbre binaire, la méthode find est utilisée pour déterminer si un nœud spécifique existe dans l'arbre binaire et la méthode inorder_traversal est utilisée pour effectuer un parcours dans l'ordre de l'arbre binaire.
Voici comment utiliser cette classe Node pour créer un arbre binaire :
root = Node(50) root.insert(30) root.insert(20) root.insert(40) root.insert(70) root.insert(60) root.insert(80) # 查找节点 print(root.find(70)) # Output: 70 is found print(root.find(90)) # Output: 90 Not Found # 中序遍历 print(root.inorder_traversal(root)) # Output: [20, 30, 40, 50, 60, 70, 80]
Dans le code ci-dessus, un nœud racine racine est d'abord créé, puis la méthode insert est utilisée pour insérer le nœud dans l'arbre, et enfin la méthode find est utilisé pour trouver le nœud et la méthode inorder_traversal est utilisée Effectuer un parcours dans l'ordre d'un arbre binaire.
En plus des méthodes d'insertion, de recherche et de parcours, les arbres binaires ont également d'autres méthodes de fonctionnement, telles que la suppression de nœuds, la détermination s'il s'agit d'un arbre de recherche binaire, le calcul de la profondeur de l'arbre, etc. Ce qui suit est un exemple de code d'arbre binaire légèrement plus complet :
class Node: def __init__(self, data): self.data = data self.left = None self.right = None def insert(self, data): 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 def find(self, data): if data < self.data: if self.left is None: return None return self.left.find(data) elif data > self.data: if self.right is None: return None return self.right.find(data) else: return self def delete(self, data): if self is None: return self if data < self.data: self.left = self.left.delete(data) elif data > self.data: self.right = self.right.delete(data) else: if self.left is None: temp = self.right self = None return temp elif self.right is None: temp = self.left self = None return temp temp = self.right.minimum() self.data = temp.data self.right = self.right.delete(temp.data) return self def minimum(self): if self.left is None: return self return self.left.minimum() def is_bst(self): if self.left: if self.left.data > self.data or not self.left.is_bst(): return False if self.right: if self.right.data < self.data or not self.right.is_bst(): return False return True def height(self, node): if node is None: return 0 left_height = self.height(node.left) right_height = self.height(node.right) return max(left_height, right_height) + 1 def inorder_traversal(self, root): res = [] if root: res = self.inorder_traversal(root.left) res.append(root.data) res = res + self.inorder_traversal(root.right) return res
Dans cet exemple, nous avons ajouté la méthode delete pour supprimer le nœud spécifié ; la méthode minimale pour trouver le plus petit nœud dans l'arborescence pour déterminer si la méthode is_bst ; L'arbre actuel est une méthode binaire de recherche de hauteur d'arbre pour calculer la profondeur de l'arbre.
Nous pouvons utiliser le code suivant pour tester la nouvelle méthode :
# 创建二叉树 root = Node(50) root.insert(30) root.insert(20) root.insert(40) root.insert(70) root.insert(60) root.insert(80) # 删除节点 print("Deleting node 20:") root.delete(20) print(root.inorder_traversal(root)) # 判断是否为二叉搜索树 print("Is it a BST?:", root.is_bst()) # 计算树的深度 print("Tree height:", root.height(root))
De cette façon, nous avons réalisé une implémentation d'arbre binaire relativement complète et avons également démontré comment utiliser des idées de programmation orientée objet en Python pour implémenter une structure de données.
Enfin, le code complet d'implémentation de la classe d'arbre binaire est joint :
class Node: def __init__(self, data): self.data = data self.left = None self.right = None def insert(self, data): 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 def find(self, data): if data < self.data: if self.left is None: return None return self.left.find(data) elif data > self.data: if self.right is None: return None return self.right.find(data) else: return self def delete(self, data): if self is None: return self if data < self.data: self.left = self.left.delete(data) elif data > self.data: self.right = self.right.delete(data) else: if self.left is None: temp = self.right self = None return temp elif self.right is None: temp = self.left self = None return temp temp = self.right.minimum() self.data = temp.data self.right = self.right.delete(temp.data) return self def minimum(self): if self.left is None: return self return self.left.minimum() def is_bst(self): if self.left: if self.left.data > self.data or not self.left.is_bst(): return False if self.right: if self.right.data < self.data or not self.right.is_bst(): return False return True def height(self, node): if node is None: return 0 left_height = self.height(node.left) right_height = self.height(node.right) return max(left_height, right_height) + 1 def inorder_traversal(self, root): res = [] if root: res = self.inorder_traversal(root.left) res.append(root.data) res = res + self.inorder_traversal(root.right) return res if __name__ == '__main__': # 创建二叉树 root = Node(50) root.insert(30) root.insert(20) root.insert(40) root.insert(70) root.insert(60) root.insert(80) # 删除节点 print("Deleting node 20:") root.delete(20) print(root.inorder_traversal(root)) # 判断是否为二叉搜索树 print("Is it a BST?:", root.is_bst()) # 计算树的深度 print("Tree height:", root.height(root))
Après avoir exécuté le code, vous pouvez obtenir le résultat suivant :
Suppression du nœud 20 :
[30, 40, 50, 60, 70, 80]
Est-ce un BST ? : Vrai
Hauteur de l'arbre : 3
Cet exemple inclut l'insertion, la recherche, la suppression, le parcours, la détermination s'il s'agit d'un arbre de recherche binaire et le calcul de la profondeur de l'arbre, etc.
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!

Outils d'IA chauds

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

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

Undress AI Tool
Images de déshabillage gratuites

Clothoff.io
Dissolvant de vêtements AI

AI Hentai Generator
Générez AI Hentai gratuitement.

Article chaud

Outils chauds

Bloc-notes++7.3.1
Éditeur de code facile à utiliser et gratuit

SublimeText3 version chinoise
Version chinoise, très simple à utiliser

Envoyer Studio 13.0.1
Puissant environnement de développement intégré PHP

Dreamweaver CS6
Outils de développement Web visuel

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

PHP et Python ont leurs propres avantages et inconvénients, et le choix dépend des besoins du projet et des préférences personnelles. 1.Php convient au développement rapide et à la maintenance des applications Web à grande échelle. 2. Python domine le domaine de la science des données et de l'apprentissage automatique.

Python et JavaScript ont leurs propres avantages et inconvénients en termes de communauté, de bibliothèques et de ressources. 1) La communauté Python est amicale et adaptée aux débutants, mais les ressources de développement frontal ne sont pas aussi riches que JavaScript. 2) Python est puissant dans les bibliothèques de science des données et d'apprentissage automatique, tandis que JavaScript est meilleur dans les bibliothèques et les cadres de développement frontaux. 3) Les deux ont des ressources d'apprentissage riches, mais Python convient pour commencer par des documents officiels, tandis que JavaScript est meilleur avec MDNWEBDOCS. Le choix doit être basé sur les besoins du projet et les intérêts personnels.

Dans VS Code, vous pouvez exécuter le programme dans le terminal via les étapes suivantes: Préparez le code et ouvrez le terminal intégré pour vous assurer que le répertoire de code est cohérent avec le répertoire de travail du terminal. Sélectionnez la commande Run en fonction du langage de programmation (tel que Python de Python your_file_name.py) pour vérifier s'il s'exécute avec succès et résoudre les erreurs. Utilisez le débogueur pour améliorer l'efficacité du débogage.

VS Code peut être utilisé pour écrire Python et fournit de nombreuses fonctionnalités qui en font un outil idéal pour développer des applications Python. Il permet aux utilisateurs de: installer des extensions Python pour obtenir des fonctions telles que la réalisation du code, la mise en évidence de la syntaxe et le débogage. Utilisez le débogueur pour suivre le code étape par étape, trouver et corriger les erreurs. Intégrez Git pour le contrôle de version. Utilisez des outils de mise en forme de code pour maintenir la cohérence du code. Utilisez l'outil de liaison pour repérer les problèmes potentiels à l'avance.

Docker utilise les fonctionnalités du noyau Linux pour fournir un environnement de fonctionnement d'application efficace et isolé. Son principe de travail est le suivant: 1. Le miroir est utilisé comme modèle en lecture seule, qui contient tout ce dont vous avez besoin pour exécuter l'application; 2. Le Système de fichiers Union (UnionFS) empile plusieurs systèmes de fichiers, ne stockant que les différences, l'économie d'espace et l'accélération; 3. Le démon gère les miroirs et les conteneurs, et le client les utilise pour l'interaction; 4. Les espaces de noms et les CGROUP implémentent l'isolement des conteneurs et les limitations de ressources; 5. Modes de réseau multiples prennent en charge l'interconnexion du conteneur. Ce n'est qu'en comprenant ces concepts principaux que vous pouvez mieux utiliser Docker.

Les extensions de code vs posent des risques malveillants, tels que la cachette de code malveillant, l'exploitation des vulnérabilités et la masturbation comme des extensions légitimes. Les méthodes pour identifier les extensions malveillantes comprennent: la vérification des éditeurs, la lecture des commentaires, la vérification du code et l'installation avec prudence. Les mesures de sécurité comprennent également: la sensibilisation à la sécurité, les bonnes habitudes, les mises à jour régulières et les logiciels antivirus.

VS Code peut fonctionner sur Windows 8, mais l'expérience peut ne pas être excellente. Assurez-vous d'abord que le système a été mis à jour sur le dernier correctif, puis téléchargez le package d'installation VS Code qui correspond à l'architecture du système et l'installez comme invité. Après l'installation, sachez que certaines extensions peuvent être incompatibles avec Windows 8 et doivent rechercher des extensions alternatives ou utiliser de nouveaux systèmes Windows dans une machine virtuelle. Installez les extensions nécessaires pour vérifier si elles fonctionnent correctement. Bien que le code VS soit possible sur Windows 8, il est recommandé de passer à un système Windows plus récent pour une meilleure expérience de développement et une meilleure sécurité.

Python excelle dans l'automatisation, les scripts et la gestion des tâches. 1) Automatisation: La sauvegarde du fichier est réalisée via des bibliothèques standard telles que le système d'exploitation et la fermeture. 2) Écriture de script: utilisez la bibliothèque PSUTIL pour surveiller les ressources système. 3) Gestion des tâches: utilisez la bibliothèque de planification pour planifier les tâches. La facilité d'utilisation de Python et la prise en charge de la bibliothèque riche en font l'outil préféré dans ces domaines.
