Hi, I got homework about tree data structure

professor wrote his own tree stuff which are: binnode.h and bintree.h
the actual file is tree.cpp

binnode.h

#ifndef BINNODE_H
#define BINNODE_H
#include <math.h>
#include <iostream> 

/*******************************************************\

   template node class for binary tree

\********************************************************/


template <typename dataType> class binNode 
{
   private:
      dataType nodeData;
      binNode<dataType> *left, *right;
      
      void deleteNode(binNode<dataType> **root) {
         if (left == NULL && right == NULL) {
            // leaf node
            *root = NULL;
         } else if (left == NULL) {
            // right branch but no left branch
            *root = right;
         } else if (right == NULL) {
            // left branch but no right branch
            *root = left;
         } else {
            // has left and right branch
            binNode<dataType> *temp = right;
            // find left most node of right branch
            while (temp->left != NULL) temp = temp->left;
            // attach left branch to left side of right branch
            temp->left = left;
            // make root point to right branch
            *root = right;
         }
         left = NULL;
         right = NULL;
         delete (this); 
      }
      
   public:
      // constructor
      binNode() : left(NULL), right(NULL) {
      }
      binNode(const dataType& dataItem) :
         nodeData(dataItem), left(NULL), right(NULL) {
      }
      
      // destructor
      ~binNode() {
         if (left != NULL) delete left;
         if (right != NULL) delete right;
      }

      void insert(const dataType& dataItem) {
         if (nodeData == dataItem) {
            throw std::invalid_argument("dataItem already in tree");
         }
         if (dataItem < nodeData) {
            if (left == NULL) {
               left = new binNode(dataItem);
            } else {
               left->insert(dataItem);
            }
         } else {
            if (right == NULL) {
               right = new binNode(dataItem);
            } else {
               right->insert(dataItem);
            }
         }
      }

      void erase(binNode<dataType> **root, const dataType &delData) {
         if (delData == nodeData) {
            deleteNode(root);
         } else {
            if (delData < nodeData) {
               if (left == NULL) {
                  throw std::invalid_argument("delItem not in tree");
               } else {
                  left->erase(&left, delData);
               }
            } else {
               if (right == NULL) {
                  throw std::invalid_argument("delItem not in tree");
               } else {
                  right->erase(&right, delData);
               }
            }
         }
      }

      dataType* find(const dataType &findData) {
         if (findData == nodeData) {
            return &nodeData;
         } else if (findData < nodeData) {
            if (left == NULL) return NULL;
            else return left->find(findData);
         } else {
            if (right == NULL) return NULL;
            else return right->find(findData);
         }
      }
      
      bool rebalance(binNode<dataType>* &root) {
         int rdepth=0, ldepth=0;
         bool rotate = false;
         if (left != NULL) {
            if (left->rebalance(left)) rotate = true;
            ldepth = left->maxTreeDepth();
         }
         if (right != NULL) {
            if (right->rebalance(right)) rotate = true;
            rdepth = right->maxTreeDepth();
         }

         if (rdepth > ldepth+1) {
            // rotate anitclockwise
            root = right;
            right = right->left;
            root->left = this;
            rotate = true;
         }

         else if (ldepth > rdepth+1) {
            // rotate clockwise
            root = left;
            left = left->right;
            root->right = this;
            rotate = true;
         }
         return rotate;
      }
      
      // tree statistic functions
      int maxTreeDepth() const {
         int rdepth = 0, ldepth = 0;
         if (left != NULL) ldepth = left->maxTreeDepth();
         if (right != NULL) rdepth = right->maxTreeDepth();
         if (ldepth > rdepth) return 1 + ldepth;
         else return 1 + rdepth;
         }
         
      int numNodes() const {
         int size = 1;
         if (left != NULL) size += left->numNodes();
         if (right != NULL) size += right->numNodes();
         return size;
      }

	  void print() const {
	     if (left != NULL) left->print();
		 std::cout << nodeData.toString() << "\n";
		 if (right != NULL) right->print();
   }

      int numLeafNodes() const {
         if (left == NULL && right == NULL) return 1;
         int numLeaf = 0;
         if (left != NULL) numLeaf += left->numLeafNodes();
         if (right != NULL) numLeaf += right->numLeafNodes();
         return numLeaf;
      }
      // overloaded dereference operator
      const dataType& operator * () const {
         return nodeData;
      }
};

#endif

bintree.h

#ifndef BINTREE_H_
#define BINTREE_H_
#include <stdexcept>
#include <math.h>
#include "binnode.h"

/********************************************************\

   template class for a binary tree

\********************************************************/

