0

バイナリツリーの特定のノードまでのパスを再帰的に表示しようとしています。このメソッドは、「左、右、左」の方法で必要なパスを出力します。これが私がこれまでに持っているものです：

public static void pathToNode(BTNode p, char target, String res){
    if(p.data == target){
        res = res + p.data;
        System.out.println(res);
        return;
    }else if(res != null){
        if(res.charAt(0) == 'S'){
        res = res + p.data;
        }
    }else{
        pathToNode(p.leftLink, target, res);
        pathToNode(p.leftLink, target, res);
    }

}

このコードは、「ABCD」のようにパスを出力することを目的としています。これを行った後、各ノードトラバーサルの正しいオプションに基づいて、メソッドを左右どちらかに出力する予定です。何か案は？

4

3 に答える 3

1

あなたのコードは私には少し不明瞭です。'S'はルートペイロードであると想定されていますか？また、実際には、よりわかりやすい変数名を使用するようにしてください。

public static String pathToNode(BTNode p, char target) {
    // termination rules
    if (p.data == target) {
       // success
       return p.data;       
    }
    // failure: p is not the target AND is a leaf.
    if (p.leftLink == null && p.rightLink == null) return null;

    // recursion: if p is in the subtree, this will find it.
    return (pathToNode(p.leftLink, target) == null) ? (p.data + pathToNode(p.rightLink), target) : (p.data + pathToNode(p.leftLink, target));

}

編集：もちろん、nullターゲットがツリーにない場合、これは結局戻る可能性があります。また、実際にパスを印刷するのを忘れました。今そこにあります。

于 2012-11-16T10:23:21.220 に答える
0

ルートからパスを見つけようとしていると思います。また、ツリーにはターゲットへのパスが1つしかないことを前提としています。つまり、同じ要素をツリーの異なる場所に配置することはできません。

このコードは機能しますが、

public static void pathToNode(BTNode p, char target, String res){
    if(p.data == target){
        res += p.data;
        System.out.println(res);
        return;
    }
    else{
        if(res==null){
           res="";
        }
        res += p.data;
        pathToNode(p.leftLink, target, res);
        pathToNode(p.rightLink, target, res);
    }
}

しかし、これは非常に非効率的で、メモリコストのかかるソリューションになります。良い解決策を得るには、ツリートラバーサルの詳細をお読みください。

于 2012-11-16T10:17:49.143 に答える
0

最初のif句で探しているターゲットが見つかったら、結果を出力します。または、ツリーの左と右の両方のブランチを試す必要があります。これは、最後の句で行っていることです（ほとんどの場合、左から2つ行っています）。

2番目の句が何をしているのかわかりませんが、それを削除して再帰呼び出しに追加p.dataすると、「現在の」ステップが変数resに保存されていることを確認する必要があります。res

if (p.data == target) {
    res = res + p.data;
    System.out.println(res);
} else {
    pathToNode(p.leftLink, target, res + p.data);
    pathToNode(p.rightLink, target, res + p.data);
}

このように、再帰的アルゴリズムに共通の従来の基本ケース+再帰的ケースを使用しています。

于 2012-11-16T10:17:59.617 に答える