0

これを実装するのに問題があります。部分文字列のインデックスを与える最も深いパスを見つけるために、深さ優先検索を行う必要があることはわかっています。dfs の実装に問題があり、おそらく私の理解が不十分です。

int getDeepestPath(TreeNode node)
{
    int maxDistance = 0;
    TreeNode maxNode;
    if(node == null) return 0;
    System.out.println(node.getSuffix());
    if(node.getSuffix() != -1) return 0;  
    else
    {
        TreeNode nextNode = node.getChild();
        while(true)
        {
            int distance = 0;
            if(nextNode != null)
            {
                distance = (nextNode.getRightLabel() -nextNode.getLeftLabel()) + 1;
                System.out.println(distance + " distance");
                distance = getDeepestPath(nextNode,t2Info) + distance;
                if(distance > maxDistance) maxDistance = distance;
                nextNode = nextNode.getSibling();
            }
            else break;
        }
    }

    System.out.println(maxDistance);
    return maxDistance;
}

最終的な目的は、最も深いノードとパスの長さを保存することです。現時点では、パスの長さを出力しようとしています。

ありがとう

4

2 に答える 2

0

nodeスタックを使用して DFS を実装し、変数をcalledに追加してみませんかvisited。ノードをスタックにプッシュするたびに、 をマークしvisited = trueます。疑似コード

root.visited = true;
root.push()
while(Stack.isEmpty()) {
  if(!root.next.visited) {
    root.next.push()
  }
}

葉を見つけ、次の分岐に進み、ポップするためのロジックを実装します。これは一般的なロジックです。バイナリ ツリーがある場合は、これを変更して、2 つの子 (左と右) だけをより単純にすることができます。

于 2013-02-14T20:05:49.237 に答える
0

あなたの仮定は間違っています。

サフィックス ツリーでは、各ノードに、そのノードで終了する文字列のキーのリストが含まれている必要があります。リストが空の場合、そのノードによって文字列は定義されていません。ツリーで長いパスを見つける必要はありません。たとえば、ツリーに "app" (1)、"apple" (2) と (5)、"apple pie" (3) の 3 つの文字列がある場合、ツリーは次のようになります。

"app" 1  
  |  
"le" 2, 5  
  |  
" pie" 3
于 2013-02-14T21:56:34.330 に答える