13 Replies - 406 Views - Last Post: 01 January 2013 - 12:22 PM Rate Topic: -----

#1 aortell24  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 18
  • Joined: 07-December 12

Finding child Nodes of a node in a tree

Posted 31 December 2012 - 01:12 PM

Hello all I need to find the child nodes of a node in a binary tree.I was just wondering if this will return the number of child nodes thanks.
        public int FindChildNodes()
        {
            if (RightNode == null && LeftNode == null)
            {
                return 1;
            }
            else
            {
                return RightNode.FindChildNodes() + LeftNode.FindChildNodes();
            }
        }



Is This A Good Question/Topic? 0
  • +

Replies To: Finding child Nodes of a node in a tree

#2 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10363
  • View blog
  • Posts: 38,355
  • Joined: 27-December 08

Re: Finding child Nodes of a node in a tree

Posted 31 December 2012 - 01:13 PM

First, you should always test your code. Second, your method won't work as intended because it only counts the leaves. You will want to return 1 + rightCount + leftCount, to include the current node as well.
Was This Post Helpful? 0
  • +
  • -

#3 aortell24  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 18
  • Joined: 07-December 12

Re: Finding child Nodes of a node in a tree

Posted 31 December 2012 - 01:19 PM

how about this?

 
public int FindChildNodes()
        {
            if (RightNode == null) 
            {
                return LeftNode.FindChildNodes() +  1;
            }
            else if (LeftNode == null)
            {
                return RightNode.FindChildNodes() + 1;
            }
            else if (LeftNode == null && RightNode == null)
            {
                return 1;
            }
            else 
            {
                return RightNode.FindChildNodes() + LeftNode.FindChildNodes();
            }
        }


Was This Post Helpful? 0
  • +
  • -

#4 modi123_1  Icon User is offline

  • Suitor #2
  • member icon



Reputation: 8890
  • View blog
  • Posts: 33,338
  • Joined: 12-June 08

Re: Finding child Nodes of a node in a tree

Posted 31 December 2012 - 01:19 PM

Quote

how about this?

... what happens when you run it?
Was This Post Helpful? 0
  • +
  • -

#5 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10363
  • View blog
  • Posts: 38,355
  • Joined: 27-December 08

Re: Finding child Nodes of a node in a tree

Posted 31 December 2012 - 01:20 PM

Nope. Because if both children are not null, you aren't counting the current Node.

By the way- why aren't you testing your code?
Was This Post Helpful? 0
  • +
  • -

#6 aortell24  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 18
  • Joined: 07-December 12

Re: Finding child Nodes of a node in a tree

Posted 31 December 2012 - 01:22 PM

I havent even written the tree class yet. I just wanted some one to take a quick look at it who know what they were doing.
Was This Post Helpful? 0
  • +
  • -

#7 Momerath  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1010
  • View blog
  • Posts: 2,444
  • Joined: 04-October 09

Re: Finding child Nodes of a node in a tree

Posted 31 December 2012 - 01:57 PM

Code won't work if both nodes are null. Your first code was better, just needed to add 1 to the total returned in the last return statement.

And you aren't really finding the child nodes, you are finding the count of the descendant nodes.
Was This Post Helpful? 2
  • +
  • -

#8 aortell24  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 18
  • Joined: 07-December 12

Re: Finding child Nodes of a node in a tree

Posted 31 December 2012 - 02:08 PM

Thanks alot man I just wrote the tree class and it is off it is different each time I run it. I will give that a try Thanks again.
Was This Post Helpful? 0
  • +
  • -

#9 aortell24  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 18
  • Joined: 07-December 12

Re: Finding child Nodes of a node in a tree

Posted 31 December 2012 - 05:17 PM

It is working I am not sure how to mark this solved .Thanks guys
Was This Post Helpful? 0
  • +
  • -

#10 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon


Reputation: 2236
  • View blog
  • Posts: 9,409
  • Joined: 29-May 08

Re: Finding child Nodes of a node in a tree

Posted 31 December 2012 - 06:10 PM

Shouldn't there a parameter to the function, say CurrentNode rather than two external variables LeftNode and RightNode ?

public int CountChildren( Node Current )
{
 if( Current == null ) return 0;
 /* etc */
}



Edit:
Depth-First Yielding of nodes.
Public IEnumerable< INode<T> > YieldChildren< T >(this Current : INode<T> ) 
{
  if( Current == null ) return Enumerable.Empty< T >();
  foreach( n in Current.LHS.YieldChildren() )
    Yield n;
  Yield Current;
  foreach( n in Current.RHS.YieldChildren() )
    Yield n;
}


Now you can use LINQ over the tree.
MyTree.TopNode.YieldChildren().Count()


This post has been edited by AdamSpeight2008: 31 December 2012 - 11:00 PM

Was This Post Helpful? 2
  • +
  • -

#11 Momerath  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1010
  • View blog
  • Posts: 2,444
  • Joined: 04-October 09

Re: Finding child Nodes of a node in a tree

Posted 01 January 2013 - 12:20 AM

Wouldn't depth first have the 'yield current' last? Otherwise that looks just like an inorder traversal. But I do agree it should have parameters, otherwise he's just counting all the nodes (or doing something funky with the left/right node pointers that will bite him, or someone else, later) and it would be easier to just keep a count while you add them.

This post has been edited by Momerath: 01 January 2013 - 12:22 AM

Was This Post Helpful? 0
  • +
  • -

#12 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3449
  • View blog
  • Posts: 10,643
  • Joined: 05-May 12

Re: Finding child Nodes of a node in a tree

Posted 01 January 2013 - 12:51 AM

The parameter is needed if you are looking at from the traditional C way to teaching data structures:
class Node
{
    public Node LeftNode;
    public Node RightNode;
}

class SomeClassThatUsesATree
{
    public int CountChildren(Node node)
    {
        :
    }
}



But if you look at it from the more modern object oriented view where classes are have state and behavior, then you can have:
class Node
{
    public Node LeftNode;
    public Node RightNode;

    public int CountChildren()
    {
        :
    }
}


Was This Post Helpful? 0
  • +
  • -

#13 Momerath  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1010
  • View blog
  • Posts: 2,444
  • Joined: 04-October 09

Re: Finding child Nodes of a node in a tree

Posted 01 January 2013 - 02:05 AM

I think that gives the node too much information. There are trees that don't have the same types of nodes at each level and wouldn't know if those nodes can have children or not. I'd think the proper place to put the count would be in the tree in most cases (AVL, balanced trees being examples where the count might be in the node).

There is also the case where you convert a 'forest' into a single tree and traditionally, right nodes are at the same level so wouldn't be considered child nodes.

This post has been edited by Momerath: 01 January 2013 - 02:28 AM

Was This Post Helpful? 0
  • +
  • -

#14 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon


Reputation: 2236
  • View blog
  • Posts: 9,409
  • Joined: 29-May 08

Re: Finding child Nodes of a node in a tree

Posted 01 January 2013 - 12:22 PM

View PostMomerath, on 01 January 2013 - 08:20 AM, said:

Wouldn't depth first have the 'yield current' last? Otherwise that looks just like an inorder traversal.


Yep! It would but the example was more of a demonstration of using a parameter.

Skydiver I would use an Interface based Node Design.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1