Annonces

l’Arbre représente les nœuds reliés par des arêtes. Nous discuterons de l’arbre binaire ou de l’arbre de recherche binaire en particulier.

Binary Tree est une structure de données spéciale utilisée à des fins de stockage de données. Un arbre binaire a une condition spéciale que chaque nœud puisse avoir un maximum de deux enfants., Un arbre binaire présente les avantages d’un tableau ordonné et d’une liste chaînée, car la recherche est aussi rapide que dans un tableau trié et les opérations d’insertion ou de suppression sont aussi rapides que dans une liste chaînée.

termes importants

Voici les termes importants par rapport à l’arbre.

  • Chemin − Chemin fait référence à la séquence de nœuds le long des bords d’un arbre.

  • Root − le nœud en haut de l’arbre s’appelle root. Il n’y a qu’une seule racine par arbre et un chemin du nœud racine vers n’importe quel nœud.,

  • Parent − tout nœud à l’exception du nœud racine a un bord vers le haut jusqu’à un nœud appelé parent.

  • l’Enfant − Le nœud en dessous d’un nœud donné relié par son bord vers le bas est appelé nœud enfant.

  • − Feuilles, Le nœud qui n’a pas de nœud enfant est appelé le nœud feuille.

  • – Arbre − sous-Arborescence représente les descendants d’un nœud.

  • visite − la visite fait référence à la vérification de la valeur d’un nœud lorsque le contrôle est sur le nœud.

  • Traverser − traverser signifie passer par des nœuds dans un ordre spécifique.,

  • les Niveaux − du Niveau d’un nœud représente la génération d’un nœud. Si le nœud racine est au niveau 0, puis son prochain nœud enfant est au niveau 1, son petit-fils est au niveau 2, et ainsi de suite.

  • touches − Clé représente une valeur d’un nœud sur la base de laquelle une opération de recherche est effectué pour un nœud.

Binaire de Recherche, de Représentation en Arborescence

arbre de Recherche Binaire présente un comportement particulier. L’enfant gauche d’un nœud doit avoir une valeur inférieure à la valeur de son parent et l’enfant droit du nœud doit avoir une valeur supérieure à sa valeur parent.,

Nous allons implémenter tree en utilisant un objet node et les connecter via des références.

nœud D’arbre

le code pour écrire un nœud d’arbre serait similaire à ce qui est donné ci-dessous. Il a une partie de données et des références à ses nœuds enfants gauche et droit.

struct node { int data; struct node *leftChild; struct node *rightChild;};

Dans un arbre, tous les nœuds communs de construire.

BST Opérations de Base

Les opérations de base qui peuvent être effectuées sur un arbre de recherche binaire structure de données, sont les suivantes:

  • Insert Insère un élément dans un arbre/créer un arbre.,

  • Search − Recherche un élément dans une arborescence.

  • Preorder Traversal − traverse un arbre de manière précommande.

  • Aussitôt la Traversée − Parcourt un arbre dans un ordre de manière.

  • Postorder Traversal − traverse un arbre de manière post-ordre.

Nous allons apprendre à créer (insérer dans) une structure arborescente et à rechercher un élément de données dans un arbre dans ce chapitre. Nous allons en apprendre davantage sur les méthodes de traversée d’arbres dans le prochain chapitre.

Insertion

La première insertion crée l’arbre., Ensuite, chaque fois qu’un élément doit être inséré, localisez d’abord son emplacement approprié. Commencez la recherche à partir du nœud racine, puis si les données sont inférieures à la valeur de la clé, recherchez l’Emplacement vide dans le sous-arbre de gauche et insérez les données. Sinon, recherchez l’Emplacement vide dans le sous-arbre de droite et insérez les données.,

algorithme

If root is NULL then create root nodereturnIf root exists then compare the data with node.data while until insertion position is located If data is greater than node.data goto right subtree else goto left subtree endwhile insert dataend If

implémentation

l’implémentation de la fonction insert devrait ressembler à ceci −

opération de recherche

chaque fois qu’un élément doit être recherché, commencez la recherche à partir du nœud racine, puis si les données sont inférieures à la valeur clé, recherchez Sinon, recherchez l’élément dans le sous-arbre de droite. Suivez le même algorithme pour chaque nœud.

l’Algorithme

If root.data is equal to search.data return rootelse while data not found If data is greater than node.data goto right subtree else goto left subtree If data found return node endwhile return data not found end if

La mise en œuvre de cet algorithme devrait ressembler à ceci.,

pour connaître la mise en œuvre de la structure de données de l’arbre de recherche binaire, veuillez cliquer ici.

Annonces