Arbre binaire est un structure de données non linéaire où chaque nœud a au plus deux enfants. Dans cet article, nous couvrirons toutes les bases de l'arbre binaire, les opérations sur l'arbre binaire, sa mise en œuvre, ses avantages, ses inconvénients qui vous aideront à résoudre tous les problèmes basés sur l'arbre binaire.
Table des matières
- Qu’est-ce que l’arbre binaire ?
- Représentation de l'arbre binaire
- Types d'arbre binaire
- Opérations sur l'arbre binaire
- Opérations auxiliaires sur l'arbre binaire
- Implémentation de l'arbre binaire
- Analyse de complexité des opérations d'arbre binaire
- Avantages de l'arbre binaire
- Inconvénients de l'arbre binaire
- Applications de l'arbre binaire
- Foire aux questions sur l'arbre binaire
Qu’est-ce que l’arbre binaire ?
L'arbre binaire est un structure de données arborescente (non linéaire) dans lequel chaque nœud peut avoir au maximum deux enfants qui sont appelés les enfant abandonné et le bon enfant .
Le nœud le plus élevé d'un arbre binaire est appelé le racine , et les nœuds les plus bas sont appelés feuilles . Un arbre binaire peut être visualisé comme une structure hiérarchique avec la racine en haut et les feuilles en bas.
mettre le texte en gras en CSS
Représentation de l'arbre binaire
Chaque nœud d'un arbre binaire comporte trois parties :
- Données
- Pointeur vers l'enfant de gauche
- Pointeur vers le bon enfant
Ci-dessous la représentation d’un nœud d’arbre binaire dans différentes langues :
C++ // Use any below method to implement Nodes of tree // Method 1: Using 'struct' to make // user-define data type struct node { int data; struct node* left; struct node* right; }; // Method 2: Using 'class' to make // user-define data type class Node { public: int data; Node* left; Node* right; };> C // Structure of each node of the tree struct node { int data; struct node* left; struct node* right; };> Java // Class containing left and right child // of current node and key value class Node { int key; Node left, right; public Node(int item) { key = item; left = right = null; } }> Python # A Python class that represents # an individual node in a Binary Tree class Node: def __init__(self, key): self.left = None self.right = None self.val = key>
C# // Class containing left and right child // of current node and key value class Node { int key; Node left, right; public Node(int item) { key = item; left = right = null; } }> Javascript >
Types d'arbre binaire
L'arbre binaire peut être classé en plusieurs types en fonction de plusieurs facteurs :
- Sur la base du nombre d'enfants
- Arbre binaire complet
- Arbre binaire dégénéré
- Arbres binaires asymétriques
- Sur la base de l'achèvement des niveaux
- Arbre binaire complet
- Arbre binaire parfait
- Arbre binaire équilibré
- Sur la base des valeurs des nœuds :
- Arbre de recherche binaire
- Arbre AVL
- Arbre Noir Rouge
- Arbre B
- Arbre B+
- Arbre de segments
Opérations sur l'arbre binaire
1. Insertion dans l'arbre binaire
Nous pouvons insérer un nœud n'importe où dans un arbre binaire en insérant le nœud comme enfant gauche ou droit de n'importe quel nœud ou en faisant du nœud la racine de l'arbre.
Algorithme pour insérer un nœud dans un arbre binaire :
- Vérifiez s'il y a un nœud dans l'arborescence binaire pour lequel il manque un enfant gauche. Si un tel nœud existe, insérez le nouveau nœud comme son enfant gauche.
- Vérifiez s'il y a un nœud dans l'arborescence binaire pour lequel il manque un enfant droit. Si un tel nœud existe, insérez le nouveau nœud comme son enfant droit.
- Si nous ne trouvons aucun nœud avec un enfant gauche ou droit manquant, recherchez le nœud pour lequel les deux enfants sont manquants et insérez le nœud comme enfant gauche ou droit.
2. Traversée de l'arbre binaire
La traversée de l'arbre binaire implique de visiter tous les nœuds de l'arbre binaire. Les algorithmes Tree Traversal peuvent être classés en deux catégories :
- Algorithmes de recherche en profondeur (DFS)
- Algorithmes de recherche en largeur d'abord (BFS)
Algorithmes de recherche en profondeur (DFS) :
- Traversée de précommande (actuel-gauche-droite) : Visitez le nœud actuel avant de visiter les nœuds à l’intérieur des sous-arbres gauche ou droit. Ici, le parcours est racine – enfant gauche – enfant droit. Cela signifie que le nœud racine est traversé en premier, puis son enfant gauche et enfin l'enfant droit.
- Traversée dans l'ordre (gauche-actuel-droite) : Visitez le nœud actuel après avoir visité tous les nœuds du sous-arbre de gauche, mais avant de visiter un nœud du sous-arbre de droite. Ici, le parcours est enfant gauche – racine – enfant droit. Cela signifie que l'enfant de gauche est traversé en premier, puis son nœud racine et enfin l'enfant de droite.
- Traversée post-commande (gauche-droite-actuelle) : Visitez le nœud actuel après avoir visité tous les nœuds des sous-arbres gauche et droit. Ici, le parcours est enfant gauche – enfant droit – racine. Cela signifie que l'enfant de gauche a traversé d'abord puis l'enfant de droite et enfin son nœud racine.
Algorithmes de recherche en largeur d'abord (BFS) :
- Traversée de l'ordre des niveaux : Visitez les nœuds niveau par niveau et de gauche à droite au même niveau. Ici, la traversée se fait par niveau. Cela signifie que l'enfant le plus à gauche a traversé en premier et ensuite les autres enfants du même niveau de gauche à droite ont traversé.
3. Suppression dans l'arborescence binaire
Nous pouvons supprimer n'importe quel nœud de l'arbre binaire et réorganiser les nœuds après la suppression pour former à nouveau un arbre binaire valide.
Algorithme pour supprimer un nœud dans un arbre binaire :
- En commençant par la racine, recherchez le nœud le plus profond et le plus à droite de l'arborescence binaire et le nœud que nous souhaitons supprimer.
- Remplacez les données du nœud le plus à droite par le nœud à supprimer.
- Supprimez ensuite le nœud le plus profond à droite.
4. Recherche dans l'arborescence binaire
Nous pouvons rechercher un élément dans le nœud en utilisant n'importe laquelle des techniques de parcours.
contient du python
Algorithme pour rechercher un nœud dans un arbre binaire :
- Commencez par le nœud racine.
- Vérifiez si la valeur du nœud actuel est égale à la valeur cible.
- Si la valeur du nœud actuel est égale à la valeur cible, alors ce nœud est le nœud requis.
- Sinon, si la valeur du nœud n'est pas égale à la valeur cible, lancez la recherche dans les enfants gauche et droit.
- Si nous ne trouvons aucun nœud dont la valeur est égale à la cible, alors la valeur n'est pas présente dans l'arborescence.
Opérations auxiliaires sur l'arbre binaire
- Trouver la hauteur de l'arbre
- Trouver le niveau d'un nœud dans un arbre binaire
- Trouver la taille de l'arbre entier
Implémentation de l'arbre binaire
Ci-dessous le code pour l'insertion, la suppression et le parcours de l'arbre binaire :
C #include // Node structure to define the structure of the node typedef struct Node { int data; struct Node *left, *right; } Node; // Function to create a new node Node* newNode(int val) { Node* temp = (Node*)malloc(sizeof(Node)); temp->données = val ; temp->gauche = temp->droite = NULL ; température de retour ; } // Fonction pour insérer des nœuds Node* insert(Node* root, int data) { // Si l'arbre est vide, le nouveau nœud devient la racine if (root == NULL) { root = newNode(data); retourner la racine ; } // File d'attente pour parcourir l'arborescence et trouver la position pour insérer le nœud Node* queue[100]; int avant = 0, arrière = 0 ; file d'attente[arrière++] = racine; while (front != arrière) { Noeud* temp = file d'attente[front++]; // Insère le nœud comme enfant gauche du nœud parent if (temp->left == NULL) { temp->left = newNode(data); casser; } // Si l'enfant de gauche n'est pas nul, poussez-le vers la file d'attente else queue[rear++] = temp->left; // Insère le nœud comme enfant droit du nœud parent if (temp->right == NULL) { temp->right = newNode(data); casser; } // Si le bon enfant n'est pas nul, poussez-le vers la file d'attente else queue[rear++] = temp->right; } renvoie la racine ; } /* Fonction pour supprimer le nœud le plus profond donné (d_node) dans l'arborescence binaire */ void deletDeepest(Node* root, Node* d_node) { Node* queue[100]; int avant = 0, arrière = 0 ; file d'attente[arrière++] = racine; // Effectue un parcours par ordre de niveau jusqu'au dernier nœud Node* temp; while (avant != arrière) { temp = file d'attente[avant++]; if (temp == d_node) { temp = NULL; libre(d_node); retour; } if (temp->right) { if (temp->right == d_node) { temp->right = NULL; libre(d_node); retour; } else file d'attente[arrière++] = temp->right; } if (temp->left) { if (temp->left == d_node) { temp->left = NULL; libre(d_node); retour; } else queue[rear++] = temp->left; } } } /* Fonction pour supprimer un élément dans l'arborescence binaire */ Suppression du nœud* (racine du nœud*, clé int) { if (!root) return NULL; if (root->left == NULL && root->right == NULL) { if (root->data == key) return NULL ; sinon, retourne la racine ; } File d'attente de nœud*[100] ; int avant = 0, arrière = 0 ; file d'attente[arrière++] = racine; Température du nœud* ; Nœud* key_node = NULL ; // Effectue un parcours par ordre de niveau pour trouver le nœud le plus profond (temp) et le nœud à supprimer (key_node) while (front != Rear) { temp = queue[front++]; if (temp->data == key) key_node = temp; if (temp->left) file d'attente[arrière++] = temp->left; if (temp->right) file d'attente[arrière++] = temp->right; } if (key_node != NULL) { int x = temp->data; key_node->data = x; deleteDeepest(racine, temp); } renvoie la racine ; } // Traversée de l'arbre dans l'ordre (Gauche - Racine - Droite) void inorderTraversal(Node* root) { if (!root) return; inorderTraversal(racine->gauche); printf('%d ', racine->données); inorderTraversal(root->right); } // Traversée de l'arbre de précommande (Racine - Gauche - Droite) void preorderTraversal(Node* root) { if (!root) return; printf('%d ', racine->données); preorderTraversal(root->left); preorderTraversal(root->right); } // Traversée de l'arbre de post-ordre (Gauche - Droite - Racine) void postorderTraversal(Node* root) { if (root == NULL) return; postorderTraversal(root->gauche); postorderTraversal(root->right); printf('%d ', racine->données); } // Fonction pour le parcours de l'arbre d'ordre de niveau void levelorderTraversal(Node* root) { if (root == NULL) return; // File d'attente pour le parcours de l'ordre de niveau Node* queue[100]; int avant = 0, arrière = 0 ; queue[arrière++] = racine; while (front != arrière) { Noeud* temp = file d'attente[front++]; printf('%d ', temp->données); // Poussez l'enfant à gauche dans la file d'attente if (temp->left) queue[rear++] = temp->left; // Poussez l'enfant à droite dans la file d'attente if (temp->right) queue[rear++] = temp->right; } } /* Fonction pilote pour vérifier l'algorithme ci-dessus. */ int main() { Nœud* root = NULL ; // Insertion de nœuds root = insert(root, 10); racine = insert(racine, 20); racine = insert(racine, 30); racine = insert(racine, 40); printf('Traversée de précommande : '); preorderTraversal(racine); printf('
Parcours dans l'ordre : '); inorderTraversal(racine); printf('
Parcours de commande : '); postorderTraversal(racine); printf('
Parcours d'ordre de niveau : '); levelorderTraversal(racine); // Supprime le nœud avec data = 20 root = deletion(root, 20); printf('
Parcours dans l'ordre après suppression : '); inorderTraversal(racine); renvoie 0 ; }> Java import java.util.LinkedList; import java.util.Queue; // Node class to define the structure of the node class Node { int data; Node left, right; // Parameterized Constructor Node(int val) { data = val; left = right = null; } } public class BinaryTree { // Function to insert nodes public static Node insert(Node root, int data) { // If tree is empty, new node becomes the root if (root == null) { root = new Node(data); return root; } // Queue to traverse the tree and find the position to // insert the node Queueq = nouvelle LinkedList(); q.offer(racine); while (!q.isEmpty()) { Node temp = q.poll(); // Insère le nœud comme enfant gauche du nœud parent if (temp.left == null) { temp.left = new Node(data); casser; } // Si l'enfant de gauche n'est pas nul, poussez-le vers la // file d'attente else q.offer(temp.left); // Insère le nœud comme enfant droit du nœud parent if (temp.right == null) { temp.right = new Node(data); casser; } // Si le bon enfant n'est pas nul, poussez-le vers la // file d'attente else q.offer(temp.right); } renvoie la racine ; } /* fonction pour supprimer le nœud le plus profond donné (d_node) dans l'arborescence binaire */ public static void deletDeepest(Node root, Node d_node) { File d'attenteq = nouvelle LinkedList(); q.offer(racine); // Effectue un parcours par ordre de niveau jusqu'au dernier nœud Node temp; while (!q.isEmpty()) { temp = q.poll(); if (temp == d_node) { temp = null; d_node = nul ; retour; } if (temp.right != null) { if (temp.right == d_node) { temp.right = null; d_node = nul ; retour; } else q.offer(temp.right); } if (temp.left != null) { if (temp.left == d_node) { temp.left = null; d_node = nul ; retour; } else q.offer(temp.left); } } } /* fonction pour supprimer un élément dans l'arborescence binaire */ public static Node deletion(Node root, int key) { if (root == null) return null; if (root.left == null && root.right == null) { if (root.data == key) return null; sinon, retourne la racine ; } File d'attenteq = nouvelle LinkedList(); q.offer(racine); Température du nœud = nouveau nœud (0); Nœud key_node = null ; // Effectue un parcours d'ordre de niveau pour trouver // le nœud le plus profond (temp) et le nœud à supprimer (key_node) while (!q.isEmpty()) { temp = q.poll(); if (temp.data == key) key_node = temp; if (temp.left != null) q.offer(temp.left); if (temp.right != null) q.offer(temp.right); } if (key_node != null) { int x = temp.data; key_node.data = x; deleteDeepest(racine, temp); } renvoie la racine ; } // Traversée de l'arbre dans l'ordre (Gauche - Racine - Droite) public static void inorderTraversal(Node root) { if (root == null) return; inorderTraversal(root.left); System.out.print(root.data + ''); inorderTraversal(root.right); } // Traversée de l'arbre de précommande (Racine - Gauche - Droite) public static void preorderTraversal(Node root) { if (root == null) return; System.out.print(root.data + ''); preorderTraversal(root.left); preorderTraversal(root.right); } // Traversée de l'arbre de post-ordre (Gauche - Droite - Racine) public static void postorderTraversal(Node root) { if (root == null) return; postorderTraversal(root.left); postorderTraversal(root.right); System.out.print(root.data + ''); } // Fonction pour le parcours de l'arbre d'ordre de niveau public static void levelorderTraversal(Node root) { if (root == null) return; // File d'attente pour le parcours de l'ordre de niveauq = nouvelle LinkedList(); q.offer(racine); while (!q.isEmpty()) { Node temp = q.poll(); System.out.print(temp.data + ''); // Poussez l'enfant à gauche dans la file d'attente if (temp.left != null) q.offer(temp.left); // Poussez l'enfant droit dans la file d'attente if (temp.right != null) q.offer(temp.right); } } /* Fonction pilote pour vérifier l'algorithme ci-dessus. */ public static void main(String[] args) { Racine du nœud = null ; // Insertion de nœuds root = insert(root, 10); racine = insert(racine, 20); racine = insert(racine, 30); racine = insert(racine, 40); System.out.print('Traversée de précommande : '); preorderTraversal(racine); System.out.print('
Parcours dans l'ordre : '); inorderTraversal(racine); System.out.print('
Parcours de commande : '); postorderTraversal(racine); System.out.print('
Parcours d'ordre de niveau : '); levelorderTraversal(racine); // Supprime le nœud avec data = 20 root = deletion(root, 20); System.out.print('
Parcours dans l'ordre après suppression : '); inorderTraversal(racine); } }> Python from collections import deque # Node class to define the structure of the node class Node: def __init__(self, val): self.data = val self.left = self.right = None # Function to insert nodes def insert(root, data): # If tree is empty, new node becomes the root if root is None: root = Node(data) return root # Queue to traverse the tree and find the position to insert the node q = deque() q.append(root) while q: temp = q.popleft() # Insert node as the left child of the parent node if temp.left is None: temp.left = Node(data) break # If the left child is not null push it to the queue else: q.append(temp.left) # Insert node as the right child of parent node if temp.right is None: temp.right = Node(data) break # If the right child is not null push it to the queue else: q.append(temp.right) return root # Function to delete the given deepest node (d_node) in binary tree def deletDeepest(root, d_node): q = deque() q.append(root) # Do level order traversal until last node while q: temp = q.popleft() if temp == d_node: temp = None del d_node return if temp.right: if temp.right == d_node: temp.right = None del d_node return else: q.append(temp.right) if temp.left: if temp.left == d_node: temp.left = None del d_node return else: q.append(temp.left) # Function to delete element in binary tree def deletion(root, key): if not root: return None if root.left is None and root.right is None: if root.data == key: return None else: return root q = deque() q.append(root) temp = None key_node = None # Do level order traversal to find deepest node (temp) and node to be deleted (key_node) while q: temp = q.popleft() if temp.data == key: key_node = temp if temp.left: q.append(temp.left) if temp.right: q.append(temp.right) if key_node is not None: x = temp.data key_node.data = x deletDeepest(root, temp) return root # Inorder tree traversal (Left - Root - Right) def inorderTraversal(root): if not root: return inorderTraversal(root.left) print(root.data, end=' ') inorderTraversal(root.right) # Preorder tree traversal (Root - Left - Right) def preorderTraversal(root): if not root: return print(root.data, end=' ') preorderTraversal(root.left) preorderTraversal(root.right) # Postorder tree traversal (Left - Right - Root) def postorderTraversal(root): if root is None: return postorderTraversal(root.left) postorderTraversal(root.right) print(root.data, end=' ') # Function for Level order tree traversal def levelorderTraversal(root): if root is None: return # Queue for level order traversal q = deque() q.append(root) while q: temp = q.popleft() print(temp.data, end=' ') # Push left child in the queue if temp.left: q.append(temp.left) # Push right child in the queue if temp.right: q.append(temp.right) # Driver function to check the above algorithm if __name__ == '__main__': root = None # Insertion of nodes root = insert(root, 10) root = insert(root, 20) root = insert(root, 30) root = insert(root, 40) print('Preorder traversal:', end=' ') preorderTraversal(root) print('
Inorder traversal:', end=' ') inorderTraversal(root) print('
Postorder traversal:', end=' ') postorderTraversal(root) print('
Level order traversal:', end=' ') levelorderTraversal(root) # Delete the node with data = 20 root = deletion(root, 20) print('
Inorder traversal after deletion:', end=' ') inorderTraversal(root)> C# using System; using System.Collections.Generic; // Node class to define the structure of the node public class Node { public int data; public Node left, right; // Parameterized Constructor public Node(int val) { data = val; left = right = null; } } public class Program { // Function to insert nodes public static Node Insert(Node root, int data) { // If tree is empty, new node becomes the root if (root == null) { root = new Node(data); return root; } // Queue to traverse the tree and find the position to insert the node Queueq = nouvelle file d'attente(); q.Enqueue(racine); while (q.Count != 0) { Node temp = q.Dequeue(); // Insère le nœud comme enfant gauche du nœud parent if (temp.left == null) { temp.left = new Node(data); casser; } // Si l'enfant de gauche n'est pas nul, placez-le dans la file d'attente else q.Enqueue(temp.left); // Insère le nœud comme enfant droit du nœud parent if (temp.right == null) { temp.right = new Node(data); casser; } // Si le bon enfant n'est pas nul, placez-le dans la file d'attente else q.Enqueue(temp.right); } renvoie la racine ; } /* fonction pour supprimer le nœud le plus profond donné (d_node) dans l'arborescence binaire */ public static void DeleteDeepest(Node root, Node d_node) { File d'attenteq = nouvelle file d'attente(); q.Enqueue(racine); // Effectue un parcours par ordre de niveau jusqu'au dernier nœud Node temp; while (q.Count != 0) { temp = q.Dequeue(); if (temp == d_node) { temp = null; d_node = nul ; retour; } if (temp.right != null) { if (temp.right == d_node) { temp.right = null; d_node = nul ; retour; } else q.Enqueue(temp.right); } if (temp.left != null) { if (temp.left == d_node) { temp.left = null; d_node = nul ; retour; } else q.Enqueue(temp.left); } } } /* fonction pour supprimer un élément dans l'arborescence binaire */ public static Node Deletion(Node root, int key) { if (root == null) return null; if (root.left == null && root.right == null) { if (root.data == key) return null; sinon, retourne la racine ; } File d'attenteq = nouvelle file d'attente(); q.Enqueue(racine); Température du nœud = nouveau nœud (0); Nœud key_node = null ; // Effectuez un parcours par ordre de niveau pour trouver le nœud le plus profond (temp) et le nœud à supprimer (key_node) while (q.Count != 0) { temp = q.Dequeue(); if (temp.data == key) key_node = temp; if (temp.left != null) q.Enqueue(temp.left); if (temp.right != null) q.Enqueue(temp.right); } if (key_node != null) { int x = temp.data; key_node.data = x; SupprimerDeepest(racine, temp); } renvoie la racine ; } // Traversée de l'arbre dans l'ordre (Gauche - Racine - Droite) public static void InorderTraversal(Node root) { if (root == null) return; InorderTraversal(root.left); Console.Write(root.data + ' '); InorderTraversal(root.right); } // Traversée de l'arbre de précommande (Racine - Gauche - Droite) public static void PreorderTraversal(Node root) { if (root == null) return; Console.Write(root.data + ' '); PreorderTraversal(root.left); PrécommandeTraversal(root.right); } // Traversée de l'arbre de post-ordre (Gauche - Droite - Racine) public static void PostorderTraversal(Node root) { if (root == null) return; PostorderTraversal(root.left); PostorderTraversal(root.right); Console.Write(root.data + ' '); } // Fonction pour la traversée de l'arbre d'ordre de niveau public static void LevelorderTraversal(Node root) { if (root == null) return; // File d'attente pour le parcours de l'ordre de niveauq = nouvelle file d'attente(); q.Enqueue(racine); while (q.Count != 0) { Node temp = q.Dequeue(); Console.Write(temp.data + ''); // Poussez l'enfant à gauche dans la file d'attente if (temp.left != null) q.Enqueue(temp.left); // Poussez l'enfant à droite dans la file d'attente if (temp.right != null) q.Enqueue(temp.right); } } /* Fonction pilote pour vérifier l'algorithme ci-dessus. */ public static void Main(string[] args) { Racine du nœud = null ; // Insertion de nœuds root = Insert(root, 10); racine = Insérer (racine, 20); racine = Insérer (racine, 30); racine = Insérer (racine, 40); Console.Write('Parcours de précommande : '); PrécommandeTraversal(racine); Console.Write('
Parcours dans l'ordre : '); InorderTraversal(racine); Console.Write('
Parcours de commande : '); PostorderTraversal(racine); Console.Write('
Parcours d'ordre de niveau : '); LevelorderTraversal(racine); // Supprime le nœud avec data = 20 root = Deletion(root, 20); Console.Write('
Parcours dans l'ordre après suppression : '); InorderTraversal(racine); } }> Javascript // Node class to define the structure of the node class Node { constructor(val) { this.data = val; this.left = null; this.right = null; } } // Function to insert nodes function insert(root, data) { // If tree is empty, new node becomes the root if (root === null) { root = new Node(data); return root; } // queue to traverse the tree and find the position to // insert the node const q = []; q.push(root); while (q.length !== 0) { const temp = q.shift(); // Insert node as the left child of the parent node if (temp.left === null) { temp.left = new Node(data); break; } // If the left child is not null push it to the // queue else q.push(temp.left); // Insert node as the right child of parent node if (temp.right === null) { temp.right = new Node(data); break; } // If the right child is not null push it to the // queue else q.push(temp.right); } return root; } /* function to delete the given deepest node (d_node) in binary tree */ function deletDeepest(root, d_node) { const q = []; q.push(root); // Do level order traversal until last node let temp; while (q.length !== 0) { temp = q.shift(); if (temp === d_node) { temp = null; delete d_node; return; } if (temp.right) { if (temp.right === d_node) { temp.right = null; delete d_node; return; } else q.push(temp.right); } if (temp.left) { if (temp.left === d_node) { temp.left = null; delete d_node; return; } else q.push(temp.left); } } } /* function to delete element in binary tree */ function deletion(root, key) { if (!root) return null; if (root.left === null && root.right === null) { if (root.data === key) return null; else return root; } const q = []; q.push(root); let temp; let key_node = null; // Do level order traversal to find deepest // node(temp) and node to be deleted (key_node) while (q.length !== 0) { temp = q.shift(); if (temp.data === key) key_node = temp; if (temp.left) q.push(temp.left); if (temp.right) q.push(temp.right); } if (key_node !== null) { const x = temp.data; key_node.data = x; deletDeepest(root, temp); } return root; } // Inorder tree traversal (Left - Root - Right) function inorderTraversal(root) { if (!root) return; inorderTraversal(root.left); console.log(root.data + ' '); inorderTraversal(root.right); } // Preorder tree traversal (Root - Left - Right) function preorderTraversal(root) { if (!root) return; console.log(root.data + ' '); preorderTraversal(root.left); preorderTraversal(root.right); } // Postorder tree traversal (Left - Right - Root) function postorderTraversal(root) { if (root === null) return; postorderTraversal(root.left); postorderTraversal(root.right); console.log(root.data + ' '); } // Function for Level order tree traversal function levelorderTraversal(root) { if (root === null) return; // Queue for level order traversal const q = []; q.push(root); while (q.length !== 0) { const temp = q.shift(); console.log(temp.data + ' '); // Push left child in the queue if (temp.left) q.push(temp.left); // Push right child in the queue if (temp.right) q.push(temp.right); } } /* Driver function to check the above algorithm. */ let root = null; // Insertion of nodes root = insert(root, 10); root = insert(root, 20); root = insert(root, 30); root = insert(root, 40); console.log('Preorder traversal: '); preorderTraversal(root); console.log('
Inorder traversal: '); inorderTraversal(root); console.log('
Postorder traversal: '); postorderTraversal(root); console.log('
Level order traversal: '); levelorderTraversal(root); // Delete the node with data = 20 root = deletion(root, 20); console.log('
Inorder traversal after deletion: '); inorderTraversal(root);> C++14 #include using namespace std; // Node class to define the structure of the node class Node { public: int data; Node *left, *right; // Parameterized Constructor Node(int val) { data = val; left = right = NULL; } }; // Function to insert nodes Node* insert(Node* root, int data) { // If tree is empty, new node becomes the root if (root == NULL) { root = new Node(data); return root; } // queue to traverse the tree and find the position to // insert the node queueq; q.push(racine); while (!q.empty()) { Noeud* temp = q.front(); q.pop(); // Insère le nœud comme enfant gauche du nœud parent if (temp->left == NULL) { temp->left = new Node(data); casser; } // Si l'enfant de gauche n'est pas nul, poussez-le vers la // file d'attente else q.push(temp->left); // Insère le nœud comme enfant droit du nœud parent if (temp->right == NULL) { temp->right = new Node(data); casser; } // Si le bon enfant n'est pas nul, poussez-le vers la // file d'attente else q.push(temp->right); } renvoie la racine ; } /* fonction pour supprimer le nœud le plus profond donné (d_node) dans l'arborescence binaire */ void deletDeepest(Node* root, Node* d_node) { queueq; q.push(racine); // Effectue un parcours par ordre de niveau jusqu'au dernier nœud Node* temp; while (!q.empty()) { temp = q.front(); q.pop(); if (temp == d_node) { temp = NULL; supprimer (d_node); retour; } if (temp->right) { if (temp->right == d_node) { temp->right = NULL; supprimer (d_node); retour; } else q.push(temp->right); } if (temp->left) { if (temp->left == d_node) { temp->left = NULL; supprimer (d_node); retour; } else q.push(temp->left); } } } /* fonction pour supprimer un élément dans l'arborescence binaire */ Suppression du nœud* (racine du nœud*, clé int) { if (!root) return NULL; if (root->left == NULL && root->right == NULL) { if (root->data == key) return NULL ; sinon, retourne la racine ; } file d'attenteq; q.push(racine); Température du nœud* ; Nœud* key_node = NULL ; // Effectue un parcours par ordre de niveau pour trouver // le nœud le plus profond (temp) et le nœud à supprimer (key_node) while (!q.empty()) { temp = q.front(); q.pop(); if (temp->data == key) key_node = temp; if (temp->gauche) q.push(temp->gauche); if (temp->right) q.push(temp->right); } if (key_node != NULL) { int x = temp->data; key_node->data = x; deleteDeepest(racine, temp); } renvoie la racine ; } // Traversée de l'arbre dans l'ordre (Gauche - Racine - Droite) void inorderTraversal(Node* root) { if (!root) return; inorderTraversal(racine->gauche); cout<< root->données<< ' '; inorderTraversal(root->droite); } // Traversée de l'arbre de précommande (Racine - Gauche - Droite) void preorderTraversal(Node* root) { if (!root) return; cout<< root->données<< ' '; preorderTraversal(root->gauche); preorderTraversal(root->right); } // Traversée de l'arbre de post-ordre (Gauche - Droite - Racine) void postorderTraversal(Node* root) { if (root == NULL) return; postorderTraversal(root->gauche); postorderTraversal(root->right); cout<< root->données<< ' '; } // Function for Level order tree traversal void levelorderTraversal(Node* root) { if (root == NULL) return; // Queue for level order traversal queueq; q.push(racine); while (!q.empty()) { Noeud* temp = q.front(); q.pop(); cout<< temp->données<< ' '; // Push left child in the queue if (temp->gauche) q.push(temp->gauche); // Poussez l'enfant à droite dans la file d'attente if (temp->right) q.push(temp->right); } } /* Fonction pilote pour vérifier l'algorithme ci-dessus. */ int main() { Nœud* root = NULL ; // Insertion de nœuds root = insert(root, 10); racine = insert(racine, 20); racine = insert(racine, 30); racine = insert(racine, 40); cout<< 'Preorder traversal: '; preorderTraversal(root); cout << '
Inorder traversal: '; inorderTraversal(root); cout << '
Postorder traversal: '; postorderTraversal(root); cout << '
Level order traversal: '; levelorderTraversal(root); // Delete the node with data = 20 root = deletion(root, 20); cout << '
Inorder traversal after deletion: '; inorderTraversal(root); }> Sortir
Preorder traversal: 10 20 40 30 Inorder traversal: 40 20 10 30 Postorder traversal: 40 20 30 10 Level order traversal: 10 20 30 40 Inorder traversal after deletion: 40 10 30>
Analyse de complexité des opérations d'arbre binaire
| Opérations | Complexité temporelle | Complexité spatiale |
|---|---|---|
| Insertion | SUR) | SUR) |
| Traversée de précommande | SUR) | SUR) |
Traversée dans l'ordre | SUR) | SUR) |
| Traversée des commandes postales | SUR) | SUR) |
| Traversée de l'ordre des niveaux | SUR) | SUR) |
Effacement Gimp comment désélectionner | SUR) | SUR) |
Recherche | SUR) | SUR) |
On peut utiliser Traversée Morris pour parcourir tous les nœuds de l'arbre binaire en temps O(1).
Avantages de l'arbre binaire
- Recherche efficace : Les arbres binaires sont efficaces lors de la recherche d'un élément spécifique, car chaque nœud a au plus deux nœuds enfants, ce qui permet Mémoire efficace : Les arbres binaires nécessitent moins de mémoire que les autres structures de données arborescentes, ils sont donc efficaces en termes de mémoire.
- Les arbres binaires sont relativement faciles à mettre en œuvre et à comprendre car chaque nœud a au plus deux enfants, l'enfant gauche et l'enfant droit.
Inconvénients de l'arbre binaire
- Structure limitée : Les arbres binaires sont limités à deux nœuds enfants par nœud, ce qui peut limiter leur utilité dans certaines applications. Par exemple, si une arborescence nécessite plus de deux nœuds enfants par nœud, une structure arborescente différente peut être plus adaptée.
- Arbres déséquilibrés : Les arbres binaires déséquilibrés, dans lesquels un sous-arbre est nettement plus grand que l'autre, peuvent conduire à des opérations de recherche inefficaces. Cela peut se produire si l'arborescence n'est pas correctement équilibrée ou si les données sont insérées dans un ordre non aléatoire.
- Inefficacité spatiale : Les arbres binaires peuvent être inefficaces en termes d'espace par rapport à d'autres structures de données. En effet, chaque nœud nécessite deux pointeurs enfants, ce qui peut représenter une surcharge de mémoire importante pour les grandes arborescences.
- Performances lentes dans les pires scénarios : Dans le pire des cas, un arbre binaire peut devenir dégénéré ou asymétrique, ce qui signifie que chaque nœud n'a qu'un seul enfant. Dans ce cas, les opérations de recherche peuvent se dégrader jusqu’à une complexité temporelle O(n), où n est le nombre de nœuds dans l’arborescence.
Applications de l'arbre binaire
- L'arbre binaire peut être utilisé pour représenter des données hiérarchiques .
- Les arbres de codage de Huffman sont utilisés dans algorithmes de compression de données .
- File d'attente de priorité est une autre application de l'arbre binaire utilisée pour rechercher le maximum ou le minimum dans une complexité temporelle O(1).
- Utile pour l'indexation segmentée au niveau de la base de données, il est utile pour stocker le cache dans le système,
- Les arbres binaires peuvent être utilisés pour mettre en œuvre des arbres de décision, un type d'algorithme d'apprentissage automatique utilisé pour l'analyse de classification et de régression.
Foire aux questions sur l'arbre binaire
1. Qu'est-ce qu'un arbre binaire ?
Un arbre binaire est une structure de données non linéaire composée de nœuds, où chaque nœud a au plus deux enfants (l'enfant de gauche et l'enfant de droite).
2. Quels sont les types d’arbres binaires ?
Les arbres binaires peuvent être classés en différents types, notamment les arbres binaires complets, les arbres binaires complets, les arbres binaires parfaits, les arbres binaires équilibrés (tels que les arbres AVL et les arbres rouge-noir) et les arbres binaires dégénérés (ou pathologiques).
CSS centrant une image
3. Quelle est la hauteur d’un arbre binaire ?
La hauteur d'un arbre binaire est la longueur du chemin le plus long allant du nœud racine à un nœud feuille. Il représente le nombre d'arêtes dans le chemin le plus long allant du nœud racine à un nœud feuille.
4. Quelle est la profondeur d’un nœud dans un arbre binaire ?
La profondeur d'un nœud dans un arbre binaire est la longueur du chemin allant du nœud racine à ce nœud particulier. La profondeur du nœud racine est 0.
5. Comment effectuer une traversée d'arbre dans un arbre binaire ?
Le parcours d'arbre dans un arbre binaire peut être effectué de différentes manières : parcours dans l'ordre, parcours en pré-ordre, parcours en post-ordre et parcours par ordre de niveau (également connu sous le nom de parcours en largeur d'abord).
6. Qu'est-ce qu'un parcours Inorder dans un arbre binaire ?
Dans le parcours Inorder, les nœuds sont visités de manière récursive dans cet ordre : enfant gauche, racine, enfant droit. Ce parcours entraîne la visite des nœuds dans un ordre non décroissant dans un arbre de recherche binaire.
7. Qu'est-ce qu'un parcours de précommande dans un arbre binaire ?
Dans le parcours Preorder, les nœuds sont visités de manière récursive dans cet ordre : racine, enfant gauche, enfant droit. Ce parcours fait que le nœud racine est le premier nœud à être visité.
8. Qu'est-ce qu'un parcours post-ordre dans un arbre binaire ?
Dans le parcours post-ordre, les nœuds sont visités de manière récursive dans cet ordre : enfant gauche, enfant droit et racine. Ce parcours fait que le nœud racine est le dernier nœud à être visité.
9. Quelle est la différence entre un arbre binaire et un arbre de recherche binaire ?
Un arbre binaire est une structure de données hiérarchique dans laquelle chaque nœud a au plus deux enfants, tandis qu'un arbre de recherche binaire est un type d'arbre binaire dans lequel l'enfant de gauche d'un nœud contient des valeurs inférieures à la valeur du nœud et l'enfant de droite contient des valeurs. supérieure à la valeur du nœud.
10. Qu'est-ce qu'un arbre binaire équilibré ?
Un arbre binaire équilibré est un arbre binaire dans lequel la hauteur des sous-arbres gauche et droit de chaque nœud diffère d'au plus un. Les arbres équilibrés aident à maintenir des opérations efficaces telles que la recherche, l'insertion et la suppression avec des complexités temporelles proches de O (log n).
Conclusion:
L'arborescence est une structure de données hiérarchique. Les principales utilisations des arbres incluent la maintenance des données hiérarchiques, la fourniture d'un accès modéré et d'opérations d'insertion/suppression. Les arbres binaires sont des cas particuliers d'arbres où chaque nœud a au plus deux enfants.
Articles Liés:
- Propriétés de l'arbre binaire
- Types d'arbre binaire