GIDForums  

Go Back   GIDForums > Computer Programming Forums > C++ Forum
User Name
Password
Register FAQ Members List Calendar Search Today's Posts Mark Forums Read
 
 
Thread Tools Search this Thread Rate Thread
  #1  
Old 25-Apr-2011, 19:07
90fmm 90fmm is offline
New Member
 
Join Date: Apr 2011
Posts: 7
90fmm is on a distinguished road

Binary Tree recursive Functions


Doing a binary tree holding numbers in it. Below is the header file with all the recursive functions. I want to know if the recursive functions that are written are correct and also having trouble coming with a solution for the void btree::print_line_help (tree_ptr current) and bool btree::duplicate_help (tree_ptr current, int number) also. Below is the code so far-> ny help is appreciated:
CPP / C++ / C Code:
#include <iostream>
using namespace std;

// a binary tree node
struct tree_node 
{
       int contents;                // integer in node
       tree_node *right, *left;     // pointers to right and left children
};

typedef tree_node* tree_ptr;

class btree 
{
      private:
          // root of tree
          tree_ptr root;
          // function creates a leaf
          tree_ptr make_leaf (int number);
          // recursive helper function for insert
          void insert_help (tree_ptr& current, int number);
          // recursive helper function for summing all nodes
          int sum_help (tree_ptr current);
          // recursive helper function for summing leafs
          int sum_leafs_help (tree_ptr current);
          // recursive helper function for finding maximum depth of tree
          int depth_help (tree_ptr current);
          // recursive helper funtion for searching the tree
          bool search_help (tree_ptr current, int number);
          // recursive helper function for determining duplicates
          bool duplicate_help (tree_ptr current, int number);
          // recursive helper function for print leafs
          void print_leafs_help (tree_ptr current);
          // recursive helper function for printing ordered nodes
          void print_line_help (tree_ptr current);
          // recursive helper function for printing inorder tree 
          void tree_print_help (tree_ptr current, int indent);
      public:
          btree ();
          void insert (int number);
          int sum ();
          int sum_leafs ();
          int depth ();
          bool search (int number);
          bool duplicate (int number);
          void print_leafs ();
          void print_line ();
          void tree_print ();
};

// constructor creates an empty tree
btree::btree ()
{
   root = NULL;
}

// function creates and returns a pointer to a leaf node
// containing number as its contents
tree_ptr btree::make_leaf (int number)
{
    tree_ptr new_ptr;  // pointer to new node to be returned
    
    new_ptr = new tree_node;
    new_ptr -> contents = number;
    new_ptr -> right = NULL;
    new_ptr -> left = NULL;
    return new_ptr;
}

// insert number into the tree
void btree::insert (int number)
{
     insert_help (root, number);
}

// recursive function for inserting
void btree::insert_help (tree_ptr& current, int number)
{
     // tree is empty (or found empty branch), insert
     // new node
     if (current == NULL)
        current = make_leaf (number);
     else
         // number is greater than current node, insert to the right
         if (number > current -> contents)
            insert_help (current -> right, number);
         else  // number is less than current node, insert to the left
            insert_help (current -> left, number);
}

// sums all nodes in the tree
int btree::sum ()
{
    return sum_help (root);
}

// recursive helper function for summing
int btree::sum_help (tree_ptr current)
{

if(current == NULL)
     return 0;
    else 
     sum = current->contents + 
            sum_help(current ->left) + sum_help(current->right);
    return sum;        
}

// sums all the leafs in the tree
int btree::sum_leafs ()
{
    return sum_leafs_help (root);
}

// recursive helper function for summing the leafs
int btree::sum_leafs_help (tree_ptr current)
{
    if(current->left == NULL && current->right == NULL)
     sum = current->contents + 
        sum_leafs_help(current->left) + sum_leafs_help(current->right);
    return 
    sum; 
    else 
      return 0;
}    
 
// returns the maximum depth of the tree
int btree::depth ()
{
    return depth_help (root);
}

// recursive helper function for depth
int btree::depth_help (tree_ptr current)
{
    int left_depth, right_depth;
    
    if(root == NULL)
      return 0;
    else
    {
     left_depth = depth_help(current->left);
     right_depth = depth_help(current->right);
     
     //use the larger one
     if(left_depth > right_depth)
     
     return (left_depth + 1);
     else 
     return (right_depth + 1);
     }
}
// returns true if number is found in the tree
bool btree::search (int number)
{
     return search_help (root, number);
}

// recursive helper function for search
bool btree::search_help (tree_ptr current, int number)
{
     if(current == NULL)
             return false;
     else 
        {
             if(current->contents == number)
                         return true;
             else if(current->contents < number)
                         search_help(current->left, number);
             else
                         search_help(current->right, number);
        }                                         
}
// returns true if number is duplicated in the tree
bool btree::duplicate (int number)
{
     return duplicate_help (root, number);
}

