Learn how to a build a cloud-first strategyRegister Now

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 3392
  • Last Modified:

Binary tree in C++ - Counting the nodes in a tree

Background: Implement binary trees: creating tree nodes, growing a tree by attaching trees to a node, counting the nodes of a tree.

Problem: I've having trouble trying to code the btree.cpp, with the 4 functions. It's my assignment and i'm stuck with these codes.

Can anyone be kind enough to help me out with the 4 functions in btree.cpp?




================== btree.h ================================
class Node {
 
private:
   int key;
   Node *l, *r;
 
public:
   Node(int); // construct a Node with a given key
   void attL(Node *); // take the given Node as left subtree
   void attR(Node *); // take the given Node as right subtree
  int count(); // return the number of nodes in the tree
};
==================================================
 
 
 
=================== btree.cpp ===============================
#include "btree.h"
 
Node::Node(int k) {
	// create a tree node
	
	key = k; 
}
 
void Node::attL(Node *tree) {
	// make tree the left sub-tree
	
	attL(tree->l);
}
 
void Node::attR(Node *tree) {
	// make tree the right sub-tree
 
	attR(tree->r);
}
 
int Node::count() {
	// return the number of nodes of the tree
	
	int count = 1;   // Start by counting the root.
 
	//counting the nodes and adding.
       //return count;
}
 
==================================================
 
================== test.cpp ================================
#include <iostream>
using namespace std;
#include "btree.h"
 
int main() {
   Node n1=1, n2=2, n3=3, n4=4, n5(5), n6(6), n7(7), n8(8);
 
   cout << "n8\t" << n8.count() << endl;
   
   n7.attR(&n8);
   cout << "n7\t" << n7.count() << endl;
 
   n4.attL(&n6);
   n4.attR(&n7);
   cout << "n4\t" << n4.count() << endl;
 
   n3.attL(&n4);
   n3.attR(&n5);
   cout << "n3\t" << n3.count() << endl;
 
   n1.attL(&n2);
   n1.attR(&n3);
   cout << "n1\t" << n1.count() << endl;
}
=======================================
i should be looking at this output:
 
n8 1
n7 2
n4 4
n3 6
n1 8

Open in new window

0
jericho_law
Asked:
jericho_law
  • 9
  • 8
2 Solutions
 
Infinity08Commented:
>> void Node::attL(Node *tree) {
>>         // make tree the left sub-tree
>>         
>>         attL(tree->l);
>> }

attL means : attach the Node passed as parameter to the current node (this), as the left sub-tree.

So, don't call attL recursively, but rather assign tree to the left sub-tree in the node.

Same for attR.


>> int Node::count() {
>>         // return the number of nodes of the tree
>>         
>>         int count = 1;   // Start by counting the root.
>> 
>>         //counting the nodes and adding.
>>        //return count;
>> }

You'll need to traverse the tree, starting from the current node as the root. Count all nodes that you encounter, and return the total count at the end.
0
 
jericho_lawAuthor Commented:
Hi Infinity08,

Thanks for your help! Correct me if i'm wrong, should it be this instead for the attL and attR:

void Node::attL(Node *tree) {
        // make tree the left sub-tree
       
      l = tree;      // this is the correct way?
      //tree->l;      // or this?
}


For the counting, i'm not sure how to do the traversing. I managed to source some online help and what i got was something like this:

int size(struct node* node) {
  if (node==NULL) {
    return(0);
  } else {
    return(size(node->left) + 1 + size(node->right));
  }
}

There's a parameter in this case, so i'm not sure how to get the count. Or should i be even looking at size?

Really appreciate your help.

0
 
jericho_lawAuthor Commented:
Anyone able to help me out?
0
Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
Infinity08Commented:
>> Correct me if i'm wrong, should it be this instead for the attL and attR:

Yes, looks good :)

Btw, in your constructor, you might want to initialize the left and right sub-trees to NULL to show that no sub-trees are attached to it (yet).


>> i got was something like this:

Do you understand how that code works ?


Try to think about it. If you have a tree, how would you count its nodes in your head, if you started at the root ?
0
 
jericho_lawAuthor Commented:
Thanks for the guidance.

Hmm, i'm still very unsure about the counting. Putting aside coding, if i will to count the nodes, i will probably start from the root and go either right or left first.

Say, count=1 with root, if there's no left, then right, count+1, then repeat again?

If put into programming terms, i have to have quite a number of loops? Or is there a way i do the checking of total left and total right sub-trees from the root.

For this coding, it's sum of the size of all the left subtrees with all the right subtrees and adding 1 which is the root. Am i right?

int size(struct node* node) {
  if (node==NULL) {
    return(0);
  } else {
    return(size(node->left) + 1 + size(node->right));
  }
}

Are you able to guide me with some skeletons coding? Thanks a million.
0
 
Infinity08Commented:
>> if i will to count the nodes, i will probably start from the root and go either right or left first.

Right, so say you go left first. Once you have counted all nodes on the left side, you go to the right, and count all nodes there. So, you get :

        count(tree) = count(left sub-tree) + 1 + count(right sub-tree)

That is the so-called recursive approach to counting nodes in a tree (recursive because for counting the nodes in the left and right sub-trees, you call the same count method).


