Recursion in C#

  • Thread starter Thread starter Guest
  • Start date Start date
G

Guest

Hello friends
I have a tree structure that I want to cross, looking for a specific node
I have tried to develope a recursive function, but when it has to leave, and return the result, it does not stop the execution, and it follows until the end of the tree
Can you help with code samples of tree search, or recursion in C# ??
Thanks a lot friend

Shark ....
 
Hello,

Since you do not provide any information on what kind of tree
you are working with, I will provide some information using a
basic binarytree where each node can have two childen, the left
and right child. The node could be designed like this (note that
I make the childen public, of course you should use properties
for this). The node includes an int variable to represent a value
in the node, you would replace this variable to suite the kind of
information you need to store:

public class BinaryNode
{
public BinaryNode left;
public BinaryNode right;
public int value;
}

Basicly what you need to do to stop the recusion is to define a
condition where the recursive method does a return instead of
continuting to call itself again.

I also do not know if the travers order is of intresst to you, so I
will breifly describe the three methods of traversing a binarytree
structure.

(1) Pre-order : Check the value of the current node and then
continue on to the left child and then the right child.

(2) In-order : Check the value of the left child, then the current
child, and last the right child.

(3) Post-order: Check the left child then the right child, and last
check the current child.

So what we will do is make a pseudo-code definition of the
BinaryTree class to illustrat what we will be doing. We have a public
method Find which will look for the node with a given value, and then
return it. This method will be the recusion-starter and we will use a
private method to do the actuall recusion.

public class BinaryTree
{
private BinaryNode root;

public BinaryTree()
{
}

public BinaryNode Find(int v)
{
if( this.root != null )
this.Find(v, root)
}

private BinaryNode Find(int v, BinaryNode n)
{
// Implement the recursive search using a given
// travers method.
}
}

Now we need to implement the private recusive method using the
traversation order we desire. I will show you how it would look, using
all of the three orders. The condition we will use to stop the recusion is
when we find a node (any node) with a given value.

(1) Pre-Order Traversion

private BinaryNode Find(int v, BinaryNode n)
{
if( n.value == value )
return this;

if( n.left != null )
this.Find(v, n.left);

if( n.right != null )
this.Find(v, n.right);
}

(2) In-Order Traversion

private BinaryNode Find(int v, BinaryNode n)
{
if( n.left != null )
this.Find(v, n.left);

if( n.value == value )
return this;

if( n.right != null )
this.Find(v, n.right);
}

(3) Post-Order Traversion

private BinaryNode Find(int v, BinaryNode n)
{
if( n.left != null )
this.Find(v, n.left);

if( n.right != null )
this.Find(v, n.right);

if( n.value == value )
return this;
}

Please note that in this simple example, the order of traversion
has litle effect, unless you perhaps always see to it that you have
a balanced, sorted, BinaryTree. I illustrated all three travers orders
since you provided spars information on what you stor, in what kind
of tree etc. But the basic idea of defining one or many conditions to
stop AND return from the recusive method is the same even if you
use a non-binarytree structure.

Hope this helps,

//Andreas Håkansson

MadWildShark said:
Hello friends.
I have a tree structure that I want to cross, looking for a specific node.
I have tried to develope a recursive function, but when it has to leave,
Click to expand...
and return the result, it does not stop the execution, and it follows until
the end of the tree.
 
Oh sorry, please note that in the code for illustrating the different
traverse orders, the following

if( n.value == value )
return this;

should be changed into this

if( n.value == v )
return this;

//Andreas
 
The tree that I'm using, has infinite children
I need some samples with that !!

Thanks again !!

----- Andreas HÃ¥kansson wrote: ----

Hello

Since you do not provide any information on what kind of tre
you are working with, I will provide some information using
basic binarytree where each node can have two childen, the lef
and right child. The node could be designed like this (note tha
I make the childen public, of course you should use propertie
for this). The node includes an int variable to represent a valu
in the node, you would replace this variable to suite the kind o
information you need to store

public class BinaryNod

public BinaryNode left
public BinaryNode right
public int value


Basicly what you need to do to stop the recusion is to define
condition where the recursive method does a return instead o
continuting to call itself again

