// For question 4 you are to write 4 functions // 1 - Find the largest value in
ID: 3770646 • Letter: #
Question
// For question 4 you are to write 4 functions // 1 - Find the largest value in the tree for an ORDERED TREE // Your algorithm MUST use the fact that the tree is ordered // The answer will be returned through the function call // char largestOrdered( TreeNode * ); // 2 - Find the largest value in a tree that is NOT ordered // The answer will be returned through the function call // char largestNoOrder( TreeNode * ); // //******************************************************************* // A right child is a node (other than the root) that is // pointed to by the right link of the parent node //******************************************************************* // 3 - Find the number of right children in a tree. // The answer will be placed in an alias parameter // void numberRightChildren( TreeNode *, int &); // // 4 - Find the number of right children in a tree. // The answer will be return through the function call // int numberRightChildren( TreeNode *); // NOTE: functions 3 and 4 can NOT call the the other function // You should get the following output: /* The largest value in the ordered tree is u The largest value in the unordered tree is w The number of right children in the unordered tree using ALIAS is 4 The number of right children in the ordered tree using ALIAS is 5 The number of right children in the unordered tree is 4 The number of right children in the ordered tree is 5 */ #include <iostream> using namespace::std; struct TreeNode { char data; TreeNode * lLink; TreeNode * rLink; TreeNode( char, TreeNode *, TreeNode * ); }; TreeNode::TreeNode( char someChar, TreeNode * leftPtr, TreeNode * rightPtr ) { data = someChar; lLink = leftPtr; rLink = rightPtr; } void AppendLeft( TreeNode * ptr, char someChar ) { ptr->lLink = new TreeNode(someChar, NULL, NULL); } void AppendRight( TreeNode * ptr, char someChar ) { ptr->rLink = new TreeNode(someChar, NULL, NULL); } TreeNode * LChild( TreeNode * ptr ) { return (ptr==NULL) ? NULL : ptr->lLink; } TreeNode * RChild( TreeNode * ptr ) { return (ptr==NULL) ? NULL : ptr->rLink; } void deleteAll( TreeNode * p) { if ( p == NULL ) return; deleteAll(LChild(p)); deleteAll(RChild(p)); delete p; } TreeNode * add( TreeNode * & t, char c); // ordered tree void inOrderPrint(ostream &,TreeNode *); // Instructor Written // ***************** STUDENT WRITTEN ****************************** char largestOrdered( TreeNode * ); // STUDENT WRITTEN // return '' for an empty tree char largestNoOrder( TreeNode * ); // STUDENT WRITTEN // return '' for an empty tree void numberRightChildren( TreeNode * p, int &); // STUDENT WRITTEN int numberRightChildren( TreeNode * p); // STUDENT WRITTEN void q4() { cout << " QUESTION 4 STARTING**********" << endl; TreeNode * tr = NULL; char message[] ="beansoup"; for( int i = 0; message[i]; i++) add(tr,message[i]); cout << "The largest value in the ordered tree is " << largestOrdered(tr) << endl; // an unordered tree TreeNode * tree = NULL; tree = new TreeNode('r',NULL,NULL); AppendLeft(tree, 'h'); AppendRight(tree,'t'); AppendLeft(LChild(tree), 'c'); AppendRight(LChild(tree), 'w'); AppendRight(RChild(tree), 'e'); AppendLeft(RChild(RChild(tree)), 'r'); AppendRight(RChild(RChild(tree)), 'b'); /* ASSERT: tree contents appear as follows: */ /* */ /* 'r' */ /* / */ /* 'h' 't' */ /* / */ /* 'c' 'w' 'e' */ /* / */ /* 'r' 'b' */ cout << "The largest value in the unordered tree is " << largestNoOrder(tree) << endl; int count = 0; numberRightChildren(tree, count); cout << "The number of right children in the unordered tree using ALIAS is " << count << endl; count = 0; numberRightChildren(tr, count); cout << "The number of right children in the ordered tree using ALIAS is " << count << endl; cout << "The number of right children in the unordered tree is " << numberRightChildren(tree) << endl; cout << "The number of right children in the ordered tree is " << numberRightChildren(tr) << endl; deleteAll(tree); deleteAll(tr); return; } char largestOrdered( TreeNode * p) // STUDENT WRITTEN { // return '' for an empty tree return 'a'; // ONLY HERE TO GET THE PROGRAM TO COMPILE } char largestNoOrder( TreeNode * p ) // STUDENT WRITTEN { // return '' for an empty tree return 'a'; // ONLY HERE TO GET THE PROGRAM TO COMPILE } void numberRightChildren( TreeNode * p, int & c) // STUDENT WRITTEN { } int numberRightChildren( TreeNode * p) // STUDENT WRITTEN { return -1; // ONLY HERE TO GET THE PROGRAM TO COMPILE } // *********************************************************************** // FUNCTIONS BELOW WERE WRITTEN BY THE INSTRUCTOR TreeNode * add( TreeNode * & t, char c) // ordered tree { if ( t == NULL ) { t = new TreeNode(c,NULL,NULL); return t; } TreeNode * walker = t; while (true) { if ( c == walker->data) { return NULL; } if ( c < walker->data ) { if ( LChild(walker) == NULL ) { AppendLeft(walker,c); return LChild(walker); } else { walker = LChild(walker); } } else { // I know that c is larger if ( RChild(walker) == NULL) { AppendRight(walker,c); return RChild(walker); } else { walker = RChild(walker); } } } } void inOrderPrint(ostream & w,TreeNode * p) { // arrive from above if ( p == NULL) return; inOrderPrint(w,LChild(p)); // come back from the left child w << p->data << ' ' ; inOrderPrint(w,RChild(p)); // come back from the right child return; }
Explanation / Answer
// For question 4 you are to write 4 functions
// 1 - Find the largest value in the tree for an ORDERED TREE
// Your algorithm MUST use the fact that the tree is ordered
// The answer will be returned through the function call
// char largestOrdered( TreeNode * );
// 2 - Find the largest value in a tree that is NOT ordered
// The answer will be returned through the function call
// char largestNoOrder( TreeNode * );
//
//*******************************************************************
// A right child is a node (other than the root) that is
// pointed to by the right link of the parent node
//*******************************************************************
// 3 - Find the number of right children in a tree.
// The answer will be placed in an alias parameter
// void numberRightChildren( TreeNode *, int &);
//
// 4 - Find the number of right children in a tree.
// The answer will be return through the function call
// int numberRightChildren( TreeNode *);
// NOTE: functions 3 and 4 can NOT call the the other function
// You should get the following output:
/*
The largest value in the ordered tree is u
The largest value in the unordered tree is w
The number of right children in the unordered tree using ALIAS is 4
The number of right children in the ordered tree using ALIAS is 5
The number of right children in the unordered tree is 4
The number of right children in the ordered tree is 5
*/
#include <iostream>
using namespace::std;
struct TreeNode {
char data;
TreeNode * lLink;
TreeNode * rLink;
TreeNode( char, TreeNode *, TreeNode * );
};
TreeNode::TreeNode( char someChar, TreeNode * leftPtr, TreeNode * rightPtr )
{
data = someChar; lLink = leftPtr; rLink = rightPtr;
}
void AppendLeft( TreeNode * ptr, char someChar )
{
ptr->lLink = new TreeNode(someChar, NULL, NULL);
}
void AppendRight( TreeNode * ptr, char someChar )
{
ptr->rLink = new TreeNode(someChar, NULL, NULL);
}
TreeNode * LChild( TreeNode * ptr )
{
return (ptr==NULL) ? NULL : ptr->lLink;
}
TreeNode * RChild( TreeNode * ptr )
{
return (ptr==NULL) ? NULL : ptr->rLink;
}
void deleteAll( TreeNode * p)
{
if ( p == NULL ) return;
deleteAll(LChild(p));
deleteAll(RChild(p));
delete p;
}
TreeNode * add( TreeNode * & t, char c); // ordered tree
void inOrderPrint(ostream &,TreeNode *); // Instructor Written
// ***************** STUDENT WRITTEN ******************************
char largestOrdered( TreeNode * ); // STUDENT WRITTEN
// return '' for an empty tree
char largestNoOrder( TreeNode * ); // STUDENT WRITTEN
// return '' for an empty tree
void numberRightChildren( TreeNode * p, int &); // STUDENT WRITTEN
int numberRightChildren( TreeNode * p); // STUDENT WRITTEN
void q4()
{
cout << " QUESTION 4 STARTING**********" << endl;
TreeNode * tr = NULL;
char message[] ="beansoup";
for( int i = 0; message[i]; i++)
add(tr,message[i]);
cout << "The largest value in the ordered tree is "
<< largestOrdered(tr) << endl;
// an unordered tree
TreeNode * tree = NULL;
tree = new TreeNode('r',NULL,NULL);
AppendLeft(tree, 'h');
AppendRight(tree,'t');
AppendLeft(LChild(tree), 'c');
AppendRight(LChild(tree), 'w');
AppendRight(RChild(tree), 'e');
AppendLeft(RChild(RChild(tree)), 'r');
AppendRight(RChild(RChild(tree)), 'b');
/* ASSERT: tree contents appear as follows: */
/* */
/* 'r' */
/* / */
/* 'h' 't' */
/* / */
/* 'c' 'w' 'e' */
/* / */
/* 'r' 'b' */
cout << "The largest value in the unordered tree is "
<< largestNoOrder(tree) << endl;
int count = 0;
numberRightChildren(tree, count);
cout << "The number of right children in the unordered tree using ALIAS is "
<< count << endl;
count = 0;
numberRightChildren(tr, count);
cout << "The number of right children in the ordered tree using ALIAS is "
<< count << endl;
cout << "The number of right children in the unordered tree is " <<
numberRightChildren(tree) << endl;
cout << "The number of right children in the ordered tree is " <<
numberRightChildren(tr) << endl;
deleteAll(tree);
deleteAll(tr);
return;
}
char largestOrdered( TreeNode * p) // STUDENT WRITTEN
{ // return '' for an empty tree
TreeNode* walker = p;
if(p == NULL)
return '';
if(RChild(p) == NULL)
return p->data;
return largestOrdered(RChild(p));
}
char largestNoOrder( TreeNode * p ) // STUDENT WRITTEN
{ // return '' for an empty tree
if(p==NULL)
return '';
char c_root = p->data;
char c_left = largestNoOrder(LChild(p));
char c_right = largestNoOrder(RChild(p));
if(c_root>=c_left&&c_root>=c_right)
return c_root;
if(c_left>=c_root&&c_left>=c_right)
return c_left;
if(c_right>=c_root&&c_right>=c_left)
return c_right;
}
void numberRightChildren( TreeNode * p, int & c) // STUDENT WRITTEN
{
if(p == NULL)
return;
else
{
c = c+1;
numberRightChildren(RChild(p),c);
}
}
int numberRightChildren( TreeNode * p) // STUDENT WRITTEN
{
if(p == NULL)
return 0;
else
return 1+numberRightChildren( RChild(p) );
return -1; // ONLY HERE TO GET THE PROGRAM TO COMPILE
}
// ***********************************************************************
// FUNCTIONS BELOW WERE WRITTEN BY THE INSTRUCTOR
TreeNode * add( TreeNode * & t, char c) // ordered tree
{
if ( t == NULL )
{
t = new TreeNode(c,NULL,NULL);
return t;
}
TreeNode * walker = t;
while (true)
{
if ( c == walker->data)
{
return NULL;
}
if ( c < walker->data )
{
if ( LChild(walker) == NULL )
{
AppendLeft(walker,c);
return LChild(walker);
}
else
{
walker = LChild(walker);
}
}
else
{
// I know that c is larger
if ( RChild(walker) == NULL)
{
AppendRight(walker,c);
return RChild(walker);
}
else
{
walker = RChild(walker);
}
}
}
}
void inOrderPrint(ostream & w,TreeNode * p)
{
// arrive from above
if ( p == NULL) return;
inOrderPrint(w,LChild(p));
// come back from the left child
w << p->data << ' ' ;
inOrderPrint(w,RChild(p));
// come back from the right child
return;
}
int main()
{
q4();
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.