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 1n7 2n4 4n3 6n1 8

>> 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 :

>> 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

The subnet calculator helps you design networks by taking an IP address and network mask and returning information such as network, broadcast address, and host range.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

>> 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.

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.

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?

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();

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

jericho_lawAuthor Commented:

Nice guidance from Infinity08. Great contributor. =)

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