Java implémente l'arborescence de recherche binaire et met en œuvre des opérations de recherche, d'insertion et de suppression de l'arborescence (fusionner et supprimer, copier et supprimer)
Tout d'abord, nous devons avoir une idée de codage, à peu près comme suit:
1. Recherche: Selon les caractéristiques des données de l'arborescence de recherche binaire, nous pouvons réaliser la recherche en fonction de la comparaison de valeur des nœuds. Lorsque la valeur de recherche est supérieure au nœud actuel, allez à droite, et vice versa!
2. INSERT: Nous devons savoir que tous les nœuds de feuilles insérés sont insérés, nous devons donc trouver l'insertion de l'emplacement du nœud feuille, et l'idée d'insertion est cohérente avec l'idée de recherche.
3. Supprimer:
1) Fusionner et supprimer: De manière générale, les situations suivantes seront rencontrées. Le nœud supprimé a un sous-arbre gauche mais pas de sous-arbre droit. À l'heure actuelle, le nœud parent du nœud actuel doit pointer vers le sous-arbre gauche du nœud actuel; Lorsque le nœud supprimé a un sous-arbre droit mais pas de sous-arbre gauche, le nœud parent du nœud actuel doit pointer vers le sous-arbre droit; Lorsque le nœud supprimé a un sous-arbre gauche et un sous-arbre droit, nous pouvons trouver le nœud le plus à droite du sous-arbre gauche du nœud supprimé, puis laisser le "pointeur" droit ou gauche de ce nœud pointer vers le sous-arbre droit du nœud supprimé
2) Copier et suppression: la copie et la suppression sont des opérations de suppression relativement simples et sont également les opérations de suppression les plus couramment utilisées. Il y a environ trois situations: lorsque le nœud actuel n'a pas de sous-arbre gauche et a un sous-arbre droit, laissez le nœud racine du sous-arbre droit actuel remplacer le nœud supprimé; Lorsque le nœud actuel n'a pas de sous-arbre droit et a un sous-arbre gauche, laissez le nœud racine du sous-arbre gauche actuel et remplacez le nœud supprimé; Lorsque le nœud actuellement supprimé a à la fois un sous-arbre gauche et un sous-arbre droit, nous devons trouver le sous-arbre du nœud supprimé, et trouver le nœud le plus à droite dans le sous-arbre gauche et attribuer la valeur de ce nœud au nœud supprimé, puis n'oubliez pas pour laisser le "pointeur" le traiter automatiquement). Vous pouvez également implémenter ce processus en tant que nœud autonome sur le nœud le plus à gauche du sous-arbre droit du nœud actuellement supprimé.
Ensuite, ajoutons le code.
Tout d'abord, ## Classe de nœuds d'arborescence binaire ##
package SearchBinaryTree; public class SearchBinaryTeenode <T> {t data; Public SearchBinaryTreenode <T> LeftChild; Public SearchBinaryTreenode <T> RightChild; public SearchBinaryTreenode () {this.data = null; this.leftchild = this.RightChild = null; } public SearchBinaryTreenode (t da) {this.data = da; this.leftchild = this.RightChild = null; } public SearchBinaryTreenode (t da) {this.data = da; this.leftchild = this.RightChild = null; } public SearchBinaryTreenode (T DA, SearchBinaryTreenode <T> gauche, SearchBinaryTreenode <T> droite) {this.data = da; this.leftchild = gauche; this.RightChild = droite; } public t getData () {return data; } public void setData (t data) {this.data = data; } public SearchBinaryTreenode <T> getleftchild () {return LeftChild; } public void SetLeftChild (SearchBinaryTreenode <T> LeftChild) {this.leftchild = LeftChild; } public SearchBinaryTreenode <T> getRightChild () {return rightchild; } public void setRightChild (SearchBinaryTreenode <T> RightChild) {this.RightChild = RightChild; } public boolean isleaf () {if (this.leftchild == null && this.Rightchild == null) {return true; } return false; }}Implémentation d'un arbre de recherche binaire
package SearchBinaryTree; public class SearchBinaryTree <T> {SearchBinaryTreenode <T> root; public boolean isEmpty () {if (root == null) {return true; } return false; } public void Visit (SearchBinaryTreenode <T> root) {if (root == null) {System.out.println ("Cet arbre est vide!"); } System.out.println (root.getData ()); } public SearchBinaryTreenode <T> Getroot () {if (root == null) {root = new SearchBinaryTeenode <T> (); } return root; } public SearchBinaryTree () {this.root = null; } / * * Créer un arbre binaire * / public void CreateTree (SearchBinaryTreenode <T> Node, t data) {if (root == null) {root = new SearchBinaryTreenode <T> (); } else {if (math.random ()> 0.5) {// Créer un arbre binaire d'une manière aléatoire if (node.leftchild == null) {node.leftchild = new SearchBinaryTreenode <T> (data); } else {createTree (node.leftchild, data); }} else {if (node.RightChild == null) {node.RightChild = new SearchBinaryTreenode <T> (data); } else {CreateTree (Node.RightChild, données); }}}}} / * * Recherche dans le deuxième arborescence de recherche de recherche * / public SearchBinaryTreenode <T> Search (searchBinaryTeenode <T> root, t valeur) {SearchBinaryTreenode <T> current = root; while ((root! = null) && (current.getData ()! = valeur)) {// Il convient de noter que les génériques en Java ne peuvent pas comparer les tailles. Dans une utilisation réelle, nous pouvons utiliser des types de données courants pour remplacer ce générique, il n'y aura donc pas d'erreurs. Current = (valeur <current.getData ()? Search (current.leftchild, valeur): search (current.RightChild, valeur)); } Retour courant; } public SearchBinaryTreenode <T> insertNode (TALAGNE T) {SearchBinaryTreenode <T> P = root, pre = null; while (p! = null) {pre = p; // Il convient de noter que les génériques en Java ne peuvent pas comparer les tailles. En usage réel, nous pouvons utiliser des types de données courants pour remplacer ce générique, de sorte qu'il n'y aura pas d'erreurs si (p.getData () <valeur) {p = p.RightChild; } else {p = p.leftchild; }} if (root == null) {root = new SearchBinaryTeenode <T> (valeur); } else if (pre.getData () <value) {pre.RightChild = new SearchBinaryTreenode <T> (valeur); } else {pre.leftchild = new SearchBinaryTreenode <T> (valeur); }} / * * Merge et supprimer * / public void DeleteBymerging (SearchBinaryTeenode <T> Node) {SearchBinaryTeenode <T> temp = node; if (nœud! = null) {// Si le nœud supprimé n'a pas de sous-arbre droit, utilisez le nœud racine de son sous-arbre gauche pour remplacer le nœud supprimé if (node.RightChild! = null) {node = node.leftchild; } else if (node.leftchild == null) {// Si le nœud supprimé n'a pas de sous-arbre gauche, utilisez le nœud le plus à gauche avec le nombre de mots au lieu du nœud supprimé Node = Node.RightChild; } else {// Si les sous-arbres gauche et droit des nœuds supprimés ont temp = node.leftchild; while (temp.RightChild! = null) {temp = temp.RightChild; // Trouvez suivant le nœud droit du sous-arbre gauche} // attribuez le pointeur droit du nœud trouvé à la racine du sous-arbre droit du nœud supprimé temp.RightChild = node.RightChild; temp = nœud; node = node.leftchild; } temp = null; }} / * * Copier et supprimer * / public void DeleteByCoping (SearchBinaryTreenode <T> Node) {SearchBinaryTreenode <T> pre = null; SearchBinaryTreenode <T> Temp = Node; // Si le nœud supprimé n'a pas de sous-arbre droit, utilisez le nœud racine de son sous-arbre gauche pour remplacer le nœud supprimé if (node.RightChild == null) {node = node.leftchild; } else if (node.leftchild == null) {node = node.Rightchild; } else {// Si les sous-arbres gauche et droit des nœuds supprimés ont temp = node.leftchild; pre = nœud; while (temp.RightChild! = null) {pre = temp; temp = temp.RightChild; // Voyagez pour trouver le nœud le plus à droite du sous-arbre gauche} node.data = temp.data; // Effectuez l'opération d'affectation if (pre == node) {pre.leftchild = node.leftchild; } else {pre.RightChild = node.RightChild; }} temp = null; }}Classe de test
package SearchBinaryTree; public class SearchBinaryTreetSeT {public static void main (String [] args) {searchBinaryTree <Integer> Tree = new SearchBinaryTree <Integer> (); pour (int i = 1; i <10; i ++) {arbre.createTree (new SearchBinaryTeenode <Integer> (), i); } // Search Tree.Search (Tree.root, 7); // Merge et supprimer Tree.DeleteByMerging (new SearchBinaryTreenode <Integer> (8)); // Copier et supprimer Tree.DeleteByCoping (new SearchBinaryTreenode <Integer> (6)); }}Ok, c'est ça!
L'article ci-dessus Java crée un arbre de recherche binaire et implémente les exemples de recherche, d'insertion et de suppression sont tout le contenu que je partage avec vous. J'espère que vous pourrez vous faire référence et j'espère que vous pourrez soutenir Wulin.com plus.