?
Solved

Function using recursion

Posted on 2005-04-26
8
Medium Priority
?
282 Views
Last Modified: 2011-04-14
I am in need of some assistance.  I have written this class, Tree, but it needs improvement.  Also, I want to create a member function size( ) that will determine how many entries a tree has, a member function min() that will find the smallest entry in the tree, and a member function max() that will find the largest entry in the tree.  I want to use recursion functions for these.  Lastly, after all these functions, I would like a member function called breadDisplay that will display the tree level by level.  CIAO.

Here is the class:

#include <iostream.h>
#include <stdlib.h>
using namespace std;

class Tree
{
   class TreeNode {
     public:
         TreeNode(int number,TreeNode *r, TreeNode *l);
         ~TreeNode();
          int number;
          TreeNode *right;
          TreeNode *left;
     
     };        
   public:
      Tree();
      ~Tree();
      void InsertNode(int newnumber);
      int tree_size(TreeNode *Tree);
      int TreeMin(TreeNode *Tree)
      int TreeMax(TreeNode *Tree)
      void searchtree() const;
   private:
     void InsertNodeHelper(TreeNode* &current, int newnumber);
     bool searchtreehelper(TreeNode *current, int findnumber) const;
     TreeNode *RootPtr;
};

// class definitions
   
void Tree::searchtree() const
{
  bool found;
  int searchnumber;
  cout << "Enter the number to be searched";
  cin >> searchnumber;
  found = searchtreehelper(RootPtr,searchnumber);
  if (found)
    cout << "The number you entered " << searchnumber << " was found in the list";
  else
     cout << "The number you entered " << searchnumber << " was not found in the list";
}

bool Tree::searchtreehelper(TreeNode *current, int findnumber) const
{
 if (current == NULL)
   return (false);
 else if (current->number == findnumber)
   return (true);
 else if (current->number > findnumber)
   return(searchtreehelper(current->left,findnumber));
 else if (current->number < findnumber)
   return(searchtreehelper(current->right,findnumber));
return(false);
}

Tree::Tree()
{
     cout << "Default constructor linklist" << endl;
     RootPtr = NULL;
}
Tree::~Tree()
{
       cout << "Tree destructor" << endl;
       if (RootPtr !=NULL)
       {
           delete RootPtr;
        }
}

int TreeSize(TreeNode *Tree)
{
        if (Tree==NULL) return 0;
        else return(1 + TreeSize(Tree->left) + TreeSize(Tree->right));
}

int TreeMin(TreeNode *Tree)
{

}

int TreeMax(TreeNode *Tree)
{
        int left, right;
        if (Tree==NULL) {
                return 0;
        } else {
                left = TreeMax(Tree->left);
                right = TreeMax(Tree->right);
                return(1 + (left > right ? left : right));
        }
}



Tree::TreeNode::TreeNode(int newnumber, TreeNode *r, TreeNode *l)
{
    // cout << "Default constructor student" << endl;
     number = newnumber;
     right = r;
     left = l;
}


Tree::TreeNode::~TreeNode()
{
       cout << "destructor student" << endl;
     if (right !=NULL)
        delete right;
     if (left !=NULL)
        delete left;
}



void Tree::InsertNode(int number)

{
   InsertNodeHelper(RootPtr,number);
}

void Tree::InsertNodeHelper(TreeNode* &current, int newnumber){
   
  if(current == NULL)
      current = new TreeNode(newnumber,NULL,NULL); //check space
   else if(newnumber > current->number)
      InsertNodeHelper(current->right,newnumber);
   else if(newnumber < current->number)
      InsertNodeHelper(current->left,newnumber);
   else
      cout << newnumber << " Is a duplicate " << endl;
}

// main functions

int main()
{
  Tree integers;
  int intval;
  cout << "Enter 10 integer values:\n";
  for (int i = 0; i < 10; i++)
    {
      cin >> intval;
      integers.InsertNode(intval);
    }
   cout << "The size of this tree is " << integers.size();
   cout << endl;
   cout << "The max value of this tree is " << integers.max();
   cout << endl;
   cout << "The min value of this tree is " << integers.min();
   cout << endl;
   cout << "The Bread Display of this tree is " << integers.breadDisplay();
   cout << endl;
   integers.searchtree();
   return 0;
    }
