Binary Tree complications

I'm having a number of issues with my program. I apologize now, if this is not the proper way of doing this. Below will be the issues, spec sheet, infile data, and current code that I have along with the output.

1. I was attempting to format my output to include 10 values then endl and print 10 more values.

2. Unsure if it is the delete method, or inorder method, or sumdigit method, but I can not get the correct output for the final criteria once values less than 10 are deleted. Even if they are deleted, the current output shows incorrectly.

3. I tried to incorporate a search method to search for specific nodes and print them out. Specifically 253, each time I attempt it prints the data not just the criteria being searched for.

As for this moment I believe this is all the issues I am having currently.

Write a program to read in as set of numbers and build an ordered binary tree. For the given the tree compute and print the following

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 253 (253 being the root of subtree) in inorder.
j. Print out the right subtree of node value 471 (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.

Input file is on blackboard named TreeRandNbrs.dat

Add delete routines:
l. Delete all the nodes in the tree that the sum of the digits (the value in the node) is less than 10.
Afterwards, print out the first 25 nodes of the tree in inorder.
m. Sum up all the values in the altered tree and compute the average. Print sum and average.

OUTPUT
A. Print Out the tree IN-ORDER (first 20 values)
100 102 107 111 115 116 117 123 127 130 133 134 136 138 139 140 141 328 369 500

B. Print out the tree PRE-ORDER (first 20 values)
141 117 116 107 100 102 115 111 134 123 130 127 133 136 140 139 138 500 369 328

C. Print out the tree POST-ORDER (first 20 values)
102 100 111 115 107 116 127 133 130 123 138 139 140 136 134 117 328 369 500 141

D. Number of Nodes in the tree: 152

E. Sum and Average of the tree:
        Sum: 48338 Average: 318.0

F. Number of Leafs in the tree: 51

G. Deepest Down in the tree: 284

H. Number of Nodes with ONE Child: 51

I. Subtree of Node 253 IN-ORDER:
100 102 107 111 115 116 117 123 127 130 133 134 136 138 139 140 141 328 369 500

J. Right Subtree of node 471 POST-ORDER:
102 100 111 115 107 116 127 133 130 123 138 139 140 136 134 117 328 369 500 141

K. Nodes to the left: 152
   Nodes to the Right:152

L. Delete Nodes, sum is less than 10 (first 25) IN-ORDER:
100 102 107 115 116 117 123 127 130 133 134 136 138 139 140 141 208 328 369 500

M. Sum and Average of Altered Tree:
        Sum: 48227 Average: 317.3

C:\Users\Owner\OneDrive\Fall 2020\CS 372 - Data Structures\9th Program - Tree\Tree\Debug\Tree.exe (process 14604) exited with code 0.
Press any key to close this window . . .

Last edited on

CodeNovice01 (278)

#include <iostream>
using namespace std;

// TREE Class
class tree
{
private:
     struct node //holds the value and position within the tree
     {
          int num; // holds the value for placement into tree
          node* LC; // left child value
          node* RC; // right child value
     };

     int  newNode()  // Creates a new node to be inserted in the tree
     {
          node* temp;
          temp->LC = NULL;
          temp->RC = NULL;
          temp->num = 0;
     }

     node* root = NULL;//head

     void insert(node* cp, int target)  //inserting numbers into the tree
     {
          node* p = NULL;

          while (cp != NULL)
          {
               p = cp;
               if (target < cp->num)
                    cp = cp->LC;
               else
                    cp = cp->RC;
          }

          cp = new node();
          cp->num = target;

          if (p == NULL)
               root = cp;
          if (p != NULL)
               if (target < p->num)
                    p->LC = cp;
               else
                    p->RC = cp;
     }

     bool ifNodeExists(struct node* root, int key) //bool function to search if a value is already in the tree 
     {
          bool answer = ifNodeExists(root->LC, key)
               , answer2 = ifNodeExists(root->RC, key);

          if (root == NULL)
               return false;
          if (root->num == key)
               return true;

          if (answer) //if node is found, return true
               return true;
          //check right side of tree 
          return answer2;
     }

     int sum(node* root)  //function to find the sum of values in a tree
     {
          if (root == NULL)
               return 0;
          return (root->num + sum(root->LC) + sum(root->RC));
     }

     int countNumNodes(node* root)  //function to cnt the number of nodes 
     {
          int c = 1;
          if (root == NULL)
               return 0;
          else
          {
               c += countNumNodes(root->LC);
               c += countNumNodes(root->RC);
               return c;
          }
     }

     int getLeafCount(node* root)   //return the number of leaf nodes
     {
          if (root == NULL)
               return 0;

          if (root->LC == NULL && root->RC == NULL)
               return 1;
          else
               return getLeafCount(root->LC) + getLeafCount(root->RC);
     }

     int oneChildCount(node* root) //counts the number of nodes with only 1 child
     {
          if (root == NULL)
               return 0;

          int cnt = 0;
          if ((root->LC == NULL && root->RC != NULL) || (root->LC != NULL && root->RC == NULL))
               cnt++;

          cnt += (oneChildCount(root->LC) + oneChildCount(root->RC));
          return cnt;
     }

     void find(node* root, int level, int& maxLevel, int& deepest) //finds the deepest node in the tree 
     {
          if (root != NULL)
          {
               find(root->LC, ++level, maxLevel, deepest);
               if (level > maxLevel)
               {
                    deepest = root->num;
                    maxLevel = level;
               }
               find(root->RC, level, maxLevel, deepest);
          }
     }

     int deepestNode(node* root)   //returns the value of the deepest node in the tree
     {
          int deepest = -1;
          int maxLevel = -1;

          find(root, 0, maxLevel, deepest);
          return deepest;
     }

     void Search( node*& root, int n)
     {
          
          if (!root)
               return;
          if (root->num == n)
               
          Search(root->LC, n);
          Search(root->RC, n);
     }

     node* FindMin(node* root)
     {
          while (root->LC != NULL) 
               root = root->LC;
          return root;
     }

     //found this method online, incorporated it bc i wasn't sure if my method was wrong
     node* Delete(node* root, int num) //deletes nodes in the tree <10
     {
          if (root == NULL)
               return root;
          else if (num < root->num) root->LC = Delete(root->LC, num);
          else if (num > root->num) root->RC = Delete(root->RC, num);
          // Wohoo... I found you, Get ready to be deleted	
          else {
               // Case 1:  No child
               if (root->LC == NULL && root->RC == NULL) {
                    delete root;
                    root = NULL;
               }
               //Case 2: One child 
               else if (root->LC == NULL) {
                    node* temp = root;
                    root = root->RC;
                    delete temp;
               }
               else if (root->RC == NULL) {
                    node* temp = root;
                    root = root->LC;
                    delete temp;
               }
               // case 3: 2 children
               else {
                    node* temp = FindMin(root->RC);
                    root->num = temp->num;
                    root->RC = Delete(root->RC, temp->num);
               }
          }
          return root;
     }

     void printInorder(node* root, int& cnt)  //function to print the tree in order
     {
          if (root == NULL)
               return;
          if (cnt < 20)
          {
               //cnt++;//commented out bc it would cause more issues
               printInorder(root->LC, cnt);
               cout << root->num << " ";
                   if(++cnt%10==0)//this is where i'm trying to do 10 values per line
                       cout<<endl;//instead it would print 8 then 10 then 2 on three lines
               printInorder(root->RC, cnt);
          }
     }

     void printPreorder(node* root, int& cnt) //function to print the tree in preorder 
     {
          if (root == NULL)
               return;

          if (cnt < 20)
          {
               cnt++;
               cout << root->num << " ";
               printPreorder(root->LC, cnt);
               printPreorder(root->RC, cnt);
          }
     }

     void printPostorder(node* root, int& cnt)  //function to print the tree in postorder
     {
          if (root == NULL)
               return;

          if (cnt < 20)
          {
               cnt++;
               printPostorder(root->LC, cnt);
               printPostorder(root->RC, cnt);
               cout << root->num << " ";
          }
     }

public:
     tree()
     {
          root = NULL;
     }
     void Search(int n)
     {
          Search(root, n);
     }
     void insert(int target)
     {
          insert(root, target);
     }

     bool ifNodeExists(int key)
     {
          return ifNodeExists(root, key);
     }

     int sum()
     {
          return sum(root);
     }

     int countNumNodes()
     {
          return  countNumNodes(root);
     }

     int getLeafCount()
     {
          return getLeafCount(root);
     }

     int oneChildCount()
     {
          return  oneChildCount(root);
     }

     int deepestNode()
     {
          return deepestNode(root);
     }

     node* Delete(int num)
     {
          return Delete(root,num);
     }

     void printInorder(int& cnt)
     {
          printInorder(root, cnt);
     }

     void printPreorder(int& count1)
     {
          printPreorder(root, count1);
     }

     void printPostorder(int& cnt)
     {
          printPostorder(root, cnt);
     }

     int sumDigits(int n)  //recursive function to find the sum of a digit
     {
          if (n)
               return ((n % 10) + sumDigits(n / 10));
          else
               return 0;
     }
};//END of Class Tree

Last edited on

CodeNovice01 (278)

#include <iostream>
#include <fstream>
#include <iomanip>
#include "tree.h"
using namespace std;

ifstream inf("tree.in");
//ofstream cout("tree.cout");

int main()
{
     tree root;  //head
     int val;        //the value to be read into the node     
     int numNodes;  //the number of nodes in the binary tree 
     int printCount = 0;  //the number of nodes to print 
     int treeSum;   //sum of the nodes in the tree 
     float avg;     //average of the nodes in the tree 
     int leafCount;  //the number of leaves in the tree 
     int deepest;    //the deepest node in the tree
     int oneChild;   //number of nodes with only 1 child 

     //while reading the values from a file
     while (inf>>val)
          root.insert(val);

     //  AAAAA   printing the tree inorder
     cout << "A. Print Out the tree IN-ORDER (first 20 values)" << endl;
     root.printInorder(printCount);
     cout << endl << endl;
     printCount = 0;  //reset the print cnt

     // BBBBBBB    printing the tree preorder 
     cout << "B. Print out the tree PRE-ORDER (first 20 values)" << endl;
     root.printPreorder(printCount);
     cout << endl << endl;
     printCount = 0; //reset the print cnt 

     //  CCCCCCC   printing the tree in postorder
     cout << "C. Print out the tree POST-ORDER (first 20 values)" << endl;
     root.printPostorder(printCount);
     cout << endl << endl;
     printCount = 0; //reset the print cnt

     // DDDDDDDD  finding the number of nodes
     numNodes = root.countNumNodes();
     cout << "D. Number of Nodes in the tree: " << numNodes << endl << endl;

     //  EEEEEEEE   printing the sum and average of the values in the tree
     cout << "E. Sum and Average of the tree: " << endl;
     treeSum = root.sum();
     avg = static_cast<float>(treeSum) / numNodes;
     cout << "\tSum: " << treeSum << " Average: " << fixed << setprecision(1) << avg << endl << endl;

     //  FFFFFFFFFF find the number of leaves in the tree
     leafCount = root.getLeafCount();
     cout << "F. Number of Leafs in the tree: " << leafCount << endl << endl;
   
     //  GGGGGGGGGG find the deepest leaf in the tree
     deepest = root.deepestNode();
     cout << "G. Deepest Down in the tree: " << deepest << endl << endl;
    
     //  HHHHHHHHHH find the number of nodes that have only (1) child
     oneChild = root.oneChildCount();
     cout << "H. Number of Nodes with ONE Child: " << oneChild << endl << endl;
   
     //  IIIIIIIII   print the tree inorder again
     cout << "I. Subtree of Node 253 IN-ORDER: " << endl;
     root.Search(253);
    
     root.printInorder(printCount);//ALTER THIS FOR REQUIREMENT
     printCount = 0;
     cout << endl << endl;
   
     //  JJJJJJJJJJ
     cout << "J. Right Subtree of node 471 POST-ORDER: " << endl;
     root.printPostorder(printCount);
     cout << endl << endl;

     //  KKKKKK print the number of nodes
     numNodes = 0;  //reset variable
     numNodes = root.countNumNodes();
     cout << "K. Nodes to the left: " << numNodes << endl 
             << "   Nodes to the Right:"   << numNodes << endl << endl;
     
     //  LLLLLLLL  delete nodes where the sum of the digits is <10
     printCount = 0;
     root.Delete(val);     
     cout << "L. Delete Nodes, sum is less than 10 (first 25) IN-ORDER: " << endl;
     root.printInorder(printCount);
     cout << endl << endl;

     //  MMMMMM find the sum and average of the tree again
     cout << "M. Sum and Average of Altered Tree: " << endl;
     treeSum = root.sum();
     avg = static_cast<float>(treeSum) / numNodes;
     cout << "\tSum: " << treeSum << " Average: " << fixed << setprecision(1) << avg << endl;

     inf.close();
   //  cout.close();
     return 0;
}

seeplus (6599)

This is where the debugger becomes your new best friend. Trace through the code using the debugger seeing the path(s) taken, the values of the variables etc. When you see what isn't expected, then you're found a problem.

CodeNovice01 (278)

I'm not sure how to properly use the debugger. I'm not a CS major, I'm IT

seeplus (6599)

What compiler/os are you using?

Now is the time to get to grips with the debugger. Every programmer needs to acquire the ability to debug programs.

Topic archived. No new replies allowed.

C++

Forum

Binary Tree complications