// recursive helper function for duplicate
bool btree::duplicate_help (tree_ptr current, int number)

     

// prints the leafs in the tree
void btree::print_leafs ()
{
     print_leafs_help (root);
}

// recursive helper function for print_leafs
void btree::print_leafs_help (tree_ptr current)
{
     if(current->left == NULL && current->right = NULL)
     cout<<current->contents;
}
     

// prints the inorder list of nodes in the tree                  
void btree::print_line ()
{
     print_line_help (root);
}

// recursive helper function for print_line
void btree::print_line_help (tree_ptr current)
{
      int count;
     
     if(current != NULL)
     {
                
                print_line_help(current->left);
                print_line_help(current->contents + " ");   
                print_line_help(current->right);
                  
     }
     
     
}

// prints the inorder tree with indentation
void btree::tree_print ()
{
     tree_print_help (root, 0);
}

// helper function for tree print with indentation
void btree::tree_print_help (tree_ptr current, int indent)
{
     int count;
     
     if(current != NULL)
     {
                //print the left subtree
                tree_print_help(current->left, indent + 2);
                cout <<endl;
                //indent and print
                for(count = 0; count < indent; count++)
                  cout << " ";
                  cout << current ->contents;
                  //print the right subtree
                  tree_print_help(current->right, indent + 2);
     }
}


  #2  
Old 27-Apr-2011, 07:33
prattcmp prattcmp is offline
Junior Member
 
Join Date: Mar 2011
Posts: 44
prattcmp will become famous soon enough

Re: Binary Tree recursive Functions


Quote:
Originally Posted by 90fmm
Doing a binary tree holding numbers in it. Below is the header file with all the recursive functions. I want to know if the recursive functions that are written are correct and also having trouble coming with a solution for the void btree:rint_line_help (tree_ptr current) and bool btree::duplicate_help (tree_ptr current, int number) also. Below is the code so far-> ny help is appreciated:
CPP / C++ / C Code:
#include <iostream>
using namespace std;

// a binary tree node
struct tree_node 
{
       int contents;                // integer in node
       tree_node *right, *left;     // pointers to right and left children
};

typedef tree_node* tree_ptr;

class btree 
{
      private:
          // root of tree
          tree_ptr root;
          // function creates a leaf
          tree_ptr make_leaf (int number);
          // recursive helper function for insert
          void insert_help (tree_ptr& current, int number);
          // recursive helper function for summing all nodes
          int sum_help (tree_ptr current);
          // recursive helper function for summing leafs
          int sum_leafs_help (tree_ptr current);
          // recursive helper function for finding maximum depth of tree
          int depth_help (tree_ptr current);
          // recursive helper funtion for searching the tree
          bool search_help (tree_ptr current, int number);
          // recursive helper function for determining duplicates
          bool duplicate_help (tree_ptr current, int number);
          // recursive helper function for print leafs
          void print_leafs_help (tree_ptr current);
          // recursive helper function for printing ordered nodes
          void print_line_help (tree_ptr current);
          // recursive helper function for printing inorder tree 
          void tree_print_help (tree_ptr current, int indent);
      public:
          btree ();
          void insert (int number);
          int sum ();
          int sum_leafs ();
          int depth ();
          bool search (int number);
          bool duplicate (int number);
          void print_leafs ();
          void print_line ();
          void tree_print ();
};

// constructor creates an empty tree
btree::btree ()
{
   root = NULL;
}

// function creates and returns a pointer to a leaf node
// containing number as its contents
tree_ptr btree::make_leaf (int number)
{
    tree_ptr new_ptr;  // pointer to new node to be returned
    
    new_ptr = new tree_node;
    new_ptr -> contents = number;
    new_ptr -> right = NULL;
    new_ptr -> left = NULL;
    return new_ptr;
}

// insert number into the tree
void btree::insert (int number)
{
     insert_help (root, number);
}

// recursive function for inserting
void btree::insert_help (tree_ptr& current, int number)
{
     // tree is empty (or found empty branch), insert
     // new node
     if (current == NULL)
        current = make_leaf (number);
     else
         // number is greater than current node, insert to the right
         if (number > current -> contents)
            insert_help (current -> right, number);
         else  // number is less than current node, insert to the left
            insert_help (current -> left, number);
}

// sums all nodes in the tree
int btree::sum ()
{
    return sum_help (root);
}

// recursive helper function for summing
int btree::sum_help (tree_ptr current)
{

if(current == NULL)
     return 0;
    else 
     sum = current->contents + 
            sum_help(current ->left) + sum_help(current->right);
    return sum;        
}

// sums all the leafs in the tree
int btree::sum_leafs ()
{
    return sum_leafs_help (root);
}

// recursive helper function for summing the leafs
int btree::sum_leafs_help (tree_ptr current)
{
    if(current->left == NULL && current->right == NULL)
     sum = current->contents + 
        sum_leafs_help(current->left) + sum_leafs_help(current->right);
    return 
    sum; 
    else 
      return 0;
}    
 
