Cannot use cstdlib!! Note -- I have already completed a-h; I am having trouble p

Question

Cannot use cstdlib!! Note -- I have already completed a-h; I am having trouble printing the subtrees (it just reprints the whoe tree no matter what I have tried). My current code is pasted after the input numbers
Input file numbers:

141
117
134
500
369
524
328
208
512
264
405
345
431
277
161
395
342
427
136
541
304
402
253
392
332
421
366
468
195
147
226
471
388
169
212
299
485
544
453
511
372
283
223
391
218
447
294
362
457
337
359
273
179
428
266
435
240
142
506
140
492
464
248
546
505
529
170
150
256
151
193
498
379
123
334
254
406
116
276
531
308
394
139
426
173
237
488
382
441
433
165
239
508
130
127
156
436
171
495
474
272
520
327
373
247
412
236
340
261
286
355
374
452
450
350
224
380
157
107
187
257
403
133
459
408
238
222
296
530
313
100
291
410
159
274
387
245
102
491
336
320
196
271
448
349
418
284
281
153
138

current code completed:

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

ifstream inFile;
ofstream outFile("treeResults.txt");
//Create struct
struct treeNode
{
   treeNode *leftChild;
   treeNode *rightChild;
   int data;
};
treeNode *root;

//Global Variables
int deepLevel = 0;       //Used in deepNode function
int deepValue = 0;       //used in deepNode function
int nodeCount = 0;       //used in insert function to count while inserting.
                       //This only works if no nodes will be deleted - nothing deleted in this code

//return true or false if root is empty/not empty
bool isempty()
{
   return root == NULL;
}
//insert values into tree
void insert(int val)
{
   treeNode *t = new treeNode;
   treeNode *parent;
   t->data = val;
   t->leftChild = NULL;
   t->rightChild = NULL;
   parent = NULL;
   if (isempty())
   {
       root = t;
       nodeCount += 1;
   }
   else
   {
       nodeCount += 1;
       treeNode *current = root;
       while (current)
       {
           parent = current;
           if (t->data > current->data)
           {
               current = current->rightChild;
           }
           else
           {
               current = current->leftChild;
           }
       }
       //insert node
       if (t->data < parent->data)
       {
           parent->leftChild = t;
       }
       else
       {
           parent->rightChild = t;
       }
   }
}
/*******************************/
//read in numbers from treeData file
void readFile()
{
   inFile.open("TreeRandNbrs.dat");
   int val;
   while (!inFile.eof())
   {
       inFile >> val;
       insert(val);
   }
   inFile.close();
}
/*******************************/
//print tree in order
void inOrder(treeNode *p) //p = parent
{
   int count = 0;
   if (p != NULL)
   {
       if (p->leftChild)
           inOrder(p->leftChild);
       outFile << " " << p->data << " ";
       if (p->rightChild)
           inOrder(p->rightChild);
   }
}
/*******************************/
//Print in Pre-order
void preOrder(treeNode *p)
{
   int count = 0;
   if (p != NULL)
   {
       outFile << " " << p->data << " ";
       if (p->leftChild)
           preOrder(p->leftChild);
       if (p->rightChild)
           preOrder(p->rightChild);
   }
}
/*******************************/
//Print Post Order
void postOrder(treeNode *p)
{
   int count = 0;
   if (p != NULL)
   {
       if (p->leftChild)
           preOrder(p->leftChild);
       count++;
       if (p->rightChild)
           preOrder(p->rightChild);
       outFile << " " << p->data << " ";
   }
}
/*******************************/
//Get sum of numbers in tree
int getSum(treeNode *p)
{
   if (p == NULL)
       return 0;
   else
       return p->data + getSum(p->leftChild) + getSum(p->rightChild);
}
/*******************************/
//Find the deepest Node in the tree
void deepNode(treeNode *p, int depth)
{
   if (p != NULL)
   {
       deepNode(p->rightChild, ++depth);
       if (depth > deepLevel)
       {
           deepValue = p->data;
           deepLevel = depth;
       }
       deepNode(p->leftChild, depth);
   }
}
/*******************************/
//count leaves
int countLeaves(treeNode *p)
{
   if (p == NULL)
       return 0;
   if (p->leftChild == NULL && p->rightChild == NULL)
       return 1;
   else
       return countLeaves(p->leftChild) + countLeaves(p->rightChild);
}
/*******************************/
//Find and print nodes with only one child
int oneChild(treeNode *p)
{
   if (p == NULL)
       return 0;
   if ((p->leftChild != NULL && p->rightChild == NULL) || (p->leftChild == NULL && p->rightChild != NULL))
       return 1;
   else
       return countLeaves(p->leftChild) + countLeaves(p->rightChild);

}
/*******************************/
//Print out the subtree of node value 299 in inorder

