Jumping into C++ cha 17 number 2 (binary tree and counting nodes)

[gdz98]

I m in the middle of this exercise of Jumping into C++.
The chapter is about binary trees and I have to build a program that let the user insert as many values as he wants and give him the possibility to see how many values he' s set up to that point. (In short I need to create a function that can count how many values there are in that tree). Here' s my code:

  #include <iostream>

using namespace std;

struct node
{
   int key;
   node* left = NULL;
   node* right = NULL;
};

node* insert (node* tree, int key)
{
    if (!tree)
    {
        node* new_tree = new node;
        new_tree->key = key;
        new_tree->left = NULL;
        new_tree->right = NULL;
        return new_tree;
    }
    if (key < tree->key)
        insert (tree->left, key);
    else
        insert (tree->right, key);
}

void Delete (node* tree)
{
    if (!tree)
        return;
    Delete(tree->left);
    Delete(tree->right);
    delete tree;
}

int Counting (node* tree, int nodes)
{
    if (!tree)
        return nodes;
    nodes++;
    if (!tree->left)
        nodes = Counting(tree->right, nodes);//This 2 statements check the  
    else if (!tree->right)                              // cases where either there are no
        nodes = Counting(tree->left, nodes); // "children" or only one 
    else
    {
        nodes = Counting(tree->left, nodes);    // and this (since the previous 2 
        nodes = Counting(tree->right, nodes);  // if statements) is the case when
                                                                  // you have both of the children
                                                                  //under a tree/sub-tree
    }
    return nodes;
}

int main ()
{
  node* tree = NULL;
  int key;
  int nodes = 0;
  int input;
  cout<<"1. Insert value \n2. See how many values you ve set \n3. Quit"<<endl;
  cin >> input;
  while (input == 1 || input == 2)
  {
    switch (input)
    {
      case 1:
          cout<<"Digit the value you want to insert \n";
          cin >> key;
          tree = insert(tree, key);
          break;
      case 2:
          nodes = Counting(tree, nodes);
          cout<<" You have set "<< nodes <<" value/s so far. \n";
          break;
    }
   cout<<"1. Insert value \n2. See how many values you ve set \n3. Quit"<<endl;
   cin >> input;
   }
   Delete(tree);
}

The issue is that no matter how many numbers I set, it always prints out that I ve only inserted one single value.... Any help with that?

[jonnin]

one way to do this is to keep a counter in your tree class. If you insert an item, increment it. If you remove an item, decrement it.

you can do a full traversal of the tree and count it, you have already seen a traversal when you did the last problem, you can count the nodes in a similar way, with a recursive touch all nodes once function.

these problems highlight what trees are NOT good at, more than their strengths, oddly. But you can overcome these weaknesses! If you store the actual nodes in a vector, and take the address from there to put into the pointers (or, if you want use index into vector instead of a pointer, either way works) you can get a count (vector.size) or sort it (vector sort, rebuild tree after) or do other iterative things without all the hassle and performance issues of trees. You can also use a scheme to store trees as trees in array type containers if that is useful to whatever your goal is (here, its a tree for the sake of a tree in a class, but later, youll be using a tree as a container to solve some problem and will have needs for that container that suit your problem).

[gdz98]

Thanks for the idea you gave me to introduce a new element in my class to keep track of the number of nodes created. It sounds much easier. I deleted the Counting function and made sure to increase the value of the new element "count" each time we add a node in the "insert" function. Now i' ve a problem thou … when I run the program and I insert the value of the new node the program quits itself. Here's my code:

#include <iostream>

using namespace std;

struct node
{
   int key;
   node* left = NULL;
   node* right = NULL;
   int count = 1;
};

node* insert (node* tree, int key)
{
    if (!tree)
    {
        node* new_tree = new node;
        new_tree->key = key;
        new_tree->left = NULL;
        new_tree->right = NULL;
        new_tree->count = tree->count;
        return new_tree;
    }
    if (key < tree->key)
    {
        tree->count++;
        insert (tree->left, key);
    }
    else
    {
        tree->count++;
        insert (tree->right, key);
    }
}

void Delete (node* tree)
{
    if (!tree)
        return;
    Delete(tree->left);
    Delete(tree->right);
    delete tree;
}

int main ()
{
  node* tree = NULL;
  int key;
  int nodes = 0;
  int input;
  cout<<"1. Insert value \n2. See how many values you ve set \n3. Quit"<<endl;
  cin >> input;
  while (input == 1 || input == 2)
  {
    switch (input)
    {
      case 1:
          cout<<"Digit the value you want to insert \n";
          cin >> key; // and then it quits...
          tree = insert(tree, key);
          break;
      case 2:
          cout<<"You' ve set "<< tree->count <<" values so far \n";
          break;
    }
   cout<<"1. Insert value \n2. See how many values you ve set \n3. Quit"<<endl;
   cin >> input;
   }
   Delete(tree);
}

uh... as regards vectors I haven't studied them yet. They're in the next chapter :D

[jonnin]

oh. it crashes becase

if (!tree)
{
node* new_tree = new node;
new_tree->key = key;
new_tree->left = NULL;
new_tree->right = NULL;
new_tree->count = tree->count; //NULL PTR DEREFERENCE ASSURED

Maybe just set count to 1 here?

I think you also need return tree in insert at the end of the function.

interestingly, I believe each node has the correct count of the sub-tree under it, due to how you did the counting. This could be handy, or it could be wasted space (extra int per node and extra counting) depending on your needs. There are ways to reduce the space and work done, but this isnt the time for all that.