логическая проблема в Tr ie вставке или операции чтения - PullRequest
Новая
       42

логическая проблема в Tr ie вставке или операции чтения

3 голосов
/ 01 августа 2020

Я пытаюсь выполнить операцию вставки в Tr ie и операцию чтения для приведенной ниже реализации. У меня возникли проблемы со вставкой. Не думаю, что есть какие-то проблемы с операцией чтения. В моем случае каждый узел Tr ie имеет массив указателей узлов и поле значения. Кроме того, я отмечаю каждую вставку символа, теоретически каждый узел имеет символ верхнего регистра и целочисленное значение. Например: скажем, должны быть добавлены 3 строки: ATAGA , AT C и 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

Ответы [ 2 ]

2 голосов
/ 01 августа 2020

Я протестировал изменения и вижу ожидаемый результат, как вы упомянули.

Вы должны обновить дочерние узлы 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;
          }
}

Аналогичным образом во время поиска / посещения получить значение из дочернего узла текущего узла. 

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]);
          }
}
1 голос
/ 01 августа 2020

В этих строках: 

trv.val = ++pass;
System.out.println((char)(i+'A')+" : "+trv.val);

вы должны использовать trv.ptrs[s.charAt(i) - 'A'].val вместо trv.val

, т.е. вы хотите получить / установить значение дочернего узла, а не родитель.

...