Implémentation Java de tri-tree

Implémentation Java de tri-tree

Qu'est-ce qu'un arbre d'essai?

Untitled Diagram.png

Un tri-arbre est une sorte d'arbre ordonné, et c'est un algorithme dans lequel les caractères sont stockés dans chaque nœud et une recherche peut être effectuée en traçant les nœuds.

Ecrire en Java

Créer une classe qui représente un nœud

public class Node {
	private int id;
	private String str;
	private ArrayList<Node> child = new ArrayList<>();
	public int getId() {
		return this.id;
	}
	public String getStr() {
		return this.str;
	}
	public ArrayList<Node> getChild(){
		return this.child;
	}
	public void setId(int id) {
		this.id = id;
	}
	public void setStr(String str) {
		this.str = str;
	}
	public void setChild(Node node) {
		this.child.add(node);
	}
}

L'identifiant identifie le nœud et n'a pas à être séparé str est le caractère à stocker dans le nœud child est censé stocker l'enfant du nœud

L'arbre peut être construit comme suit

public class Main {
	private static ArrayList<Node> nodeList = new ArrayList<>();
	private static int id = 1;
	public static void insert(Node parent, String word, int charIndex) {
		String w = String.valueOf(word.charAt(charIndex));
		//System.out.println(w);
		if(charIndex == word.length()-1) { //Pour le dernier personnage
			for(Node n:parent.getChild()) { //Si le dernier nœud est un nœud existant
				if(n.getStr() != null&&n.getStr().equals(w)) {
					return;
				}
			}
			Node node = new Node();
			node.setStr(w);
			parent.setChild(node);
			node.setChild(node);
			node.setId(id);
			id += 1;
			nodeList.add(node);
			return;
		}
		for(Node n:parent.getChild()) { //Si l'enfant contient le service actuel
			if(n.getStr() != null&&n.getStr().equals(w)) {
				insert(n,word,charIndex+1);
				return;
			}
		}
		Node node = new Node();
	        node.setStr(w);
		parent.setChild(node);
		node.setId(id);
		id += 1;
		nodeList.add(node);
		if(charIndex < word.length()-1) { //Traitement récursif
		     insert(node, word, charIndex+1);
		}
	}

Je suis désolé si j'ai fait une erreur car c'était une réécriture de l'article que j'ai écrit quand je faisais un autre algorithme en concevant un petit tri-arbre (_ _)

Résumé

Cette fois, j'ai eu la chance d'utiliser un tri-arbre, donc j'ai essayé de l'implémenter avec java, mais cela a pris du temps à comprendre car il utilise un traitement récursif. Après tout, je ne suis pas doué pour le traitement récursif, je veux donc l'utiliser activement pour éliminer ma faiblesse ...

Recommended Posts

Implémentation Java de tri-tree
Implémentation d'une fonction similaire en Java
Implémentation de l'interpréteur par Java
Implémentation Boyer-Moore en Java
Implémentation du tri de tas (en java)
[Java] Implémentation du réseau Faistel
Implémentation de HashMap avec kotlin
Implémentation du traitement asynchrone dans Tomcat
Liste des types ajoutés dans Java 9
Obtenez le résultat de POST en Java
Créons une application TODO en Java 4 Implémentation de la fonction de publication
Partition en Java
Implémentation du traitement asynchrone compatible multi-tenant dans Tomcat
Créons une application TODO en Java 6 Implémentation de la fonction de recherche
Changements dans Java 11
Créons une application TODO en Java 8 Implémentation des fonctions d'édition
Janken à Java
Mécanisme et caractéristiques de la classe d'implémentation Collection souvent utilisés en Java
L'histoire de l'écriture de Java dans Emacs
Taux circonférentiel à Java
[Java] Présentation de Java
Rôle de JSP dans les applications Web [Java]
FizzBuzz en Java
Discrimination d'énum dans Java 7 et supérieur
Ceci et cela de la mise en œuvre du jugement en temps réel des dates en Java
Comparaison des méthodes d'implémentation de thread en Java et de la méthode d'expression lambda
L'histoire de la comparaison de chaînes de bas niveau en Java
[Java] Gestion des Java Beans dans la chaîne de méthodes
L'histoire de la fabrication d'un Othello ordinaire à Java
À propos de l'idée des classes anonymes en Java
Implémentation du regroupement de chiffres dans l'application Furima
L'histoire de l'apprentissage de Java dans la première programmation
Mesurer la taille d'un dossier avec Java
[Java] Utilisation de final dans la déclaration de variable locale
Ressentez le passage du temps même à Java
[Rails] Mise en œuvre de "notifier la notification d'une manière ou d'une autre"
Nom de méthode de la chaîne de méthodes dans Java Builder + α
Importer des fichiers de la même hiérarchie en Java
Collection expirée de java
Caractéristiques prévues de Java
Faites un blackjack avec Java
Application Janken en Java
Programmation par contraintes en Java
Mettez java8 dans centos7
NVL-ish guy en Java
"Hello World" en Java
Vérifier l'implémentation de Java toString ()
Interface appelable en Java
NIO.2 examen de Java
Commentaires dans la source Java
Fonctions Azure en Java