Function using recursion

Do you need more information?

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_

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.

Go thru my posts in this link

https://www.experts-exchange.com/questions/21400356/question-on-binary-tree-search.html

This is exactly what u want - breadthwise printing of Tree


Amit

greyfacemagilicuty,

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

Amit

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

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