I also do not know if the travers order is of intresst to you, so
will breifly describe the three methods of traversing a binarytre
structure

(1) Pre-order : Check the value of the current node and the
continue on to the left child and then the right child

(2) In-order : Check the value of the left child, then the curren
child, and last the right child

(3) Post-order: Check the left child then the right child, and las
check the current child

So what we will do is make a pseudo-code definition of th
BinaryTree class to illustrat what we will be doing. We have a publi
method Find which will look for the node with a given value, and the
return it. This method will be the recusion-starter and we will use
private method to do the actuall recusion

public class BinaryTre

private BinaryNode root

public BinaryTree(



public BinaryNode Find(int v

if( this.root != null
this.Find(v, root


private BinaryNode Find(int v, BinaryNode n

// Implement the recursive search using a give
// travers method



Now we need to implement the private recusive method using th
traversation order we desire. I will show you how it would look, usin
all of the three orders. The condition we will use to stop the recusion i
when we find a node (any node) with a given value

(1) Pre-Order Traversio

private BinaryNode Find(int v, BinaryNode n

if( n.value == value
return this

if( n.left != null
this.Find(v, n.left)

if( n.right != null
this.Find(v, n.right)


(2) In-Order Traversio

private BinaryNode Find(int v, BinaryNode n

if( n.left != null
this.Find(v, n.left)

if( n.value == value
return this

if( n.right != null
this.Find(v, n.right)


(3) Post-Order Traversio

private BinaryNode Find(int v, BinaryNode n

if( n.left != null
this.Find(v, n.left)

if( n.right != null
this.Find(v, n.right)

if( n.value == value
return this


Please note that in this simple example, the order of traversio
has litle effect, unless you perhaps always see to it that you hav
a balanced, sorted, BinaryTree. I illustrated all three travers order
since you provided spars information on what you stor, in what kin
of tree etc. But the basic idea of defining one or many conditions t
stop AND return from the recusive method is the same even if you
use a non-binarytree structure.

Hope this helps,

//Andreas HÃ¥kansson

MadWildShark said:
Hello friends.
I have a tree structure that I want to cross, looking for a specific node.
I have tried to develope a recursive function, but when it has to leave,
Click to expand...
and return the result, it does not stop the execution, and it follows until
the end of the tree.
 
Hello again,

Well, it would not be that hard. I do not know how each of your
nodes store thier childen, but I assume you use some kind of array
to store them:

private Nodes[] children;

If so, then you could do something like this

public Node Find(int v)
{
if( this.root != null )
this.Find(v, root);
}

private Node Find(int v, Node n)
{
if( n.value == n )
return n;

for(int n = 0; children.Length - 1; n++)
this.Find(v, nodes[n]);
}

Basicly here you only have In-order and Post-order
traversin (move the check to after the loop to get a
Post-order travers).

Hope this helps,

//Andreas
 
The tree that I defined, has infinite children
I need some samples with that !!

Thanks again !!
 
This might be a crazy idea and please let me know if this method wouldn't
work for you, but aren't the features in visual studio to do the
following...
1. base their tree on an xml document.
2. Resync the tree with the xml document.
3. Add nodes to the xml document as needed.
4. Use built in xml functionality to search for what they wanted in the
trees, even specifying how deep to search.

Anyway just an idea.
 
Hi, When you are talking about general Trees, the thing is diferent. You can take three kinds of implementation..

the first, and maybe, the easiest, Pointer to fathe
the second, Pointer to first son and Rigth Brother.
the third, both of them..

the classes may look like this

First case..

class GeneralTre

cNode Father
object Value


second case...

class GeneralTre

cNode FirstSon
cNode RigthBrother
object Value


third case...

class GeneralTre

cNode Father
cNode FirstSon
cNode RigthBrother

object Value


in C# you must keep this values in and arraylist or add a Next pointer to each kind of implementation...

I hope this help.
 
Nathan,

This would give a (huge) performance penalty and would need a much
larger memory footprint then just recusivly travers the tree. First you
would
have to build the XmlDocument and then search (recusivly or with XPath)
to find the node.

//Andreas
 
Back
Top