0
Comment
Question by:greyfacemagilicuty
  • 3
  • 2
  • 2
  • +1
8 Comments
 

Author Comment

by:greyfacemagilicuty
ID: 13872858
Do you need more information?
0
 
LVL 8

Expert Comment

by:novitiate
ID: 13872893
for min, max and size...

#include <iostream>
#include <stdlib.h>
using namespace std;


class Tree
{
public:
      class TreeNode {
      public:
            TreeNode(int number,TreeNode *r, TreeNode *l);
            ~TreeNode();
            int number;
            TreeNode *right;
            TreeNode *left;
            
      };        
public:
            Tree();
            ~Tree();
            void InsertNode(int newnumber);
            int size();
            int min();
            int max();
            void searchtree() const;
private:
            void InsertNodeHelper(TreeNode* &current, int newnumber);
            bool searchtreehelper(TreeNode *current, int findnumber) const;
            TreeNode *RootPtr;
};

// class definitions

void Tree::searchtree() const
{
      bool found;
      int searchnumber;
      cout << "Enter the number to be searched";
      cin >> searchnumber;
      found = searchtreehelper(RootPtr,searchnumber);
      if (found)
            cout << "The number you entered " << searchnumber << " was found in the list";
      else
            cout << "The number you entered " << searchnumber << " was not found in the list";
}

bool Tree::searchtreehelper(TreeNode *current, int findnumber) const
{
      if (current == NULL)
            return (false);
      else if (current->number == findnumber)
            return (true);
      else if (current->number > findnumber)
            return(searchtreehelper(current->left,findnumber));
      else if (current->number < findnumber)
            return(searchtreehelper(current->right,findnumber));
      return(false);
}

Tree::Tree()
{
      cout << "Default constructor linklist" << endl;
      RootPtr = NULL;
}
Tree::~Tree()
{
      cout << "Tree destructor" << endl;
      if (RootPtr !=NULL)
      {
            delete RootPtr;
      }
}

int TreeSize(Tree::TreeNode *Tree)
{
      if (Tree==NULL) return 0;
      else return(1 + TreeSize(Tree->left) + TreeSize(Tree->right));
}

int TreeMin(const Tree::TreeNode & Tree)
{
      Tree::TreeNode *node = (Tree::TreeNode*)&Tree;
      while(node->left) node = node->left;
      return node->number;      
}

int TreeMax(const Tree::TreeNode & Tree)
{
      Tree::TreeNode *node = (Tree::TreeNode*)&Tree;
      while(node->right) node = node->right;
      return node->number;      
}
void breadDisplay(Tree::TreeNode *Tree)
{
      if (Tree==NULL) return;
      cout << "\t";
      breadDisplay(Tree->right);
      cout << Tree->number << endl;
}

int Tree::size(){return TreeSize(RootPtr);}
int Tree::min(){return TreeMin(*RootPtr);}
int Tree::max(){return TreeMax(*RootPtr);}

Tree::TreeNode::TreeNode(int newnumber, TreeNode *r, TreeNode *l)
{
    // cout << "Default constructor student" << endl;
      number = newnumber;
      right = r;
      left = l;
}


Tree::TreeNode::~TreeNode()
{
      cout << "destructor student" << endl;
      if (right !=NULL)
        delete right;
      if (left !=NULL)
        delete left;
}



void Tree::InsertNode(int number)

{
      InsertNodeHelper(RootPtr,number);
}

void Tree::InsertNodeHelper(TreeNode* &current, int newnumber){
      
      if(current == NULL)
            current = new TreeNode(newnumber,NULL,NULL); //check space
      else if(newnumber > current->number)
            InsertNodeHelper(current->right,newnumber);
      else if(newnumber < current->number)
            InsertNodeHelper(current->left,newnumber);
      else
            cout << newnumber << " Is a duplicate " << endl;
}

// main functions

int main()
{
      Tree integers;
      int intval;
      cout << "Enter 10 integer values:\n";
      for (int i = 0; i < 10; i++)
    {
            cin >> intval;
            integers.InsertNode(intval);
    }
      cout << "The size of this tree is " << integers.size();
      cout << endl;
      cout << "The max value of this tree is " << integers.max();
      cout << endl;
      cout << "The min value of this tree is " << integers.min();
      cout << endl;
      
      integers.searchtree();
      return 0;
}

