DaniWeb Forum Index > Software Development > C++

C++ RSS

tell me how to solve "counting Problem" in a BTree ?

Please support our C++ advertiser: Intel Parallel Studio Home

•

Join Date: Apr 2007

Posts: 85

Reputation: Zay is an unknown quantity at this point

Solved Threads: 0

Zay

Offline

Junior Poster in Training

tell me how to solve "counting Problem" in a BTree ?

Jun 1st, 2007

Hello;

i have this Question and need your help, i do not know how to solve it;

Problem:
Write a member function called countNodeWithNoRchild that will return the number of nodes in a BT(binary Tree) does not have a right child. (Hint: a leaf node also does not have a right child)

i try to do it but the ways i followed are wrong , because there are some missing node not visited yet ..

•

Join Date: Sep 2004

Posts: 7,606

Reputation: Narue has a reputation beyond repute

Solved Threads: 713

Narue

Offline

Code Goddess

Re: tell me how to solve "counting Problem" in a BTree ?

Jun 1st, 2007

Have you written a function that tells you the height of a binary search tree? If you have, you can use the same principles to solve this problem. If you haven't, you need to do a complete traversal of the tree (recursive is easiest) and for each node, return the count of the nodes below it that have no right child. The hint in your problem gives you the base case for recursion.

I'm here to prove you wrong.

•

Join Date: Apr 2007

Posts: 85

Reputation: Zay is an unknown quantity at this point

Solved Threads: 0

Zay

Offline

Junior Poster in Training

Re: tell me how to solve "counting Problem" in a BTree ?

Jun 2nd, 2007

see my code , i do it using recursion

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
 
int count(nodeType<T> *p)
{ if (p==NULL)  // when reach the end or this is an empty tree
return 0;
 
else if (p->rlink==NULL && p->llink!=NULL)
return (1+count(p->llink));
 
else if(p->rlink==NULL&&p->llink==NULL)//leaf node no R & no L
return(1+count(p->llink));
 
else // node with R and L
return (1+count(p->rlink), count(p->llink));
 
}
 
int count(nodeType<T> *p)
{ if (p==NULL)  // when reach the end or this is an empty tree
return 0;
 
else if (p->rlink==NULL && p->llink!=NULL)
return (1+count(p->llink));
 
else if(p->rlink==NULL&&p->llink==NULL)//leaf node no R & no L
return(1+count(p->llink));
 
else // node with R and L
return (1+count(p->rlink), count(p->llink));
 
}

correct ??

•

Join Date: Sep 2004

Posts: 7,606

Reputation: Narue has a reputation beyond repute

Solved Threads: 713

Narue

Offline

Code Goddess

Re: tell me how to solve "counting Problem" in a BTree ?

Jun 2nd, 2007

Basically what you're doing is a typical node count, but you only increment the count when p->rlink is null. Something along these lines:

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
int count ( nodeType<T> *p )
{
  if ( p == NULL )
    return 0;
  else {
    int left = count ( p->llink );
    int right = count ( p->rlink );
 
    return right + left + ( p->rlink == NULL );
  }
}
int count ( nodeType<T> *p )
{
  if ( p == NULL )
    return 0;
  else {
    int left = count ( p->llink );
    int right = count ( p->rlink );

    return right + left + ( p->rlink == NULL );
  }
}