>> For this coding, it's sum of the size of all the left subtrees with all the right subtrees and adding 1 which is the root. Am i right?

Correct.


>> Are you able to guide me with some skeletons coding?

Well, now you understand how it's done, it should be relatively easy to put it into code. You have this method :

        int Node::count() {
            // ...
        }

which has to count all nodes in the tree starting from the current node (this). So, you have 1 for the current node, and two recursive calls for the left and right sub-trees.
0
 
jericho_lawAuthor Commented:
I'm able to understand this:

 count(tree) = count(left sub-tree) + 1 + count(right sub-tree)

as a pseudocode, but i'm rather lost when the method i have is just count() which doesn't parse in any parameter. In this case, how can do my count for my left and right subtrees?

Sorry i'm not able to see it in C++ context. =(
0
 
Infinity08Commented:
The thing is that we're dealing with a method (member function). Methods have a hidden parameter, that is the object the method is called from.

So, if you call :

        Node n;
        int cnt = n.count();

then you call the count method for the n object. And the count method will count all nodes that are part of the tree with n as the root.
0
 
jericho_lawAuthor Commented:
Sorry that i'm not getting your point. =(

How close am i with this?

int Node::count() {
      // return the number of nodes of the tree

      return (1+ l.count() + r.count()) ;  // Return the total.
}
0
 
Infinity08Commented:
>> How close am i with this?

Pretty close ;)

Except for two small things :

1) l and r are pointers to Node, so you need to dereference the pointer first before calling the method. ie. l->count() instead of l.count()

2) you need to account for the tree leaves (end points of the branches). At a leaf, the l (or r) pointer is NULL. If it is NULL, then the count for that sub-tree is obviously 0, and you cannot dereference the pointer. So, check for NULL before dereferencing the pointer.
0
 
jericho_lawAuthor Commented:
You're a good teacher.

Here's my changes:

int Node::count() {
      // return the number of nodes of the tree
            
      int leftCount=0;
      int rightCount=0;
      
      if(l!=NULL)  // has left-subtrees
            leftCount = l->count();
            
    if(r!=NULL)  // has right-subtrees
            rightCount = r->count();
            
      return (leftCount + 1 + rightCount) ;  // Return the total.

}

Have i got it?
0
 
Infinity08Commented:
>> Have i got it?

That should do the trick, yes :)

Now, try it with the test code, and see if you get the correct output. If there's anything still wrong, then you can post the whole code here again, and I'll have a look at it.
0
 
jericho_lawAuthor Commented:
Yes, it works! =)


I've some questions though. Hope you are able to answer my doubts:

1. The int variable key. What is the purpose of it? Sort of an identifier to the root node?

2. An alternative to l->count() is (*l).count()?

3. I'm not sure with the Nodes declared in test.cpp: (Node n1=1, n2=2, n3=3, n4=4, n5(5), n6(6), n7(7), n8(8)). Can you explain the difference with n1=1 and n5(5)?

4. How are the nodes counted in the test.cpp? The tree keep getting extended down the coding?

             8
                       8
                 6           7
          4           5
    2         3

Is this correct?
0
 
Infinity08Commented:
>> Hope you are able to answer my doubts:

Sure.


>> 1. The int variable key. What is the purpose of it? Sort of an identifier to the root node?

It is supposed to be the content of the node (there wouldn't be much point to the tree if nothing was stored in it). Here, for demonstration purposes, an int value is used, and each node has a different value, so it's easy to distinguish them.


>> 2. An alternative to l->count() is (*l).count()?

Correct. They do the exact same thing.


>> 3. I'm not sure with the Nodes declared in test.cpp: (Node n1=1, n2=2, n3=3, n4=4, n5(5), n6(6), n7(7), n8(8)). Can you explain the difference with n1=1 and n5(5)?

In this case, there is no difference in behavior. Both notations will call the constructor (that takes a single int as parameter), and construct a Node object.

They are semantically different though. n1=1 basically casts the int value 1 to a Node object (by calling the constructor). n5(5) explicitly calls the constructor.

I prefer the latter, as it's clearer what happens. A cast does not make a lot of sense (how do you cast an int to a Node - they're two different concepts - it's like saying that you transform a chair into a cupboard).


>> 4. How are the nodes counted in the test.cpp? The tree keep getting extended down the coding?

The recursive approach performs a depth-first search :

        http://en.wikipedia.org/wiki/Depth-first_search

Note that the contents of the tree at the end of main look like this :

           1
          / \
        2   3
            /  \
          4    5
         / \
        6  7
              \
               8

The depth first search would traverse the nodes in this order :

        1 2 1 3 4 6 4 7 8 7 4 3 5 3 1

Or the total count would be :

        (1) + 1 + (((1) + 1 + ((0) + 1 + (1))) + 1 + (1)) = 8

or, a different way of looking at it, the nodes are counted in this order :

        2 1 6 4 7 8 3 5
0
 
jericho_lawAuthor Commented:
Nice guidance from Infinity08. Great contributor. =)
0
 
jericho_lawAuthor Commented:
Thanks! I understand them better now. =)
0
 
Infinity08Commented:
Glad to have been of assistance :)
0

Featured Post

Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

  • 9
  • 8
Tackle projects and never again get stuck behind a technical roadblock.
Join Now