_novi_
0
 

Author Comment

by:greyfacemagilicuty
ID: 13872968
thanks novi.  however the breadDisplay is confusing to me.  after it gives me the size, min, and max, it asks for a number to be searched.  when i complete this it says it has found the number, and than repeats destructor number over and over.  the function I would like is the breadDisplay that will display the tree level by level.  i hope you can help me and if so the 500 points are all yours.
0
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.

 
LVL 8

Accepted Solution

by:
novitiate earned 2000 total points
ID: 13873735
Tree::TreeNode::~TreeNode()
{
//cout << "destructor student" << endl;
      if (right !=NULL)
        delete right;
      if (left !=NULL)
        delete left;
}

_novi_
0
 
LVL 10

Expert Comment

by:Sys_Prog
ID: 13877683
Go thru my posts in this link

http://experts-exchange.com/Programming/Programming_Languages/Cplusplus/Q_21400356.html

This is exactly what u want - breadthwise printing of Tree


Amit
0
 
LVL 10

Expert Comment

by:Sys_Prog
ID: 13878131
greyfacemagilicuty,

Did u need the breadthdisplay function or not
Did u get it from novi's reply

Amit
0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
ID: 13878564
TreeMin and TreeMax are not recursive til now and for any reason they are not member functions of class Tree (also TreeSize), but they should. I also changed the argument from pointer to reference and renamed the 'Tree' argument to 'node' as some compilers wouldn't accept a variable having the same name as a class.

I worked some time to get tree output. I needed to turn the tree by -90°, cause it is to difficult to traverse level by level but easy to make preorder traverse.

Finally that's my code:

#include <iostream>
#include <stdlib.h>
using namespace std;


class Tree
{
public:
    class TreeNode {
    public:
        TreeNode(int number,TreeNode *r, TreeNode *l);
        ~TreeNode();
        int number;
        TreeNode *right;
        TreeNode *left;
       
    };        
    public:
        Tree();
        ~Tree();
        void InsertNode(int newnumber);
        int depth() const;
        int size() const;
        int minimum() const;
        int maximum() const;
        void searchtree() const;
        void display() const;
    private:
        void InsertNodeHelper(TreeNode* &current, int newnumber);
        bool searchtreehelper(TreeNode *current, int findnumber) const;
        int  TreeDepth(const Tree::TreeNode& node) const;
        int  TreeSize(const TreeNode& node) const;
        int  TreeMin(const TreeNode& node) const;
        int  TreeMax(const TreeNode& node) const;  
        void breadDisplay(Tree::TreeNode* pNode, int offset) const;
       
        TreeNode *RootPtr;
};

// class definitions

void Tree::searchtree() const
{
    bool found;
    int searchnumber;
    cout << "Enter the number to be searched ==> ";
    cin >> searchnumber;
    found = searchtreehelper(RootPtr,searchnumber);
    if (found)
        cout << "The number you entered " << searchnumber << " was found in the list" << endl;
    else
        cout << "The number you entered " << searchnumber << " was not found in the list" << endl;
}

bool Tree::searchtreehelper(TreeNode *current, int findnumber) const
{
    if (current == NULL)
        return (false);
    else if (current->number == findnumber)
        return (true);
    else if (current->number > findnumber)
        return(searchtreehelper(current->left,findnumber));
    else if (current->number < findnumber)
        return(searchtreehelper(current->right,findnumber));
    return(false);
}

Tree::Tree()
{
    cout << "Default constructor linklist" << endl;
    RootPtr = NULL;
}
Tree::~Tree()
{
    if (RootPtr !=NULL)
    {
        delete RootPtr;
    }
}

int Tree::TreeDepth(const Tree::TreeNode& node) const
{
    if (node.left == NULL && node.right == NULL)
        return 1;
    else if (node.left == NULL)
        return (1 + TreeDepth(*node.right));
    else if (node.right == NULL)
        return (1 + TreeDepth(*node.left));
    else
    {
        int dl = TreeDepth(*node.left);
        int dr = TreeDepth(*node.right);
        return (dl < dr)? dr + 1 : dl + 1;
    }
}

