5

深さ優先検索に関するウィキペディアの記事で説明されている内容によると、バイナリ ツリーの DFS は、事前順序付けされたトラバーサル ルート (左から右) と同じだと思います (私は正しいですか?)。

しかし、少し検索してこのコードを取得しました。このコードの作成者は、ノードが以前にアクセスされたことがあるかどうかを記録するためにツリーが必要であると主張しています (または、グラフの場合はこれが必要ですか?)。

// copyright belongs to the original author 
public void dfs() {
    // DFS uses Stack data structure
    Stack stack = new Stack();
    stack.push(this.rootNode);
    rootNode.visited=true;
    printNode(rootNode);
    while(!stack.isEmpty()) {
        Node node = (Node)s.peek();
        Node child = getUnvisitedChildNode(n);
        if(child != null) {
            child.visited = true;
            printNode(child);
            s.push(child);
        }
        else {
            s.pop();
        }
    }
    // Clear visited property of nodes
    clearNodes();
}

誰でもこれを説明できますか？

4

2 に答える 2

5

はい、予約注文です。ただし、ツリーをトラバースしない可能性があるため、トラバーサルとは言いたくありません。要素を見つけるとすぐに停止します。印刷したプログラムは検索ではなく、トラバーサルです。すべてを印刷しています。二分木で検索する検索関数は次のようになります。

public boolean search(Tree t, int i) {
    if(t == null)
        return false;
    elif(t.value() == i)
        return true;
    else
        for(child in t.children()) {
            if(search(child,i))
                return true;
        }
        return false;
        //return search(t.leftTree(), i) or search(t.rightTree(),i) binary tree case
}
于 2013-03-06T01:57:03.107 に答える
4

二分木上の dps は、前順トラバーサル ルート - 左 - 右 と同じだと思います (私は正しいですか?)

深さ優先検索は、前、中、または後のトラバーサルにすることができます。スタックは必要ありません。再帰的に実装する方が簡単です。その場合、ノードを訪問済みとしてマークする必要もありません。

于 2013-03-06T01:40:33.113 に答える