J'ai créé une arborescence de recherche binaire de compteur de mots qui incrémente le compte d'un mot lorsqu'il est saisi plusieurs fois. Le mot et le nombre de mots sont enregistrés dans l'arborescence. J'essaie d'imprimer d'abord le nombre de mots le plus élevé et de descendre dans l'ordre décroissant.
J'ai converti le BST en ArrayList pour ce faire, mais maintenant je n'arrive pas à comprendre comment trier la liste en diminuant ordre de comptage. Voici ce que j'ai jusqu'à présent:
public ArrayList<String> toArray() {
ArrayList<String> result = new ArrayList<String>();
toArrayHelp(root, result);
Collections.sort(result);
return result;
}
private void toArrayHelp(Node<String, Integer> node, ArrayList<String> result) {
if (node == null) {
return;
}
toArrayHelp(node.left, result);
result.add("count: " + String.valueOf(node.count) + "/t word: " + node.data);
toArrayHelp(node.right, result);
}
J'ai essayé Collections.sort () mais je ne le trie pas par chaîne, uniquement par mot.
p>
4 Réponses :
List > à partir de tous les éléments List en triant la partie int des nœuds Vous construisez la chaîne de sortie trop tôt: vous devez d'abord trier la liste en utilisant le décompte comme clé, puis imprimer les résultats. Vous pouvez créer un simple wrapper qui contiendra le résultat:
public class WordCount implements Comparable<WordCount>{
private String word;
private Integer count;
//constructors, getters, setters etc..
@Override
public int compareTo(WordCount other) {
return Integer.compare(this.count, other.count);
}
}
et construire une List pendant que vous parcourez l'arborescence. Une fois que vous avez terminé, il vous suffit de trier la liste par Collections.sort (liste) et d'imprimer les résultats.
1 Pour l'ordre DESC, utilisez Collections.sort (result, Collections.reverseOrder ()); car l'ordre de tri par défaut est ASC.
2.Assurez-vous que la représentation sous forme de chaîne de count a la même longueur. Sinon, l'ordre lexicographique suppose 11
List<String> list = Arrays.asList("11", "01", "02");
Collections.sort(list, Collections.reverseOrder());
System.out.println(list); // output: [11, 02, 01]
Mais si les nombres ont la même longueur fonctionne bien:
List<String> list = Arrays.asList("11", "1", "2");
Collections.sort(list, Collections.reverseOrder());
System.out.println(list); // output: [2, 11, 1]
Comment pour ajouter des zéros non significatifs, vous pouvez trouver ici https://stackoverflow.com/a/275715/4671833 .
Doit être quelque chose comme ceci result.add ("count:" + String.format ("% 02d", String.valueOf (node.count)) + "/ t mot:" + node.data); code>
Deux brefs points: laissez la sélection de nom et le formatage être vos amis! Vous voudrez prendre l'habitude de choisir des noms de variables simples et expressifs, et de garder votre code soigneusement formaté.
Commençons par mettre cela en étapes claires:
(1) Il y a une source de données de mot, exprimées sous forme d'arbre de nœuds. En évitant trop de détails, définissons les détails importants du type de nœud et ayons l'arborescence de nœuds disponible à l'aide d'un getter.
Un détail important à mentionner est que les nœuds sont destinés à être conservés dans un binaire trié arbre qui a des valeurs de clé distinctes, et pour lequel la valeur de tout nœud gauche est strictement inférieure à la valeur du nœud, et la valeur de tout nœud droit est strictement supérieure à la valeur du nœud. Cela a une conséquence importante qui est que les valeurs du sous-arbre gauche d'un nœud sont toutes strictement inférieures à la valeur du nœud, et les valeurs du sous-arbre droit sont de même toutes strictement supérieures à la valeur du nœud .
public void sort(List<Node<String, Integer>> nodes) {
Collections.sort(
nodes,
((Node<String, Integer> n1, Node<String, Integer> n2) -> Integer.compare(n1.value, n2.value)) );
}
public static final Comparator<Node<String, Integer>> NODE_COMPARATOR =
new Comparator<Node<String, Integer>>() {
public int compare(Node<String, Integer> n1, Node<String, Integer> n2) {
return Integer.compare(n1.value, n2.value);
}
};
public void sort(List<Node<String, Integer>> nodes) {
Collections.sort(nodes, NODE_COMPARATOR);
}
(2) Trois opérations principales sont nécessaires: une opération pour rassembler les nœuds de l'arborescence dans une liste, une opération pour trier cette liste, et un opération pour afficher la liste triée:
public List<Node<String, Integer>> flatten(Node<String, Integer> rootNode) {
List<Node<String, Integer>> flatNodes = new ArrayList<Node<String, Integer>>();
if ( rootNode != null ) {
flatten(rootNode, flatNodes);
}
return flatNodes;
}
public void flatten(Node<String, Integer> node, List<Node<String, Integer>> flatNodes) {
Node<String, Integer> leftNode = node.left;
if ( leftNode != null ) {
flatten(leftNode, flatNodes);
}
flatNodes.add(node);
Node<String, Integer> rightNode = node.right;
if ( rightNode != null ) {
flatten(rightNode, flatNodes);
}
}
(3) Cela s'emboîte, par exemple, comme suit:
public List<Node<String, Integer>> flatten(Node<String, Integer> rootNode) {
List<Node<String, Integer>> flatNodes = new ArrayList<Node<String, Integer>>();
flatten(rootNode, flatNodes);
return flatNodes;
}
public void flatten(Node<String, Integer> node, List<Node<String, Integer>> flatNodes) {
if ( node == null ) {
return;
}
flatten(node.left, flatNodes);
flatNodes.add(node);
flatten(node.right, flatNodes);
}
(4) Il reste à détailler les différentes méthodes. Nous commençons par «aplatir». Cela sera implémenté comme une opération récursive. Et, comme le passage du stockage pour la liste plate est plus simple, la méthode sera divisée en deux parties, l'une qui alloue le stockage et l'autre qui effectue le traitement récursif. Cette technique de transmission d'une collection de stockage est typique de ce type de traitement.
'flatten' utilise la propriété de classement d'un nœud par rapport au nœud gauche du nœud et au nœud droit du nœud: 'flatten 'ajoute toutes les valeurs du sous-arbre de gauche à la liste des nœuds plats, suivi du nœud, suivi de toutes les valeurs du sous-arbre de droite.
public void tester() {
Node<String, Integer> rootNode = getRootNode();
List<Node<String, Integer>> flatNodes = flatten(rootNode);
sort(flatNodes);
print(flatNodes)l
}
(5) Pour plus de clarté, cela peut être rendu un peu plus efficace en déplaçant les vérifications nulles. Pour un arbre entièrement équilibré, cela évitera environ 2/3 des appels récursifs, ce qui est une assez bonne réduction. Cela n'a d'importance que si le nombre de nœuds est élevé. Et un bon compilateur convertira probablement le code de cette façon de toute façon.
public List<Node<String, Integer>> flatten(Node<String, Integer> rootNode) {
// Undetailed ...
}
public void sort(List<Node<String, Integer>> nodes) {
// Undetailed ...
}
public void print(List<Node<String, Integer>> nodes) {
// Undetailed ...
}
(6) Le bit suivant est de trier la liste des nœuds plats. Deux implémentations sont présentées, une plus moderne qui utilise des lambdas et une plus ancienne qui utilise un comparateur explicite. Les comparaisons sont écrites pour générer une liste triée du plus petit au plus grand. Pour inverser l'ordre de tri, échangez l'ordre de comparaison.
public class Node<K, V> {
public K key;
public V value;
public Node<K, V> left;
public Node<K, V> right;
public Node(K key, V value) {
this.key = key;
this.value = value;
}
}
public Node<String, Integer> getRootNode() {
// Undetailed ...
}
(7) L'impression de la liste triée résultante est laissée à titre d'exercice.
Vous pouvez implémenter votre propre comparateur pour comparer les valeurs de
countCe message devrait aider dzone.com/articles/sorting-java-arraylist
Vous ne vous rendez pas service lorsque vous convertissez les données traitables en chaîne, puis essayez de trier le résultat, ce qui nécessiterait d’analyser les chaînes. Collectez dans un tableau de
Node, triez-les par leur nombre et convertissez la liste triée en une liste deStringà la place.