// returns the maximum depth of the tree
int btree::depth ()
{
    return depth_help (root);
}

// recursive helper function for depth
int btree::depth_help (tree_ptr current)
{
    int left_depth, right_depth;
    
    if(root == NULL)
      return 0;
    else
    {
     left_depth = depth_help(current->left);
     right_depth = depth_help(current->right);
     
     //use the larger one
     if(left_depth > right_depth)
     
     return (left_depth + 1);
     else 
     return (right_depth + 1);
     }
}
// returns true if number is found in the tree
bool btree::search (int number)
{
     return search_help (root, number);
}

// recursive helper function for search
bool btree::search_help (tree_ptr current, int number)
{
     if(current == NULL)
             return false;
     else 
        {
             if(current->contents == number)
                         return true;
             else if(current->contents < number)
                         search_help(current->left, number);
             else
                         search_help(current->right, number);
        }                                         
}
// returns true if number is duplicated in the tree
bool btree::duplicate (int number)
{
     return duplicate_help (root, number);
}

// recursive helper function for duplicate
bool btree::duplicate_help (tree_ptr current, int number)

     

// prints the leafs in the tree
void btree::print_leafs ()
{
     print_leafs_help (root);
}

// recursive helper function for print_leafs
void btree::print_leafs_help (tree_ptr current)
{
     if(current->left == NULL && current->right = NULL)
     cout<<current->contents;
}
     

// prints the inorder list of nodes in the tree                  
void btree::print_line ()
{
     print_line_help (root);
}

// recursive helper function for print_line
void btree::print_line_help (tree_ptr current)
{
      int count;
     
     if(current != NULL)
     {
                
                print_line_help(current->left);
                print_line_help(current->contents + " ");   
                print_line_help(current->right);
                  
     }
     
     
}

// prints the inorder tree with indentation
void btree::tree_print ()
{
     tree_print_help (root, 0);
}

// helper function for tree print with indentation
void btree::tree_print_help (tree_ptr current, int indent)
{
     int count;
     
     if(current != NULL)
     {
                //print the left subtree
                tree_print_help(current->left, indent + 2);
                cout <<endl;
                //indent and print
                for(count = 0; count < indent; count++)
                  cout << " ";
                  cout << current ->contents;
                  //print the right subtree
                  tree_print_help(current->right, indent + 2);
     }
}


It burns! Too much code to look over! MxB will probably be the only one to read all of that.
__________________
The Revived Coder
  #3  
Old 27-Apr-2011, 13:53
WaltP's Avatar
WaltP WaltP is offline
Outstanding Member
 
Join Date: Feb 2004
Location: Midwest US
Posts: 3,435
WaltP is a name known to allWaltP is a name known to allWaltP is a name known to allWaltP is a name known to allWaltP is a name known to allWaltP is a name known to all

Re: Binary Tree recursive Functions


Quote:
Originally Posted by 90fmm
I want to know if the recursive functions that are written are correct...
Did the functions crash? Did the functions give the proper output? These are usually the criteria for a "correct" function.


Quote:
Originally Posted by prattcmp
It burns! Too much code to look over! MxB will probably be the only one to read all of that.
That's not so bad. At least it's formatted!
__________________

Definition: Politics
Latin, from
poly meaning many and
tics meaning blood sucking parasites
-- Tom Smothers
  #4  
Old 27-Apr-2011, 18:37
prattcmp prattcmp is offline
Junior Member
 
Join Date: Mar 2011
Posts: 44
prattcmp will become famous soon enough

Re: Binary Tree recursive Functions


Quote:
Originally Posted by WaltP
That's not so bad.
Yea, now that I look at it again, but still. It is too much for me to answer a question especially since the question is so broad.
Quote:
Originally Posted by WaltP

At least it is properly formatted
Yes, that is true . He succused at something i didnt
__________________
The Revived Coder
 


Thread Tools Search this Thread
Search this Thread:

Advanced Search
Rate This Thread
Rate This Thread:

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Forum Jump

Similar Threads
Thread Thread Starter Forum Replies Last Post
WPF Tree View Question Falcon Eyes .NET Forum 0 20-Jan-2011 15:19
Push binary equivalent of a file to an array/vector jc.021286 C++ Forum 1 23-Nov-2010 03:50
conflict between printf and stdarg.h va functions mirizar C Programming Language 3 12-Jul-2004 08:11
Understanding functions tommy69 C Programming Language 15 15-Mar-2004 18:59
tree problem zuzupus MySQL / PHP Forum 0 01-Aug-2003 08:27

Network Sites: GIDNetwork · GIDApp · GIDBlog · Learning Journal by J de Silva, The

All times are GMT -6. The time now is 03:11.


vBulletin, Copyright © 2000 - 2017, Jelsoft Enterprises Ltd.