int Tree::TreeSize(const Tree::TreeNode& node) const
{
    if (node.left == NULL && node.right == NULL)
        return 1;
    else if (node.left == NULL)
        return (1 + TreeSize(*node.right));
    else if (node.right == NULL)
        return (1 + TreeSize(*node.left));
    else
        return (1 + TreeSize(*node.left) + TreeSize(*node.right));
}


int Tree::TreeMin(const Tree::TreeNode & node) const
{
    if (node.left == NULL)
        return node.number;
    return TreeMin(*node.left);    
}

int Tree::TreeMax(const Tree::TreeNode & node) const
{
    if (node.right == NULL)
        return node.number;
    return TreeMax(*node.right);    
}

void Tree::breadDisplay(Tree::TreeNode* pNode, int offset) const
{
    if (pNode == NULL)
        return;
    breadDisplay(pNode->left, offset+1);
    for (int i = 0; i < offset; ++i)
        cout << "\t";
    cout << pNode->number << endl;
    breadDisplay(pNode->right, offset+1);
}

int Tree::depth() const
{
    return (RootPtr == NULL)? 0 : TreeDepth(*RootPtr);
}

int Tree::size() const
{
    return (RootPtr == NULL)? 0 : TreeSize(*RootPtr);
}

int Tree::minimum() const
{
    return (RootPtr == NULL)? 0 : TreeMin(*RootPtr);
}

int Tree::maximum() const
{
    return (RootPtr == NULL)? 0 : TreeMax(*RootPtr);
}

Tree::TreeNode::TreeNode(int newnumber, TreeNode *r, TreeNode *l)
{
    // cout << "Default constructor student" << endl;
    number = newnumber;
    right = r;
    left = l;
}


Tree::TreeNode::~TreeNode()
{
    cout << "destructor student" << endl;
    if (right !=NULL)
        delete right;
    if (left !=NULL)
        delete left;
}



void Tree::InsertNode(int number)

{
    InsertNodeHelper(RootPtr, number);
}          

void Tree::InsertNodeHelper(TreeNode* &current, int newnumber){
   
    if(current == NULL)
        current = new TreeNode(newnumber,NULL,NULL); //check space
    else if(newnumber > current->number)
        InsertNodeHelper(current->right,newnumber);
    else if(newnumber < current->number)
        InsertNodeHelper(current->left,newnumber);
    else
        cout << newnumber << " Is a duplicate " << endl;
}

void Tree::display() const
{
    breadDisplay(RootPtr, 0);
}
// main functions

int main()
{
    Tree integers;
    int intval;
    cout << "Enter 10 integer values:\n";
    for (int i = 0; i < 10; i++)
    {
        cin >> intval;
        integers.InsertNode(intval);
    }
    cout << "The size of this tree is " << integers.size();
    cout << endl;
    cout << "The max value of this tree is " << integers.maximum();
    cout << endl;
    cout << "The min value of this tree is " << integers.minimum();
    cout << endl;
   
    integers.searchtree();
    integers.searchtree();
   
    integers.display();
    return 0;
}

Regards, Alex
0
 

Author Comment

by:greyfacemagilicuty
ID: 13881420
Thanks for all your help.  I'm trying to teach myself Btree now.  I would like to set up pretty much the same program.  I would like to try one function using recursion with size() that will determine how many Nodes the Btree has.  I would like two functions for min() and max().  And lastly, a size() function.  All of these should be set-up with recursion.  Also, I haven't put in a main function but it should execute based on the definition of each of the 3 functions.  Thanks.

#include <fstream>
#include <iostream>
using namespace std;

class BTree
{public:
  static const int N=1;
private:
  class BNode
  {public:
    BNode(const int &t,int sz=1,BNode * ch=NULL);
    int size;
    int data[2*N+1];
    BNode *child[2*N+2];
  };
public:
  BTree();
  ~BTree();
  void add(const int & t);
  void display(ostream &out);
private:
  BNode *root;   //IMPORTANT: root points to an empty node whose 0th
  //               child points to the actual tree.