template <typename dataType> class bintree
{  
   private:
      binNode<dataType> *root;
      int numItems;
      
   public:
      /*******************************************************\

         constructors & destructors

      \*******************************************************/
      // constructor
      bintree() : root(NULL), numItems(0) {}
      
      // destructor
      ~bintree() {
         if (root != NULL) delete root;
      }

      /*******************************************************\

         misc functions

      \*******************************************************/

      bool empty() const {
         return (numItems == NULL);
      }

      int size() const {
         return numItems;
      }

      int numNodes() const {
         if (root == NULL) {
            return 0;
         } else {
            return root->numNodes();
         }
      }

      int maxTreeDepth() const {
         if (root == NULL) {
            return 0;
         } else {
            return root->maxTreeDepth();
         }
      }

      int numLeafNodes() const {
         if (root == NULL) {
            return 0;
         } else {
            return root->numLeafNodes();
         }
      }

      double balance() const {
         // Returns a measure of how balanced a tree is.
         // A value of 1 is a prefectly balanced tree.
         // The closer to 0 the value is the more unbalanced
         // the tree.
         // A value < 0.5 indicates a tree that is seriously unbalanced
         
         // case of no nodes in tree
         if (numItems == 0) return 1.0;
         
         // calculate balance
         double log2numItems = log10(numItems + 1) / log10(2);
         return log2numItems / maxTreeDepth() * (numLeafNodes() * 2) / (numItems + 1); 
      }

      void rebalance() {
         // Rebalance tree using the AVL algorithm
         // While this does not guarantee a perfectly balanced tree
         // it does make it mostly balanced by guranteeing that the diference
         // in depth between every right and left subtree is at most 1

         if (root != NULL) {
            while (root->rebalance(root));
         }
      }

      /*******************************************************\

         insertion and erasure functions

      \*******************************************************/

      void insert(const dataType& newData) {
         if (root == NULL) {
            root = new binNode<dataType>(newData);
         } else {
            root->insert(newData);
         }
         numItems++;
      }

      void erase(const dataType& delData) {
         if (root == NULL) {
            throw std::invalid_argument("data does not exist in tree to erase");
         }
         root->erase(&root, delData);
         numItems--;
      }

      dataType* find(const dataType &findData) const {
	     // this function looks for findData in ther tree.
		 // If it find the data it will return the address of the data in the tree
		 // otherwise it will return NULL
         if (root == NULL) return NULL;
         else return root->find(findData);
      }

      /*******************************************************\

         print function for assignment. 

		 assumes dataType has print() function 

      \*******************************************************/

	  void print() const {
	     if (root != NULL) root->print();
      }
};

#endif

here is the tree.cpp

#include <iostream>

#include "bintree.h"

using namespace std;

/* Small program to explore using binary trees.
   The program fills a tree with number in the order 1 to 16;
   It then prints some statistics about the tree
   It then rebalances the tree calling the rebalance function
   of bintree and then reprints the stats.
   
   Can you figure out what this tree looks like when first constructed?
   Can you figure out what balance value it could have if properly
   balanced?
*/ 

void fillTree(const bintree<int> &treeRoot);
void printTreeStats(const bintree<int> &treeRoot);

int main()
{
   bintree<int> treeRoot;

   printTreeStats(treeRoot);
   fillTree(treeRoot);
   treeRoot.rebalance();
   printTreeStats(treeRoot);

   return 0;
}

void fillTree(const bintree<int> &treeRoot)
{
   int *ptr;
   
   for (int i=1; i<16; i++) {
      ptr = new int(i);
      treeRoot.insert(*ptr);   //ERROR HAPPENS HERE
   }
}

void printTreeStats(const bintree<int> &treeRoot)
{
   cout << "Num nodes      = " << treeRoot.size() << "\n";
   cout << "Max tree depth = " << treeRoot.maxTreeDepth() << "\n";
   cout << "Num leaf nodes = " << treeRoot.numLeafNodes() << "\n";
   cout << "Tree balance   = " << treeRoot.balance() << "\n";
   
   printf("\n");
}

the error says:

tree.cpp: in function 'void fillTree(const bintree<int>&)':
tree.cpp:39: error: passing 'const bintree<int>' as 'this' argument of
void bintree<dataType>::insert(const dataType&) [with dataType = int]' discards qualifiers

I have been trying to debug it... but couldn't find it >.<
I'm new to tree data structure..

Any help will be appreciated

I think the problem is lines 18 and 33:

void fillTree(const bintree<int> &treeRoot);

By passing treeRoot into fillTree as a constant reference, what you're telling the compiler is that your function will not modify the contents of treeRoot....

As you are modifying the values held, this is the reason your compiler is complaining. If you declare the function passing an ordinary reference instead I.E.:

void fillTree(bintree<int> &treeRoot);

I think the error should go away!

Cheers for now,
Jas.

This article has been dead for over six months. Start a new discussion instead.