/***************************MAIN***************************/
int main()
{
   //declare variables
   int sum = 0,
       leafCount = 0,
       singleChild = 0;

   //read in file
   readFile();
   //In-Order print
   outFile << "Printing in order " << endl;
   inOrder(root);
   outFile << endl;
   //Pre-Order Print
   outFile << "Printing in PreOrder" << endl;
   preOrder(root);
   outFile << endl;
   //Post Order Print
   outFile << "Printing in Post Order" << endl;
   postOrder(root);
   outFile << endl;
   //Print number of nodes in tree
   outFile << "Number of Nodes = " << nodeCount << endl;
   //find and print sum and average
   sum = getSum(root);
   outFile << "The sum of the numbers in the tree is " << sum << " and the average is: " << (sum / nodeCount) << endl;
   //Find and print the value of the deepest root
   deepNode(root, 0);
   outFile << "The value that is deepest in the tree is: " << deepValue << endl;
   //Print number of nodes with one child
    leafCount = countLeaves(root);
   singleChild = oneChild(root);
   outFile << "The number of nodes with only one child is " << singleChild << endl;

    outFile.close();
   return 0;
}

Tree Work Out Write a program to read in as set of numbers and build an ordered binary tree. For the given tree compute and print the followin,g a. Print out the tree in inorder (Print the first 20 values) b. Print out the tree in preorder. (Print the first 20 values) c. Print out the tree in postorder. (Print the first 20 values) d. Print out the number of nodes in the tree. (Traverse the tree and count the nodes) e. Sum up all the values in the tree and compute the average. Print sum and average. f. Count the number of leafs in the tree g. Print the value that is the deepest down in the tree h. Print the number of nodes that have only one (1) child i. Print out the subtree of node value 299 (299 being the root of subtree) in inorder j. Print out the right subtree of node value 253 (again root) in postorder. k. Print the number of nodes that are to the left of the root & the number of nodes to the right of the root Label all output.

Explanation / Answer