  static void add(const int & t,BNode *&rt);
  static void display(ostream &out,BNode *rt,char * indent="    ",int
                  deep=0);
  static void kill(BNode *&rt);
  static void split(BNode *&rt,int loc);
  static int findLoc(BNode *rt,const int &t);
};

int main()
{int x[]={2, 5, 8, 27, 13, 14, 89, -9, 18, 193, 4,90,0,1};
 BTree t;
 for(int j=0;j<14;j++)
  {t.add(x[j]);
  cout<<"Adding "<<x[j]<<endl;
  t.display(cout);
  }

}


BTree::BNode::BNode(const int &number,int sz,BNode * ch)
{size=sz;
 data[0]=number;
 child[0]=ch;
 for(int j=1;j<2*N+2;j++)
   child[j]=NULL;
}


BTree::BTree()
{int temp; //dummy entry
root=new BNode(temp,0);
if (root == NULL){
   cout << "No more Memory";
   exit(1);
}

}


BTree::~BTree(){kill(root);}


void BTree::kill(BNode *&rt)
{if(rt!=NULL)
  for(int j=0; j<=rt->size;j++)
    kill(rt->child[j]);
 delete rt;
 rt=NULL;
}


void BTree::add(const int & number)
{add(number,root);
 if(root->size>0)
   {int temp;
    root=new BNode(temp,0,root);
    if (root == NULL){
        cout << "No more Memory";
        exit(1);
   }
}
}

void BTree::add(const int & number,BNode *&rt)
{int loc;
 loc=findLoc(rt,number); //find place before which number belongs (insertion sort)
 if(rt->child[0]==NULL)//leaf
    {for(int j=rt->size;j>loc;j--)
      rt->data[j]=rt->data[j-1];
     rt->data[loc]=number;
     rt->size++;
    }
 else
   {add(number,rt->child[loc]);
    if(rt->child[loc]->size>=2*N+1)
      split(rt,loc);
   }
}

int BTree::findLoc(BNode *rt,const int &number)
{int loc;
 loc=0;
 while(loc < rt->size && number > rt->data[loc])
   loc++;
 return loc;
}


void BTree::split(BNode *&rt,int loc)
{BNode *temp;
 int number;
 temp=new BNode(number);
 if (temp == NULL)
 {
        cout << "No more Memory";
        exit(1);
 }
  temp->child[N]=rt->child[loc]->child[2*N+1];
 
 for(int j=N+1;j<2*N+1;j++)//copy right side of overfull child
   {temp->child[j-N-1]=rt->child[loc]->child[j];
   rt->child[loc]->child[j]=NULL;
   temp->data[j-N-1]=rt->child[loc]->data[j];
   temp->size=N;
   }
   
 number=rt->child[loc]->data[N]; //save mid-most datum
 
 for(int j=rt->size+1; j>loc+1; j--)
   {rt->child[j]=rt->child[j-1];
    rt->data[j-1]=rt->data[j-2];
   }
   
 rt->child[loc]->size=N;
 rt->data[loc]=number;
 rt->child[loc+1]=temp;
 rt->size++;
}

void BTree::display(ostream &out)
{display(out,root);}


void BTree::display(ostream &out,BNode *rt,char * indent,int deep)
{if(rt!=NULL)
  {for(int j=0; j<rt->size;j++)
    {display(out,rt->child[j],indent,deep+1);
     for(int k=0;k<10-deep;k++)
       out<<indent;
     out<<rt->data[j]<<endl;
    }
  display(out,rt->child[rt->size],indent,deep+1);
  }
}
0

Featured Post

[Webinar] Cloud and Mobile-First Strategy

Maybe you’ve fully adopted the cloud since the beginning. Or maybe you started with on-prem resources but are pursuing a “cloud and mobile first” strategy. Getting to that end state has its challenges. Discover how to build out a 100% cloud and mobile IT strategy in this webinar.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Written by John Humphreys C++ Threading and the POSIX Library This article will cover the basic information that you need to know in order to make use of the POSIX threading library available for C and C++ on UNIX and most Linux systems.   [s…
Introduction This article is the first in a series of articles about the C/C++ Visual Studio Express debugger.  It provides a quick start guide in using the debugger. Part 2 focuses on additional topics in breakpoints.  Lastly, Part 3 focuses on th…
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.
Suggested Courses

839 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question