MTH4300 Home

Binary Search Tree

The main ingredient of the tree is a node that has 3 components. The first component is the content that maintains the data. The other two components are pointers that contains the addresses of the left child and right child. We will denote these two addresses by aLeft and aRight.

Our goal is to make it easy to search for values in the tree. We will make sure that for each node, its content is bigger than the content of every node in the the left sub-tree. Similarly, the content of each node will be smaller than the contents of the nodes in the right sub-tree.

We will create an example in which the components of the tree are fractions. First we will create a class fraction that has two private attributes: numerator and denominator. The class must have the public method operator< that would allow us to compare contents of different nodes.

class Frac{
private:
   long num; long den;
public:
   Frac(const long& =0, const long& =1);
   long getNum() const; long getDen() const;
   void setNum(const long &);
   void setDen(const long &);
   int operator< (const Frac& ) const;
};
Frac::Frac(const long & n, const long &d){
   num=n;den=d;
   if(den==0){den=1;}
   if(den<0){den*=-1;num*=-1;}
}
long Frac::getNum() const{return num;}
   long Frac::getDen() const{return den;}
   void Frac::setNum(const long &n){num=n;}
   void Frac::setDen(const long &d){
   den=d;
   if(den==0){den=1;}
   if(den<-1){num*=-1;den*=-1;}
}
int Frac::operator< (const Frac & b) const{
   if(num*(b.den) < den*(b.num)){return 1;}
   return 0;
}

Implementation of the Tree

Now that we have created the class Frac we can implement the tree.