Un, la définition de l'arbre de tri binaire
1. Définition de l'arbre de tri binaire <Br /> Tri binaire (arbre de tri binaire), également connu sous le nom d'arbre de recherche binaire. Il est défini comme: un arbre de tri binaire ou un arbre vide, ou un arbre binaire qui répond aux propriétés suivantes:
① Si son sous-arbre gauche n'est pas vide, les valeurs de tous les nœuds du sous-arbre gauche sont plus petites que la valeur du nœud racine;
② Si son sous-arbre droit n'est pas vide, les valeurs de tous les nœuds du sous-arbre droit sont supérieures aux valeurs du nœud racine;
③Les sous-arbres gauche et droit eux-mêmes sont chacun un arbre de tri binaire.
Les propriétés ci-dessus sont appelées la propriété de l'arborescence de tri binaire (propriété BST), de sorte que l'arbre de tri binaire est en fait un arbre binaire qui satisfait la propriété BST.
2. Propriétés de l'arbre de tri binaire <Br /> Transférer l'arbre de tri binaire dans l'ordre moyen, et la séquence de traversée d'ordre intermédiaire résultant est une séquence ordonnée incrémentielle.
3. Insérez l'arbre de tri binaire <r /> insérer un nouveau nœud dans l'arbre de tri binaire, pour vous assurer que l'arbre binaire inséré répond toujours à la définition de l'arbre de tri binaire.
Insérer le processus:
Si l'arbre de tri binaire est vide, le nœud * est inséré dans l'arbre vide comme nœud racine;
Lorsqu'il n'est pas vide, comparez la touche clé S-> à insérer avec le mot-clé racine arborescence T-> touche. Si s-> key = t-> touche, il n'est pas nécessaire de l'insérer. Si la clé S-> Key <T->, elle est insérée dans le sous-arbre gauche de la racine. Si la touche S->> T->, elle est insérée dans le sous-arbre droit de la racine. Le processus d'insertion dans le sous-arbre est le même que le processus d'insertion dans l'arbre. Cela continue jusqu'à ce que le nœud * soit inséré dans l'arbre de tri binaire en tant que nouvelle feuille, ou jusqu'à ce que l'arbre ait des nœuds avec les mêmes mots clés.
4. Recherche d'arbre de tri binaire <br /> en supposant que le pointeur racine de l'arborescence de tri binaire est root et que la valeur du mot-clé donné est k, l'algorithme de recherche peut être décrit comme:
① Définir la valeur initiale: q = root;
② Si k = q -> clé, la recherche est réussie et l'algorithme se termine;
③ Sinon, si la clé k <q －＞ et le sous-arbre gauche de q n'est pas vide, le sous-arbre gauche de q est envoyé à Q puis l'étape ②; Sinon, la recherche échoue et l'algorithme se termine;
④ Sinon, si K ＞ Q －＞ Key, et que le sous-arbre droit de Q n'est pas vide, le sous-arbre droit de Q est envoyé à Q puis l'étape ②; Sinon, la recherche échoue et l'algorithme se termine.
5. Délétion de l'arbre de tri binaire <Br /> Supposons que le nœud supprimé soit * p et que les parents sont * f, qui ne sont pas perdus dans la généralité. Supposons que * p est l'enfant gauche de * f, les éléments suivants sont divisés en trois situations:
⑴ Si le nœud * p est un nœud de feuille, il vous suffit de modifier le pointeur de son nœud parent * f.
⑵ Si le nœud * p a seulement le sous-arbre gauche PL ou uniquement le sous-arbre droit droit, faites simplement pl ou pr le sous-arbre gauche de son nœud parent.
⑶ Si les sous-arbres gauche et droit du nœud * p ne sont pas vides, trouvez d'abord le nœud du prédécesseur (ou successeur) de l'ordre moyen de * P (notez que * s est le nœud le plus à droite inférieur dans le sous-arbre gauche de * p, et son domaine de chaîne droite est vide), puis il y a deux façons: ① Laisse le sous-trace gauche de * P enchaîné à la chaîne droite du nœud prédécesseur de l'ordre moyen de * P * s. ② Remplacer * P par le nœud prédécesseur de l'ordre moyen * S de * p (c'est-à-dire copier les données de * s en * p), et enchaîner le sous-arbre gauche de * s vers la chaîne gauche (ou droite) du nœud parent * q de * s.
6. Traversion des arbres binaires <Br /> Il existe trois façons de traverser les arbres binaires, comme suit:
(1. Racine abrégée - gauche - droite.
(2) Traversion dans l'ordre (LDR), d'abord traverser le sous-arbre gauche, puis accéder au nœud racine et enfin traverser le sous-arbre droit. Remarque abrégée: ROT-ROOT-DIGMENT.
(3) Traversion post-ordre (LRD), traversant d'abord le sous-arbre gauche, puis traversant le sous-arbre droit et accédant enfin au nœud racine. Abrégé à gauche-droite.
2. Écriture de code
1. Définition du nœud d'arbre Classe 0
package com.lin; / ** * Résumé de la fonction: * / classe publique Treenode {Données entières publiques; / * Nœud parent de ce nœud * / public Treenode Parent; / * Nœud enfant gauche de ce nœud * / public Treenode à gauche; / * Right Child Node de ce nœud * / public Treenode à droite; Public Treenode (données entiers) {this.data = data; } @Override public String toString () {return "Treenode [data =" + data + "]"; }} 2. Définition de l'arbre de tri binaire
package com.lin; / ** * Résumé de la fonction: Sort / arbre binaire équilibré * / classe publique SearchTree {public Treenode Root; taille longue du public; / ** * Ajouter un nœud à l'arborescence * @param data * @return booléen insertion renvoie true * / public boolean addTreenode (integer data) {if (null == root) {root = new Treenode (data); System.out.println ("Les données ont été insérées avec succès dans l'arbre binaire équilibré"); Retour Vrai; } Treenode Treenode = new Treenode (données); // les données à insérer Treenode CurrentNode = root; Treenode ParentNode; while (true) {parentNode = currentNode; // Enregistrer le nœud parent // Les données insérées sont plus petites que le nœud parent if (currentNode.data> data) {currentNode = currentNode.Left; // Le nœud enfant gauche du nœud parent actuel est vide if (null == currentNode) {parentNode.left = Treenode; Treenode.parent = parentNode; System.out.println ("Les données ont été insérées avec succès dans l'arborescence de recherche binaire"); taille ++; Retour Vrai; } // Les données insérées sont plus grandes que le nœud parent} else if (currentNode.data <data) {currentNode = currentNode.Right; // Le nœud enfant droit du nœud parent actuel est vide if (null == currentNode) {parentNode.Right = Treenode; Treenode.parent = parentNode; System.out.println ("Les données sont insérées avec succès dans l'arborescence de recherche binaire"); taille ++; Retour Vrai; }} else {System.out.println ("Les données d'entrée sont les mêmes que les données du nœud"); retourne false; }}} / ** * @param data * @return Treenode * / public Treenode findTreenode (Integer data) {if (null == root) {return null; } Treenode Current = root; while (current! = null) {if (current.data> data) {current = current.left; } else if (current.data <data) {current = current.Right; } else {return current; }} return null; }} Voici une méthode d'ajout et de recherche
3. Traversé avant, moyen et arrière
package com.lin; import java.util.stack; / ** * Résumé de la fonction: * / classe publique Treeorder {/ ** * Implémentation récursive de la traversée de précommande * @Author Linbingwen * @Since 29 août 2015 * @param Treenode * / public static void PreorderMethodone (Treenode Treenode) {if (null! = Treenode) {System.out.print (Treenode.Data.Data + "" "" if (null! = Treenode.Left) {preOrderMethodone (Treenode.Left); } if (null! = Treenode.Right) {preorderMethodone (Treenode.Right); }}} / ** * boucle pour implémenter la précommande Traversal * @param Treenode * / public static void preorderMethodtwo (Treenode Treenode) {if (null! = Treenode) {stack <rerenode> stack = new Stack <rerenode> (); Stack.push (Treenode); while (! stack.isempty ()) {Treenode tempnode = stack.pop (); System.out.print (tempnode.data + ""); // Le nœud enfant bon n'est pas nul, mettez le bon nœud enfant dans if (null! = Tempnode.right) {stack.push (tempnode.Right); } // Après avoir mis le nœud enfant droit, mettez le nœud enfant gauche et prenez if (null! = Tempnode.left) {stack.push (tempnode.left); }}}} / ** * Implémentez récursivement Traversal dans l'ordre * @param Treenode * / public static void medOrderMethodone (Treenode Treenode) {if (null! = Treenode) {if (null! = Treenode.left) {medOrderMethodone (Treenode.left); } System.out.print (Treenode.Data + ""); if (null! = Treenode.Right) {medOrderMethodone (Treenode.Right); }}} / ** * Loop Implémentation In-Order Traversal * @param Treenode * / public static void medOrderMethodtwo (Treenode Treenode) {stack <reenode> pile = new Stack <rerenode> (); Treenode Current = Treenode; while (current! = null ||! stack.isempty ()) {while (current! = null) {stack.push (current); courant = courant.left; } if (! stack.isempty ()) {current = stack.pop (); System.out.print (Current.Data + ""); courant = courant.Right; }}} / ** * Implémentation récursive Post-Order Traversal * @param Treenode * / public static void PostOrderMethodone (Treenode Treenode) {if (null! = Treenode) {if (null); } if (null! = Treenode.Right) {postOrderMethodone (Treenode.Right); } System.out.print (Treenode.Data + ""); }} / ** * boucle pour implémenter la traversée post-ordre * @param Treenode * / public static void PostOrderMethodtwo (Treenode Treenode) {if (null! = Treenode) {stack <rerenode> stack = new Stack <rerenode> (); Treenode Current = Treenode; Treenode RightNode = null; while (current! = null ||! stack.isempty ()) {while (current! = null) {stack.push (current); courant = courant.left; } current = stack.pop (); while (current! = null && (current.right == null || current.Right == RightNode)) {System.out.print (current.data + ""); RightNode = Current; if (stack.isempty ()) {System.out.println (); retour; } current = stack.pop (); } stack.push (courant); courant = courant.Right; }}}} 4. Comment utiliser
package com.lin; / ** * Résumé de la fonction: * / classe publique SearchTreetSest {/ ** * @param args * / public static void main (String [] args) {SearchTree arbre = new SearchTree (); Tree.AddTreenode (50); Tree.AddTreenode (80); Tree.AddTreenode (20); Tree.AddTreenode (60); Tree.AddTreenode (10); Tree.AddTreenode (30); Tree.AddTreenode (70); Tree.AddTreenode (90); Tree.AddTreenode (100); Tree.AddTreenode (40); System.out.println("===================================================================================================== =====================================================================. ======================================================================. =====================================================================. ======================================================================. ======================================================================. ======================================================================. System.out.println ("========================================================= ============================================================================. ============================================================================. ===============================================================================. ============================================================================. ============================================================================. ============================================================================. ===============================================================================. TreeOrder.PostorderMethodone (arbre.root); System.out.println (); System.out.println("====================================================================================================== ======================================================================. =======================================================================. ======================================================================. =======================================================================. ======================================================================. =======================================================================. System.out.println ("========================================================= ============================================================================. ============================================================================. ===============================================================================. ============================================================================. ============================================================================. ============================================================================. ===============================================================================. TreeOrder.MedorderMethodtwo (Tree.root);Résultat de sortie:
De même, le processus de recherche est le suivant:
Treenode Node = Tree.FindTreenode (100); System.out.println (nœud);
Le résultat est correct
Ce qui précède est une introduction détaillée à l'arbre de tri binaire Java. J'espère que cela sera utile à l'apprentissage de la programmation Java.