Prev: solution for implementing algorithms
Next: biew-6.1.0 has been released
From: Chad on 10 Dec 2009 20:46
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);
}
}
From: Richard Heathfield on 11 Dec 2009 02:33
In <d4396e32-28f4-4602-b44d-385fd5e99a85(a)u1g2000pre.googlegroups.com>,
Chad wrote:

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

A simple recursive solution such as the one you give here will visit
an left (or right) subtree in its entirety, and will then visit the
other subtree in its entirety. If you want to visit the nodes in
strict left-right order, one row at a time, i.e. if in this tree

D
/ \
B F
/ \ / \
A C E G

you want the order DBFACEG, then the best way is probably to pre-scan
the tree, building a list of pointers, and then iterate through the
list. (Actually, the best way is even more probably to question why
on earth you decided to use a tree in the first place, given the
weird ordering you want - but I can think of *one* good reason for
ordering access in this way - i.e. printing.)


--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
"Usenet is a strange place" - dmr 29 July 1999
Sig line vacant - apply within
From: Ben Bacarisse on 11 Dec 2009 08:49
Richard Heathfield <rjh(a)see.sig.invalid> writes:

> In <d4396e32-28f4-4602-b44d-385fd5e99a85(a)u1g2000pre.googlegroups.com>,
> Chad wrote:
>
>> 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);
>> }
>> }
>
> A simple recursive solution such as the one you give here will visit
> an left (or right) subtree in its entirety, and will then visit the
> other subtree in its entirety. If you want to visit the nodes in
> strict left-right order, one row at a time, i.e. if in this tree
>
> D
> / \
> B F
> / \ / \
> A C E G
>
> you want the order DBFACEG, then the best way is probably to pre-scan
> the tree, building a list of pointers, and then iterate through the
> list. (Actually, the best way is even more probably to question why
> on earth you decided to use a tree in the first place, given the
> weird ordering you want - but I can think of *one* good reason for
> ordering access in this way - i.e. printing.)

Does breadth first search really deserve the term "weird"? I agree
that it is perhaps more common when the tree is generated during the
search but I can imagine it occurring as a solution before it becomes
clear that the actual tree can be removed altogether.

Anyway, it is also common enough in algorithms on graphs that I would
not call it weird.

--
Ben.
From: Richard Heathfield on 11 Dec 2009 12:19
In
<0.ec57c4bc16062d8bc5f0.20091211134948GMT.871vj1ips3.fsf(a)bsb.me.uk>,
Ben Bacarisse wrote:

<snip>

> Does breadth first search really deserve the term "weird"? I agree
> that it is perhaps more common when the tree is generated during the
> search but I can imagine it occurring as a solution before it
> becomes clear that the actual tree can be removed altogether.
>
> Anyway, it is also common enough in algorithms on graphs that I
> would not call it weird.

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.

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
"Usenet is a strange place" - dmr 29 July 1999
Sig line vacant - apply within
From: Ben Pfaff on 11 Dec 2009 13:09
Richard Heathfield <rjh(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 Pfaff
http://benpfaff.org
 |  Next  |  Last
Pages: 1 2 3
Prev: solution for implementing algorithms
Next: biew-6.1.0 has been released