Prev: solution for implementing algorithms
Next: biew-6.1.0 has been released
From: Chad on 11 Dec 2009 13:35
On Dec 10, 11:33 pm, Richard Heathfield <r...(a)see.sig.invalid> wrote:
> In <d4396e32-28f4-4602-b44d-385fd5e99...(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

Maybe I'm reading too much into this, but is there a difference
between visiting a subtree and visiting a subtree entirely? If so,
what is it.

From: Casey Hawthorne on 11 Dec 2009 13:45
Do you mean you want to visit all the children, then all the
grand-children?

Think about why the tree traversals: preorder, inorder, and postorder
don't do what you want.


If traversing a graph, look up Breadth-First Search (BFS), which
"tree-ifies" a graph.

Compare it with Depth-First Search (DFS).


On Thu, 10 Dec 2009 17:46:59 -0800 (PST), Chad <cdalten(a)gmail.com>
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);
> }
>}
--
Regards,
Casey
From: Richard Heathfield on 11 Dec 2009 17:45
Chad wrote:
> On Dec 10, 11:33 pm, Richard Heathfield <r...(a)see.sig.invalid> wrote:
>> In <d4396e32-28f4-4602-b44d-385fd5e99...(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
>
> Maybe I'm reading too much into this, but is there a difference
> between visiting a subtree and visiting a subtree entirely? If so,
> what is it.

Taking the above tree: if you visit the node, then its left subtree, and
then its right subtree, recursively, then you get DBACFEG. What he
actually wants is DBFACEG.


--
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: Chad on 11 Dec 2009 18:20
On Dec 11, 10:45 am, Casey Hawthorne <caseyhHAMMER_T...(a)istar.ca>
wrote:
> Do you mean you want to visit all the children, then all the
> grand-children?
>
> Think about why the tree traversals: preorder, inorder, and postorder
> don't do what you want.
>
> If traversing a graph, look up Breadth-First Search (BFS), which
> "tree-ifies" a graph.
>

Yes, I looking to do a Breadth-First Search. I just forgot what it was
called when I asked the question.

> Compare it with Depth-First Search (DFS).
>

I know for sure that I don't need to do a Depth-First Search.

> On Thu, 10 Dec 2009 17:46:59 -0800 (PST), Chad <cdal...(a)gmail.com>
> 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);
> >  }
> >}
>

And for whatever reasons, I thought that my original code constituted
a Breadth-First Search.
From: Patricia Shanahan on 11 Dec 2009 18:47
Chad wrote:
> On Dec 11, 10:45 am, Casey Hawthorne <caseyhHAMMER_T...(a)istar.ca>
> wrote:
>> Do you mean you want to visit all the children, then all the
>> grand-children?
>>
>> Think about why the tree traversals: preorder, inorder, and postorder
>> don't do what you want.
>>
>> If traversing a graph, look up Breadth-First Search (BFS), which
>> "tree-ifies" a graph.
>>
>
> Yes, I looking to do a Breadth-First Search. I just forgot what it was
> called when I asked the question.

The simplest way I know to do a BFS of a tree uses a queue of nodes.
Initialize it to contain just the root. Iterate on the following until
the pop fails because the queue is empty:

Pop the head item.
Process it.
Push its children to the end of the queue.

Patricia
First  |  Prev  |  Next  |  Last
Pages: 1 2 3
Prev: solution for implementing algorithms
Next: biew-6.1.0 has been released