5

二分木 (二分探索木ではない) のノードのパスをトレースしようとしています。ノードを指定して、ルートからパスの値を出力しようとしています。

代替テキスト

以下のプログラムを書きました。

package dsa.tree;

import java.util.Stack;

public class TracePath {
    private Node n1;

    public static void main(String args[]){
        TracePath nodeFinder = new TracePath();
        nodeFinder.find();
    }

    public void find(){
        Tree t = getSampleTree();
        tracePath(t,n1);
    }

    private Tree getSampleTree() {
        Tree bsTree = new BinarySearchTree();
        int randomData[] = {43,887,11,3,8,33,6,0,46,32,78,76,334,45};
        for(int i=0;i<randomData.length;i++){
            bsTree.add(randomData[i]);
        }
        n1 = bsTree.search(76);
        return bsTree;
    }

    public void tracePath(Tree t, Node node){
        trace(t,node);
    }

    Stack<Node> mainStack = new Stack<Node>();

    public void trace(Tree t, Node node){
        trace(t.getRoot(),node);
    }

    private void trace(Node parent, Node node){
        mainStack.push(parent);
        if(node.data == parent.data){
            for(Node iNode:mainStack){
                System.out.println(iNode.data);
            }
            return;
        }
        if(parent.left != null){
            trace(parent.left, node);
        }
        if(parent.right!=null){
            trace(parent.right, node);
        }
        mainStack.pop();
    }
}

出力を正しく取得しています。しかし、そのような厄介です。メソッド trace(Node, Node) が表示されている場合は、すべきではない値を出力しています。trace メソッドを正常に完了させたい。少なくとも、if 条件に遭遇した段階で再帰構造を強制終了する必要があります。

お知らせ下さい。

4

5 に答える 5

5

ノードが見つかったら、再帰を強制終了する必要があります。十分に単純です。ノードが見つかったかどうかを示すブール値を返すように trace メソッドを変更します。そうすれば、ノードを見つけた直後にツリーをさかのぼることができます。

private boolean trace(Node parent, Node node){
    mainStack.push(parent);
    if(node.data == parent.data){
        for(Node iNode:mainStack){
            System.out.println(iNode.data);
        }
        return true;
    }
    if(parent.left != null){
        if (trace(parent.left, node)) return true;
    }
    if(parent.right!=null){
        if (trace(parent.right, node)) return true;
    }
    mainStack.pop();
    return false;
}
于 2010-02-11T19:42:02.303 に答える
3

これは宿題だと思いますので、コードの代わりにいくつかのポインタを示します。

  • トレース メソッドは再帰的な降下を行うため、スタックは必要ありません。見つかったノードから戻るときにパス構造を構築できます。
  • メソッドがブール値またはリストの戻り値を使用する場合は、戻るときにパスを出力するか、検索メソッドが戻った後に出力するノードを含むリストを作成できます。

編集：ルートへのパスノードが必要な場合は、単純なブール値の戻り値で十分です：

private boolean trace(Node parent, Node node) {
    boolean found = (node.data == parent.data)

    if (!found && parent.left != null) {
        found = trace(parent.left, node);
    }
    if (!found && parent.right != null){
        found = trace(parent.right, node);
    }

    if (found) {
        System.out.println(parent.data);
    }

    return found;
}

ルートからノードへのパスが必要な場合は、リストを渡してノードを順番に受け取ることができます。

private boolean trace(Node parent, Node node, List path) {
    boolean found = (node.data == parent.data)

    if (!found && parent.left != null) {
        found = trace(parent.left, node);
    }
    if (!found && parent.right != null){
        found = trace(parent.right, node);
    }

    if (found) {
        path.add(0, parent);
    }

    return found;
}

または、帰りにパスを作成してリストとして返すこともできます。

private List trace(Node parent, Node node) {
    List path = null;

    if (null != node) {
        if (node.data == parent.data) {

            path = new ArrayList();
        } else {
            path = trace(parent.left, node);

            if (null == path) {
                path = trace(parent.right, node);
            }
        }
        if (null != path) {
            path.add(0, parent);
        }
    }
    return path;
}
于 2010-02-11T19:35:26.597 に答える
1

このようなもの ？

public Stack<Node> findPath(Node src, Node dest, Stack<Node> alreadyCollected) {
    if (src == dest) 
        return alreadyCollected;
    if (src.left == null && src.right == null)
        return null;
    if (src.left != null) {
        Stack<Node> toTheLeft = new Stack<Node>(alreadyCollected);
        toTheLeft.push(src.left);
        Stack<Node> result = findPath(src.left, dest, toTheLeft);
        if (result != null)
            return result;
    }
    List<Node> toTheRight = new Stack<Node>(alreadyCollected);
    return findPath(src.right, dest, toTheRight);
}
于 2010-02-11T19:55:31.950 に答える
1

これは、スタックを使用しない再帰関数です。再帰は技術的にスタックと同等であり、再帰を行うときにスタックは必要ありません。

PS: 疑似コードを書いています。自分で書き直してコンパイルしてください:)

bool trace(Node curr, Node n, Path path){
    if(curr == null)
        return;
    if(n == curr){
        path.insertAtEnd(curr);
        return true;
    }

    if(trace(curr.left, n, path)){
        path.insertAtEnd(curr);
        return true;
    }
    if(trace(curr.right, n, path)){
        path.insertAtEnd(curr);
        return true;
    }
    return false
}
于 2010-02-11T20:35:54.350 に答える
0

トレースからブール値を返し、再帰呼び出しから返された値に基づいて検索を続行するかどうかを決定します。

于 2010-02-11T19:40:12.560 に答える