#include<iostream>
#include<fstream>
#include<iomanip>
using namespace std;
ifstream inFile;
ofstream outFile("treeResults.txt");
//Create struct
struct treeNode
{
treeNode *leftChild;
treeNode *rightChild;
int data;
};
treeNode *root;
//Global Variables
int deepLevel = 0; //Used in deepNode function
int deepValue = 0; //used in deepNode function
int nodeCount = 0; //used in insert function to count while inserting.
//This only works if no nodes will be deleted - nothing deleted in this code
//return true or false if root is empty/not empty
bool isempty()
{
return root == NULL;
}
//insert values into tree
void insert(int val)
{
treeNode *t = new treeNode;
treeNode *parent;
t->data = val;
t->leftChild = NULL;
t->rightChild = NULL;
parent = NULL;
if (isempty())
{
root = t;
nodeCount += 1;
}
else
{
nodeCount += 1;
treeNode *current = root;
while (current)
{
parent = current;
if (t->data > current->data)
{
current = current->rightChild;
}
else
{
current = current->leftChild;
}
}
//insert node
if (t->data < parent->data)
{
parent->leftChild = t;
}
else
{
parent->rightChild = t;
}
}
}
/*******************************/
//read in numbers from treeData file
void readFile()
{
inFile.open("TreeRandNbrs.dat");
int val;
while (!inFile.eof())
{
inFile >> val;
insert(val);
}
inFile.close();
}
/*******************************/
//print tree in order
void inOrder(treeNode *p) //p = parent
{
int count = 0;
if (p != NULL)
{
if (p->leftChild)
inOrder(p->leftChild);
outFile << " " << p->data << " ";
if (p->rightChild)
inOrder(p->rightChild);
}
}
/*******************************/
//print tree in order of node value 299
void findAndInorder(treeNode *p,int val) //p = parent
{
treeNode *temp = new treeNode;
temp = p;
// Run the loop untill temp points to a NULL pointer.
while(temp != NULL)
{
if(temp->data == val)
{
inOrder(temp);
return;
}
// Shift pointer to left child.
else if(temp->data > val)
temp = temp->leftChild;
// Shift pointer to right child.
else
temp = temp->rightChild;
}
cout<<" Data not found";
return;
}
/*******************************/
//Print in Pre-order
void preOrder(treeNode *p)
{
int count = 0;
if (p != NULL)
{
outFile << " " << p->data << " ";
if (p->leftChild)
preOrder(p->leftChild);
if (p->rightChild)
preOrder(p->rightChild);
}
}
/*******************************/
//Print Post Order
void postOrder(treeNode *p)
{
int count = 0;
if (p != NULL)
{
if (p->leftChild)
preOrder(p->leftChild);
count++;
if (p->rightChild)
preOrder(p->rightChild);
outFile << " " << p->data << " ";
}
}
//print tree post order of node value 253
void findAndPostorder(treeNode *p,int val) //p = parent
{
treeNode *temp = new treeNode;
temp = p;
// Run the loop untill temp points to a NULL pointer.
while(temp != NULL)
{
if(temp->data == val)
{
postOrder(temp);
return;
}
// Shift pointer to left child.
else if(temp->data > val)
temp = temp->leftChild;
// Shift pointer to right child.
else
temp = temp->rightChild;
}
cout<<" Data not found";
return;
}
/*******************************/
//Get sum of numbers in tree
int getSum(treeNode *p)
{
if (p == NULL)
return 0;
else
return p->data + getSum(p->leftChild) + getSum(p->rightChild);
}
/*******************************/
//Get sum of numbers in tree
int getSumAllLeft(treeNode *p)
{
int count = 0;
if (p->leftChild != NULL)
count += 1 + getSumAllLeft(p->leftChild);   
if (p->rightChild != NULL)
count += getSumAllLeft(p->rightChild);
return count;
}
int getSumAllRight(treeNode *p)
{
if(p == NULL) return 0;
int num_l=0, num_r=0;
if(p->leftChild != NULL)
num_l = getSumAllRight(p->leftChild);
if(p->rightChild != NULL)
num_r = getSumAllRight(p->rightChild)+1;
return num_l+num_r;
}
/*******************************/
//Find the deepest Node in the tree
void deepNode(treeNode *p, int depth)
{
if (p != NULL)
{
deepNode(p->rightChild, ++depth);
if (depth > deepLevel)
{
deepValue = p->data;
deepLevel = depth;
}
deepNode(p->leftChild, depth);
}
}
/*******************************/
//count leaves
int countLeaves(treeNode *p)
{
if (p == NULL)
return 0;
if (p->leftChild == NULL && p->rightChild == NULL)
return 1;
else
return countLeaves(p->leftChild) + countLeaves(p->rightChild);
}
/*******************************/
//Find and print nodes with only one child
int oneChild(treeNode *p)
{
if (p == NULL)
return 0;
if ((p->leftChild != NULL && p->rightChild == NULL) || (p->leftChild == NULL && p->rightChild != NULL))
return 1;
else
return countLeaves(p->leftChild) + countLeaves(p->rightChild);
}
/*******************************/
//Print out the subtree of node value 299 in inorder
/***************************MAIN***************************/
int main()
{
//declare variables
int sum = 0,
leafCount = 0,
singleChild = 0;
//read in file
readFile();
//In-Order print
outFile << "Printing in order " << endl;
inOrder(root);
outFile << endl;
//Pre-Order Print
outFile << "Printing in PreOrder" << endl;
preOrder(root);
outFile << endl;
//Post Order Print
outFile << "Printing in Post Order" << endl;
postOrder(root);
outFile << endl;
//Print number of nodes in tree
outFile << "Number of Nodes = " << nodeCount << endl;
//find and print sum and average
sum = getSum(root);
outFile << "The sum of the numbers in the tree is " << sum << " and the average is: " << (sum / nodeCount) << endl;
//Find and print the value of the deepest root
deepNode(root, 0);
outFile << "The value that is deepest in the tree is: " << deepValue << endl;
//Print number of nodes with one child
leafCount = countLeaves(root);
singleChild = oneChild(root);
outFile << "The number of nodes with only one child is " << singleChild << endl;
outFile << "Finding and Printing in Order for 299" << endl;
findAndInorder(root,299);
outFile << "Finding and Printing post Order for 253" << endl;
findAndPostorder(root,253);
outFile << "Total no of Left Nodes " <<getSumAllLeft(root)<< endl;
outFile << "Total no of Right Nodes " <<getSumAllRight(root)<<endl;
outFile.close();
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.