Arbre binaire#
Un arbre binaire est une structure de données hiérarchique composée de nœuds, où chaque nœud a au plus deux enfants, généralement appelés fils gauche et fils droit. Le nœud au sommet de l’arbre est appelé la racine, et chaque nœud peut avoir zéro, un ou deux enfants.
Les arbres binaires sont utilisés pour stocker et organiser des données de manière efficace. Voici quelques utilisations courantes des arbres binaires :
Représentation hiérarchique des données: Les arbres binaires sont souvent utilisés pour représenter des structures de données hiérarchiques telles que des arbres de fichiers dans un système de fichiers, des arbres généalogiques, des structures organisationnelles, etc.
Recherche et tri efficaces: Les arbres binaires de recherche (ABR) sont des structures de données qui permettent de stocker des données de manière ordonnée et de réaliser des opérations de recherche et de tri efficaces. Les ABR garantissent que les données sont organisées de manière à ce que les opérations de recherche puissent être effectuées en un temps logarithmique par rapport à la taille de l’arbre.
Implémentation de structures de données avancées: Les arbres binaires sont utilisés comme composants de base dans de nombreuses structures de données avancées telles que les tas binaires, les arbres AVL, les arbres rouge-noir, etc. Ces structures de données offrent des performances optimales pour des opérations spécifiques telles que l’insertion, la suppression et la recherche.
Analyse et traitement de données: Les arbres binaires sont utilisés dans l’analyse de données et le traitement de données pour représenter des hiérarchies de données complexes et pour effectuer des opérations telles que l’agrégation, la recherche de chemins, etc.
En résumé, les arbres binaires sont des structures de données polyvalentes utilisées dans de nombreux domaines de l’informatique pour stocker, organiser et manipuler des données de manière efficace et structurée. Ils offrent une grande flexibilité et sont largement utilisés dans le développement de logiciels pour diverses applications.
Fonction#
1class TreeNode:
2"""Class representing a node in a binary tree."""
3def __init__(self, data):
4 """Initializes a node with data and left and right pointers.
5
6 Args:
7 data: The data to be stored in the node.
8 """
9 self.data = data
10 self.left = None
11 self.right = None
12
13
14def depth_of_tree(tree):
15 """Recursive function to find the depth of a binary tree.
16
17 Args:
18 tree (TreeNode): The root node of the tree.
19
20 Returns:
21 int: The depth of the tree.
22 """
23 if tree is None:
24 return 0
25 else:
26 depth_left_tree = depth_of_tree(tree.left)
27 depth_right_tree = depth_of_tree(tree.right)
28 if depth_left_tree > depth_right_tree:
29 return 1 + depth_left_tree
30 else:
31 return 1 + depth_right_tree
32
33
34def is_full_binary_tree(tree):
35 """Function to check if a binary tree is full.
36
37 Args:
38 tree (TreeNode): The root node of the tree.
39
40 Returns:
41 bool: True if the tree is full, False otherwise.
42 """
43 if tree is None:
44 return True
45 if (tree.left is None) and (tree.right is None):
46 return True
47 if (tree.left is not None) and (tree.right is not None):
48 return is_full_binary_tree(tree.left) and is_full_binary_tree(tree.right)
49 else:
50 return False
51
52
53def main():
54 """Main function for testing.
55
56 Creates a binary tree, then checks if it's full and calculates its depth.
57 """
58 tree = TreeNode(1)
59 tree.left = TreeNode(2)
60 tree.right = TreeNode(3)
61 tree.left.left = TreeNode(4)
62 tree.left.right = TreeNode(5)
63 tree.left.right.left = TreeNode(6)
64 tree.right.left = TreeNode(7)
65 tree.right.left.left = TreeNode(8)
66 tree.right.left.left.right = TreeNode(9)
67
68 print(is_full_binary_tree(tree))
69 print(depth_of_tree(tree))
if __name__ == '__main__':
main()
False
5