Solved

# Function using recursion

Posted on 2005-04-26
Medium Priority
282 Views
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
Question by:greyfacemagilicuty
• 3
• 2
• 2
• +1

Author Comment

ID: 13872858
0

LVL 8

Expert Comment

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;
}
{
if (Tree==NULL) return;
cout << "\t";
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

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

LVL 8

Accepted Solution

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

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

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

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;
for (int i = 0; i < offset; ++i)
cout << "\t";
cout << pNode->number << endl;
}

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
{
}
// 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

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

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
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

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
Course of the Month14 days, 22 hours left to enroll