https://stackoverflow.com/questions/2225540
-
19-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
3 개의 작업을 지원하는 Java에서 매우 간단한 트리를 구현하려고합니다. 삽입 메소드, a는 메소드가 있고 (예 : 트리의 특정 단어), 트리를 문자열 형식으로 되돌릴 수있는 토스트 링 메소드가 있습니다. 나는 삽입이 제대로 작동한다고 생각하지만 Tostring은 어려운 것으로 판명되었습니다. 지금까지 내가 가진 것이 있습니다.
트리 클래스.
public class CaseInsensitiveTrie implements SimpleTrie {
//root node
private TrieNode r;
public CaseInsensitiveTrie() {
r = new TrieNode();
}
public boolean has(String word) throws InvalidArgumentUosException {
return r.has(word);
}
public void insert(String word) throws InvalidArgumentUosException {
r.insert(word);
}
public String toString() {
return r.toString();
}
public static void main(String[] args) {
CaseInsensitiveTrie t = new CaseInsensitiveTrie();
System.out.println("Testing some strings");
t.insert("TEST");
t.insert("TATTER");
System.out.println(t.has("TEST"));
}
}
그리고 노드 클래스
public class TrieNode {
//make child nodes
private TrieNode[] c;
//flag for end of word
private boolean flag = false;
public TrieNode() {
c = new TrieNode[26]; //1 for each letter in alphabet
}
protected void insert(String word) {
int val = word.charAt(0) - 64;
//if the value of the child node at val is null, make a new node
//there to represent the letter
if (c[val] == null) {
c[val] = new TrieNode();
}
//if word length > 1, then word is not finished being added.
//otherwise, set the flag to true so we know a word ends there.
if (word.length() > 1) {
c[val].insert(word.substring(1));
} else {
c[val].flag = true;
}
}
public boolean has(String word) {
int val = word.charAt(0) - 64;
if (c[val]!=null && word.length()>1) {
c[val].has(word.substring(1));
} else if (c[val].flag==true && word.length()==1) {
return true;
}
return false;
}
public String toString() {
return "";
}
}
따라서 기본적으로 트리를 만들 때 Trienode는 26 명의 어린이가있는 뿌리로 만들어집니다. 인서트를 시도하면 해당 루트 노드에서 인서트가 호출되어 올바른 위치에서 새 노드를 재귀 적으로 생성하고 단어가 완료 될 때까지 계속됩니다. 그 방법이 제대로 작동한다고 생각합니다.
내 기능은 매우 깨졌습니다 가지다 어떤 이유로 괄호 밖에서 그 반환 진술을받는 것입니다. 다른 조항에 포함 할 수 없거나 컴파일러가 불만을 제기 할 수 없습니다. 그 외에는 그 방법이 약간의 조정으로 작동해야한다고 생각하지만, 나는 내 삶에 대해서는 그것을 알아낼 수 없습니다.
Tostring은 내가 다루려고 시도한 짐승이지만, 내가 던지는 것은 아무것도 작동하지 않으므로 문제를 해결할 때까지 떠날 것입니다. 내가 작동한다면 그것을 tostring 함수로 재구성하는 방법을 알아낼 수 있습니다.
int val = Word.charat (0) -64의 목적; 입력 한 각 문자열은 모든 캡이어야하기 때문에 (나중에이를 보장하기 위해 문자열 형식 함수를 생성 할 것입니다) 첫 번째 문자의 int 값 -64는 배열의 위치가 될 것입니다. IE Array Index 0은 a이므로 a = 64, a -64 = 0입니다. b = 65, b -64 = 1 등.
해결책
당신의 has 함수는 아마도 다음과 같아야합니다.
if (c[val]!=null && word.length()>1) {
return c[val].has(word.substring(1)); //<-- Change is on this line
} else if (c[val].flag==true && word.length()==1) {
...etc
재귀 호출을 수행하지만 그 값을 원래 발신자에게 전파하도록해야합니다.
다른 팁
어쩌면 "trienode [] c"대신 "Map C"를 사용할 수 있습니다. 따라서 모든 유형의 문자 대문자/소문자 및 특수 문자에도 사용할 수 있으며 공간을 절약 할 수 있습니다 (26 자 배열을 할당 할 수도 있습니다. 각 캐릭터 레벨)
내 구현은 다음과 같습니다. -
public class Tries {
class Node {
HashMap<Character, Node> children;
boolean end;
public Node(boolean b){
children = new HashMap<Character, Tries.Node>();
end = false;
}
}
private Node root;
public Tries(){
root = new Node(false);
}
public static void main(String args[]){
Tries tr = new Tries();
tr.add("dog");
tr.add("doggy");
System.out.println(tr.search("dogg"));
System.out.println(tr.search("doggy"));
}
private boolean search(String word) {
Node crawl = root;
int n = word.length();
for(int i=0;i<n;i++){
char ch = word.charAt(i);
if(crawl.children.get(ch) == null){
return false;
}
else {
crawl = crawl.children.get(ch);
if(i==n-1 && crawl.end == true){
return true;
}
}
}
return false;
}
private void add(String word) {
Node crawl = root;
int n = word.length();
for(int i=0;i<n;i++){
char ch = word.charAt(i);
if(crawl.children.containsKey(ch)){
crawl = crawl.children.get(ch);
}
else {
crawl.children.put(ch, new Node(false));
Node temp = crawl.children.get(ch);
if(i == n-1){
temp.end = true;
}
crawl = temp;
System.out.println(ch + " " + crawl.end);
}
}
}
}
여기 내 구현 :
public class Tries {
private static class Leaf {
private Leaf(char c) {
this.c=c;
}
char c;
int counter = 1;
List<Leaf> leaves = new ArrayList<>(10);
}
private Leaf root = new Leaf('0');
public void add(String word) {
Leaf current = root;
Leaf newLeaf = null;
for (char c : word.toCharArray()) {
boolean found = false;
for (Leaf leaf : current.leaves) {
if (leaf.c == c) {
current = leaf;
current.counter++;
found=true;
break;
}
}
if (!found) {
newLeaf = new Leaf(c);
current.leaves.add(newLeaf);
current = newLeaf;
}
}
}
public int find(String partial) {
Leaf current = root;
for (char c : partial.toCharArray()) {
boolean found = false;
for (Leaf leaf : current.leaves) {
if (leaf.c == c) {
current=leaf;
found=true;
break;
}
}
if(!found) return 0;
}
return current.counter;
}
public boolean hasWord(String partial) {
return find(partial)>0;
}
}
다음은 다른 데이터 구조를 사용하지 않고 간단한 Java 구현입니다.
import java.util.ArrayList;
import java.util.List;
class Trie {
private static Node root = new Node(' ', false);
static int getIndex(char x) {
return ((int) x) - ((int) 'a');
}
static class Node {
char data;
boolean isLeaf;
Node[] children;
Node(char data, boolean leaf) {
this.data = data;
this.isLeaf = leaf;
this.children = new Node[26];
}
}
static void insert(String data, Node root) {
if (data == null || data.length() == 0) {
return;
}
Node child = root.children[getIndex(data.charAt(0))];
if (child == null) {
Node node = new Node(data.charAt(0), data.length() == 1);
root.children[getIndex(data.charAt(0))] = node;
if (data.length() > 1) {
insert(data.substring(1, data.length()), node);
}
} else {
if (data.length() == 1) {
child.isLeaf = true;
} else {
insert(data.substring(1, data.length()), child);
}
}
}
static boolean find(String data, Node root) {
if (data == null || data.length() == 0) {
return true;
}
char x = data.charAt(0);
//note that first node ie root is just dummy, it just holds important
Node node = root.children[getIndex(x)];
if (node == null) {
return false;
} else {
if (data.length() == 1) {
return node.isLeaf;
} else {
return find(data.substring(1, data.length()), node);
}
}
}
static boolean delete(String data, Node root) {
if (data == null || data.length() == 0) {
return false;
}
char x = data.charAt(0);
//note that first node ie root is just dummy, it just holds important
Node node = root.children[getIndex(x)];
if (node == null) {
return false;
} else {
if (data.length() == 1) {
node.isLeaf = false;
boolean allNull = true;
for (Node node1 : node.children) {
allNull = allNull && node1 == null;
}
return allNull;
} else {
boolean delete = delete(data.substring(1, data.length()), node);
if (delete) {
node.children[getIndex(x)] = null;
if(node.isLeaf){
return false;
}
boolean allNull = true;
for (Node node1 : node.children) {
allNull = allNull && node1 == null;
}
return allNull; }
}
}
return false;
}
private static List<String> strings = new ArrayList<>();
private static List<String> getAll() {
strings = new ArrayList<String>();
findAllDFS(root, "");
return strings;
}
private static void findAllDFS(Node node, String old) {
if (node != null) {
if (node.data != ' ') {
old = old + node.data;
}
if (node.isLeaf) {
strings.add(old);
}
for (Node node1 : node.children) {
findAllDFS(node1, old);
}
}
}
public static void main(String[] args) {
insert("abc", root);
insert("xyz", root);
insert("abcd", root);
insert("abcde", root);
delete("abcd", root);
/* System.out.println(find("abc", root));
System.out.println(find("abcd", root));
System.out.println(find("ab", root));
System.out.println(find("xyz", root));*/
System.out.println(getAll());
}
}
제휴하지 않습니다 StackOverflow
