Re: Depth First Search in Binary Search Tree?


Howard 寫道：

"howa" <howachen@xxxxxxxxx> wrote in message
news:1161876654.310945.67020@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx


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.

-Howard

if this is a binary tree, there is no need to check `visited` or not

.

Relevant Pages