Geek asks and answers

How to implement depth search (DFS) on a binary tree in java?

According to what the Wikipedia article about depth-searching does , I think that DFS on a binary tree is identical to circumventing root-left-right pre-orders (am I right?).

But I just did a little search and got this code, the author of which claims that DFS needs a tree for writing if node has been visited before (or do we need it in case of a graph?).

// 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();
}

Can anyone explain this?

+5
source share
2 answers

, . , , , , . , , , : . :

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
}
+5

, dps , preorder - - . (am right?)

, . : , .

+4

More articles:


All Articles