Prev: solution for implementing algorithms
Next: biew-6.1.0 has been released
From: Pascal J. Bourguignon on 11 Dec 2009 19:56
Chad <cdalten(a)gmail.com> writes:

> Let's say that I have a balanced binary tree with N nodes. Now when I
> go down the tree, I want to visit both the left and right child at the
> same time until I reach NULL. Is this possible? If so, could I do
> something like the following....
>
> int search(struct node* node, int data) {
> if (node == NULL) {
> return 0;
> }
> else {
> /*Do some stuff with data* */
> return(search(node->left, more_data) ||
> search(node->right, more_data);
> }
> }

Tree walks are distinguished by where you're processing each node with
respect to the recursive calls. For a binary tree, you have two
recursive calls, therefore three different positions for the
processing of the node, three different walks: prefix, infix, suffix.


int search_prefix(struct node* node, int data) {
if (node == NULL) {
return 0;
} else {
/* Do some stuff with data in prefix mode */
search_prefix(node->left, more_data);
search_prefix(node->right, more_data);
}
}


int search_infix(struct node* node, int data) {
if (node == NULL) {
return 0;
} else {
search_infix(node->left, more_data);
/* Do some stuff with data in infix mode */
search_infix(node->right, more_data);
}
}


int search_suffix(struct node* node, int data) {
if (node == NULL) {
return 0;
} else {
search_suffix(node->left, more_data);
search_suffix(node->right, more_data);
/* Do some stuff with data in suffix mode */
}
}


For left-to-right processing of the nodes you will probably want an infix walk.


--
__Pascal Bourguignon__
From: Gene on 13 Dec 2009 19:10
On Dec 11, 1:09 pm, Ben Pfaff <b...(a)cs.stanford.edu> wrote:
> Richard Heathfield <r...(a)see.sig.invalid> writes:
> > I don't recall *ever* having to use breadth-first search. It seems
> > that I have made the (common) mistake of assuming my own experience
> > (or in this case, lack thereof) to be typical.
>
> BFS is good for testing.  If you are testing a stateful system,
> by starting from an initial state and then applying a series of
> actions, checking the system's correctness after each action,
> then breadth-first search will find bugs after the minimum number
> of actions, which is easier to debug than otherwise.
> --
> Ben Pfaffhttp://benpfaff.org

I've also used it for testing of parsers: to generate strings from the
respective grammar. The BFS lets you to generate terminal strings
even with recursive rules.

BFS also occurs in building level graphs for max flow and similar
problems.

It's easy and on average twice as fast as DFS for solving the shortest-
path problem if all edges have unit length.
From: Casey Hawthorne on 13 Dec 2009 20:37
On Sun, 13 Dec 2009 16:10:23 -0800 (PST), Gene
<gene.ressler(a)gmail.com> wrote:

>On Dec 11, 1:09�pm, Ben Pfaff <b...(a)cs.stanford.edu> wrote:
>> Richard Heathfield <r...(a)see.sig.invalid> writes:
>> > I don't recall *ever* having to use breadth-first search. It seems
>> > that I have made the (common) mistake of assuming my own experience
>> > (or in this case, lack thereof) to be typical.
>>
>> BFS is good for testing. �If you are testing a stateful system,
>> by starting from an initial state and then applying a series of
>> actions, checking the system's correctness after each action,
>> then breadth-first search will find bugs after the minimum number
>> of actions, which is easier to debug than otherwise.
>> --
>> Ben Pfaffhttp://benpfaff.org
>
>I've also used it for testing of parsers: to generate strings from the
>respective grammar. The BFS lets you to generate terminal strings
>even with recursive rules.
>
>BFS also occurs in building level graphs for max flow and similar
>problems.
>
>It's easy and on average twice as fast as DFS for solving the shortest-
>path problem if all edges have unit length.

And BFS can search game trees a ply at a time without trying to bottom
out on one path.

--
Regards,
Casey
First  |  Prev  | 
Pages: 1 2 3
Prev: solution for implementing algorithms
Next: biew-6.1.0 has been released