Trie 插入或读取操作中的逻辑问题
logical problem in Trie insertion or a read operation
我正在尝试 Trie 中的插入操作和以下实现的读取操作我在插入时遇到了问题。我认为读取操作没有任何问题。在我的例子中,Trie 的每个节点都有一个节点指针数组和一个值字段。另外,我在理论上标记每个字符插入,每个节点都有大写字符和一个整数值。例如:假设要添加 3 个字符串,如 ATAGA、ATC 和 GAT,因此每个字符的值将由代码中的“pass”变量给出,有关详细信息,请参阅预期输出。
import java.util.*;
class node{
public int val;
public node ptrs[];
node(){
this.val =0;
ptrs = new node[26];
for (node ptr : ptrs) {
ptr = null;
}
}
}
class Tree{
public node root = new node();
public int pass =0;
void insert(String s) {
node trv = root;
for (int i = 0; i < s.length(); i++) {
if (trv.ptrs[s.charAt(i) - 'A'] == null) {
trv.ptrs[s.charAt(i) - 'A'] = new node();
trv.val = ++pass;
// System.out.println(s.charAt(i)+" val : "+trv.val);
}
trv = trv.ptrs[s.charAt(i) - 'A'];
}
}
private void visit(node trv){
for(int i =0;i<26;i++){
if(trv.ptrs[i]!=null){
System.out.println((char)(i+'A')+" : "+trv.val);
visit(trv.ptrs[i]);
}
}
}
void call(){
this.visit(root);
}
}
public class trie {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
Tree t = new Tree();
while (n-- > 0) {
String s = sc.next();
t.insert(s);
}
t.call();
sc.close();
}
}
我的输出:
3
ATAGA
ATC
GAT
A : 7
T : 2
A : 6
G : 4
A : 5
C : 6
G : 7
A : 8
T : 9
预期输出:
3
ATAGA
ATC
GAT
A : 1
T : 2
A : 3
G : 4
A : 5
C : 6
G : 7
A : 8
T : 9
在这些行中:
trv.val = ++pass;
System.out.println((char)(i+'A')+" : "+trv.val);
你应该使用 trv.ptrs[s.charAt(i) - 'A'].val
而不是 trv.val
即您想要 get/set 子节点的值,而不是父节点。
我已经测试了更改,我可以看到您提到的预期输出。
您必须在插入期间更新子节点 val 和 ptrs 数组而不是父节点。
for (int i = 0; i < s.length(); i++)
{
if (trv.ptrs[s.charAt(i) - 'A'] == null)
{
trv.ptrs[s.charAt(i) - 'A'] = new node();
trv.ptrs[s.charAt(i) - 'A'].val = ++pass;
}
}
与search/visit类似,从当前节点的子节点取值
for(int i=0;i<26;i++)
{
if(trv.ptrs[i]!=null)
{
System.out.println((char)(i+'A')+" : "+trv.ptrs[i].val);
visit(trv.ptrs[i]);
}
}
我正在尝试 Trie 中的插入操作和以下实现的读取操作我在插入时遇到了问题。我认为读取操作没有任何问题。在我的例子中,Trie 的每个节点都有一个节点指针数组和一个值字段。另外,我在理论上标记每个字符插入,每个节点都有大写字符和一个整数值。例如:假设要添加 3 个字符串,如 ATAGA、ATC 和 GAT,因此每个字符的值将由代码中的“pass”变量给出,有关详细信息,请参阅预期输出。
import java.util.*;
class node{
public int val;
public node ptrs[];
node(){
this.val =0;
ptrs = new node[26];
for (node ptr : ptrs) {
ptr = null;
}
}
}
class Tree{
public node root = new node();
public int pass =0;
void insert(String s) {
node trv = root;
for (int i = 0; i < s.length(); i++) {
if (trv.ptrs[s.charAt(i) - 'A'] == null) {
trv.ptrs[s.charAt(i) - 'A'] = new node();
trv.val = ++pass;
// System.out.println(s.charAt(i)+" val : "+trv.val);
}
trv = trv.ptrs[s.charAt(i) - 'A'];
}
}
private void visit(node trv){
for(int i =0;i<26;i++){
if(trv.ptrs[i]!=null){
System.out.println((char)(i+'A')+" : "+trv.val);
visit(trv.ptrs[i]);
}
}
}
void call(){
this.visit(root);
}
}
public class trie {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
Tree t = new Tree();
while (n-- > 0) {
String s = sc.next();
t.insert(s);
}
t.call();
sc.close();
}
}
我的输出:
3
ATAGA
ATC
GAT
A : 7
T : 2
A : 6
G : 4
A : 5
C : 6
G : 7
A : 8
T : 9
预期输出:
3
ATAGA
ATC
GAT
A : 1
T : 2
A : 3
G : 4
A : 5
C : 6
G : 7
A : 8
T : 9
在这些行中:
trv.val = ++pass;
System.out.println((char)(i+'A')+" : "+trv.val);
你应该使用 trv.ptrs[s.charAt(i) - 'A'].val
而不是 trv.val
即您想要 get/set 子节点的值,而不是父节点。
我已经测试了更改,我可以看到您提到的预期输出。
您必须在插入期间更新子节点 val 和 ptrs 数组而不是父节点。
for (int i = 0; i < s.length(); i++)
{
if (trv.ptrs[s.charAt(i) - 'A'] == null)
{
trv.ptrs[s.charAt(i) - 'A'] = new node();
trv.ptrs[s.charAt(i) - 'A'].val = ++pass;
}
}
与search/visit类似,从当前节点的子节点取值
for(int i=0;i<26;i++)
{
if(trv.ptrs[i]!=null)
{
System.out.println((char)(i+'A')+" : "+trv.ptrs[i].val);
visit(trv.ptrs[i]);
}
}