Re: Depth First Search in Binary Search Tree?
- From: "L7" <jesse.r.brown@xxxxxxxxx>
- Date: 27 Oct 2006 07:44:02 -0700
Howard wrote:
"CBFalconer" <cbfalconer@xxxxxxxxx> wrote in message
news:4540E069.4D6DD86@xxxxxxxxxxxx
Howard wrote:
"howa" <howachen@xxxxxxxxx> wrote in message
from the web, i found:
void dfs (TreeElement t) {
print(t);
if (t.left!=null) dfs(t.left);
if (t.right!=null) dfs(t.right);
}
seems same as pre-order?
It IS a pre-order traversal. It's not a search at all. Why it's
called "dfs" is beyond me. A search implies you're looking for
something, right? There's nothing in that code which checks to see
if a desired node is found, nor any way to report it if it were
found. It's simply a poorly named pre-order traversal.
But, with some changes, it can be used for a depth first search:
void dfs(telem *t, int curdepth, int depth) {
if (++curdepth == depth) print(t);
if (t->left) dfs(t->left, currdepth, depth)
if (t->right) dfs(t->right, currdepth, depth)
}
...
dfs(t, 0, d); /* print items at depth d */
That's not the meaning of a depth-first search. A depth-first search means
that you are looking for a node which meets a specific condition. It
A DFS has nothing to do with locating a specific node.
searches for a SINGLE node. It does not report all nodes meeting some
condition. And the "depth" of that node in the tree does not need to be a
condition of the search (although it could be, if that's something you cared
about).
A DFS is performed by checking the current node to see if it's the one you
want (using whatever criteria you want to make that decision), and if you
haven't found it yet, then checking the ENTIRE subtree of one of the
children of the node, before moving on to check any of the other children.
This method means that you'll get all the way to the bottom of the tree down
one path before moving sideways at all. That's what "depth-first" means.
It looks "deeper" before it looks across. (An alternative search method is
"breadth-first", which checks all child nodes of the current node before
moving downward to check their child subtrees.)
You keep using the term 'tree'. You should be using the term 'graph'.
While a tree is a graph, and therefore can have DFS applied to it, it
is not the _only_ type of graph out there. More correctly, a DFS (or
BFS for that matter) is used to construct trees from graphs.
These algorithms do not imply that a particular element is being
searched for (although it is entirely possible to search using this
method). The marking of the nodes of the graph are to indicate the
current state of the node (i.e. new, visited, complete). Useful for
locating (and eliminating) cycles in large, dense graphs the DFS has
more use than what you claim it does for 'trees'. As a tree that can be
searched using preorder/postorder/inorder has no smaller connected
components, you wouldn't see the benefit of a DFS over any other
traversal algorithm, but try using an in-order traversal to determine
connected components or articulation points in a graph.
What you've shown is simply a pre-order traversal which reports all nodes of
a given depth. It's NOT a depth-first search.
-Howard
.
- Follow-Ups:
- Re: Depth First Search in Binary Search Tree?
- From: Howard
- Re: Depth First Search in Binary Search Tree?
- From: Richard Harter
- Re: Depth First Search in Binary Search Tree?
- References:
- Depth First Search in Binary Search Tree?
- From: howa
- Re: Depth First Search in Binary Search Tree?
- From: Howard
- Re: Depth First Search in Binary Search Tree?
- From: howa
- Re: Depth First Search in Binary Search Tree?
- From: Howard
- Re: Depth First Search in Binary Search Tree?
- From: CBFalconer
- Re: Depth First Search in Binary Search Tree?
- From: Howard
- Depth First Search in Binary Search Tree?
- Prev by Date: Re: Calculate gradient in C
- Next by Date: Re: finding primes
- Previous by thread: Re: Depth First Search in Binary Search Tree?
- Next by thread: Re: Depth First Search in Binary Search Tree?
- Index(es):
Relevant Pages
|
|
