2

トライの実装があり、トライを印刷して、その内容を確認したいと考えています。単語が実際に意味をなすように、深さ優先のトラバーサルが望ましいです。これが私のコードです：

package trie;

public class Trie {
    public TrieNode root;

    public Trie(){
        root = new TrieNode();
    }

    /*
    public Trie(char c){
        TrieNode t = new TrieNode(c);
        root = t;
    }*/

    public void insert(String s, int phraseNb){
        int i = 0;
        TrieNode node = root;
        char[] string = s.toCharArray();
        TrieNode child = null;

        while(i < string.length){
            child = node.getChild(string[i]);
            if(child == null){
                child = new TrieNode(string[i]);
                node.addChild(child);
            }
            else{
                node = child;
            }
            i++;
        }

        node.endOfWord();
        node.setNb(phraseNb);
    }

    public int[] search(char[] c){
        TrieNode node = root;
        for(int i = 0; i < c.length-1; i++){
            node = root;
            int s = 0;
            while(i+s < c.length){
                TrieNode child = node.getChild(c[i + s]);
                if(child == null){
                    break;
                }
                if(child.isWord()){
                    return new int[] {i, s+1, node.getNb()};
                }
                node = child;
                s++;
            }
        }
        return new int[] {-1, -1, -1};
    }

    public void print(){

    }
}

package trie;

import java.io.*;
import java.util.*;

public class TrieNode {
    private boolean endOfWord;
    private int phraseNb;
    private char letter;
    private HashSet<TrieNode> children = new HashSet<TrieNode>();

    public TrieNode(){}

    public TrieNode(char letter){
        this.letter = letter;
    }

    public boolean isWord(){
        return endOfWord;
    }

    public void setNb(int nb){
        phraseNb = nb;
    }

    public int getNb(){
        return phraseNb;
    }

    public char getLetter(){
        return letter;
    }

    public TrieNode getChild(char c){
        for(TrieNode child: children){
            if(c == child.getLetter()){
                return child;
            }
        }
        return null;
    }

    public Set<TrieNode> getChildren(){
        return children;
    }

    public boolean addChild(TrieNode t){
        return children.add(t);
    }

    public void endOfWord(){
        endOfWord = true;
    }

    public void notEndOfWord(){
        endOfWord = false;
    }
}

それを行う方法についての説明またはいくつかの擬似コードが必要です。御時間ありがとうございます。

4

5 に答える 5

1

コンソールでツリーを印刷しようとした大学時代を思い出します。Trie は、IMO を印刷するという点では同じです... これは私がしたことであり、これも私があなたに提案することです。ここで、トライをどのように印刷するかを考えます。trie は N-tree (バイナリではなく、たくさんの子を持つツリー) のように構成されていると思います。それに加えて、ツリーのような再帰的な構造です。したがって、ここで深さ優先アプローチを実際に適用できます。

次のようなトライを出力するとします (ノード 'a' はルートです)。

a

  b

     e

     f

     g
  d

これは単語を含むトライのようなものです: ad abe abf abg

したがって、ルートから始めて、オフセットを蓄積し、再帰的にトラバースします。

printTrie(Node node, int offset) {
     print(node, offset)
     // here you can play with the order of the children
     for(Node child : node.getChildren()) {
          printTrie(child, offset + 2)
     } 
}

次のコマンドで再帰を開始します。

printTrie(root, 0)

そして、あなたは終わります

定数として 2 を使用して、オフセット変更係数を操作し、それを 3,4 などに変更して、何が起こるかを確認しました。

お役に立てれば。幸運を！

于 2012-07-29T07:59:22.493 に答える
0

これは役立つかもしれません。

public void printTrie(TrieNode node,String s) {
    String strSoFar = s;
    strSoFar += String.valueOf(node.c);
    if(node.isLeaf)
    {
        System.out.println(strSoFar);
        return;
    }
    else
    {
        Stack<TrieNode> stack = new Stack<TrieNode>();
        Iterator<TrieNode> itr = node.children.values().iterator();
        while(itr.hasNext())
        {
            stack.add(itr.next());
        }
        while(!stack.empty()){
            TrieNode t = stack.pop();
            printTrie(t,strSoFar);
        }

    }
}

関数を呼び出してみてください。

trieObject.printTrie(trieObject.getRoot(), "");
于 2017-06-14T10:02:17.167 に答える
0

ビジターデザイン パターンは、Trie のような複合データ構造を扱う場合に役立ちます。これにより、開発者は、複合データ構造のトラバーサルを各ノードで取得した情報から切り離すことができます。

ビジター デザイン パターンを使用してトライを印刷できます。

于 2012-07-29T08:44:32.000 に答える