|
Un arbre binaire de recherche est une structure de données dans laquelle les enregistrements de données , appelées «nœuds», ont pointeurs vers d'autres nœuds , appelés «enfants». Cela donne les noeuds , quand graphiquement sur , une forme semblable à un arbre généalogique . Les nœuds reçoivent leur place dans l'arbre selon qu'ils évalueraient comme supérieur ou inférieur à d'autres nœuds. Enfants laissés sont toujours inférieures à leurs parents , les enfants toujours raison arbres de recherche more.Binary sont importants en informatique , car ils peuvent être à la fois triés et fouillé , en moyenne, en O ( n log n) . Choses que vous devez
compilateur
existant binaire arbre de recherche
Afficher plus Instructions
1 Créer une fonction de stockage qui reçoit le nœud racine. Si vous travaillez avec des arbres dans l'informatique, l'algorithme le plus efficace sera presque toujours récurrent et le stockage de l'arbre dans un fichier ne fera pas exception . Voici un squelette de l'échantillon de la fonction de sauvegarde récursive (en Java). Magasin public void (Node n ) throws IOException {...}
2 écrire des données sur le nœud racine dans un fichier. Cela va utiliser «pré -ordre " (Root, Gauche enfant, le droit enfant ) pour passer en revue tous les nœuds de l'arbre , parce que cette méthode de parcours , il sera plus facile de reconstruire l'arbre de l'ordre des nœuds dans le fichier . La fonction récursive ressemble maintenant à ceci : magasin public void (Node n ) throws IOException {write ( savefile , n) ;} magasin devrait s'appeler avec l' enfant de gauche : Magasin public void (Node n ) throws IOException {write ( savefile , n ) ; magasin ( n.left );} magasin devrait s'appeler à l'enfant le droit : Magasin public void (Node n ) throws IOException {write ( savefile , n) ; magasin ( n.left ) ; magasin ( n.right ) ; }
3 Double- vérifier que la fonction passe la liste récursive. Pour éviter toute erreur de débordement de pile , toujours vérifier que la fonction récursive remplit les conditions suivantes : Est-ce que la fonction possède un état de sortie? Oui , tant que l'arbre n'est pas d' une profondeur infinie , elle finira par atteindre un nœud qui n'a ni enfant gauche ou la droite et la exit.Does chaque itération de la fonction se rapprocher de l'état de sortie? Oui , en supposant que l'arbre n'est pas circulaire et aucun noeud a l'un de ses ancêtres en fonction child.The passe la liste.
4 Reconstruire à partir du fichier . Quand vient le temps de charger l'arbre à partir du fichier , vous aurez simplement à insérer chaque nœud dans l'arbre comme il est chargé à partir du fichier en utilisant votre algorithme d'insertion standard. Cela devrait commencer à la racine et se frayer un chemin vers le bas à l'aide de pré -ordre , en plaçant le nouveau nœud dans le premier espace vide dans lequel il va s'insérer. Ceci devrait reconstruire l'arbre exactement comme il était initialement composée en O ( n log n) en moyenne .
|
