Thread: Binary Search Trees

  1. #1
    Registered User
    Join Date
    Sep 2009
    Posts
    68

    Binary Search Trees

    For this assignment we are suppose to a public function to call a private function to do recursion.

    As of now I'm not sure were to declare.

    Code:
    node *root;
    Depending on where I place it generates different errors. If i place it with Private functions the publics tell me its unidentified. Could i do a friend or something perhaps?

    its also telling me when i try to call my private functions from inside the public ones that.

    example:

    Insert takes 1 argument.



    any assistant is appreciated.

    Code:
    #include <string>
    
    using namespace std;
    
    class exception
    {
    public:
    	void NonExistent() throw();
    };
    
    struct node 
    {
    	string data;
    	node *left;
    	node *right;
    };
    
    
    class BSTree
    {
    public:
    	void Insert(string);
    	void InOrderTraversal();
    	void PreOrderTraversal();
    	void PostOrderTraversal();
    	int Count();
    	string First();
    	string Last();
    private:
    	void InOrderTraversal(node *current);
    	void PreOrderTraversal(node *current);
    	void PostOrderTraversal(node *current);
    	int Count(node *current);
    	string First(node *current);
    	string Last(node *current);
    
    
    
    };
    
    
    void Insert(string data)
    {
    		root = new node;
    		root->data = data;
    		root->left = NULL;
    		root->right = NULL;
    }
    
    //In order public and private functions
    void InOrderTraversal()
    {
    	if (root == NULL)
    	{
    		return;
    	}
    	else
    	{
    		InOrderTraversal();
    	}
    }
    
    void InOrderTraversal(node *current)
    {
    	if (current == NULL)
    	{
    		return;
    	}
    	else
    	{
    		InOrderTraversal(current->left);
    		cout << current->data;
    		InOrderTraversal(current->right);
    	}
    }
    
    //Post order public and private functions
    void PostOrderTraversal()
    {
    	if (root == NULL)
    	{
    		return;
    	}
    	else
    	{
    		PostOrderTraversal(root);
    	}
    }
    
    void PostOrderTraversal(node *current)
    {
    	if (current == NULL)
    	{
    		return;
    	}
    	else
    	{
    		PostOrderTraversal(current->left);
    		PostOrderTraversal(current->right);
    		cout << current->data;
    	}
    }
    
    //Pre order public and private functions
    void PreOrderTraversal()
    {
    	if (root == NULL)
    	{
    		return;
    	}
    	else
    	{
    		PreOrderTraversal(root);
    	}
    }
    
    void PreOrderTraversal(node *current)
    {
    	if (current == NULL)
    	{
    		return;
    	}
    	else
    	{
    		cout << current->data;
    		PreOrderTraversal(current->left);
    		PreOrderTraversal(current->right);
    	}
    }
    
    int Count()
    {
    	if (root == NULL)
    	{
    		return 0;
    	}
    	else
    	{
    		Count(root);
    	}
    }
    
    int Count(node *current)
    {
    	if (current == NULL)
    	{
    		return 0;
    	}
    	else
    	{
    	int count = 1;
    
    	count += Count(current->left);
    
    	count += Count(current->right);
    
    	return count;
    	}
    }

  2. #2
    Registered User
    Join Date
    Sep 2009
    Posts
    68
    if it helps here is cpp file provided to us by our teacher.

    Code:
    /* To compile this program, do the following
    aCC olab10BSTreeMain.cpp BSTree.cpp
    To execute with test data file
    a.out < /nfshome/csal/public_html/spring.10/2170/olab10sp10.dat
    
    uses exceptions
    As always let me know if there are syntax errors in program
    */
    
    #include <iostream>
    #include "BSTree.h"
    using namespace std;
    
    int main()
    {
    
       BSTree MyTree;			// A binary search tree used in examples
    
       // See what happens when an empty tree is printed
       cout << "An empty tree:" << MyTree << "*" << endl;
       cout << "Count: " << MyTree.Count() << endl;
       try
       {
          cout << "First String: " << MyTree.First() << endl;
       }
       catch (NonExistent myexception)
       {
         cerr << "There are data itemd in the tree" << endl; 
       }
    
       try
       {
         cout << "Last String: " << MyTree.Last() << endl;
       }
       catch (NonExistent myexception)
       {
         cerr << "There are data itemd in the tree" << endl; 
       }
      
       cin >> MyTree;		// read's into
       cout << "Tree after first read: " << MyTree << endl;;
       cout << "Count: " << MyTree.Count() << endl;
       try
       {
          cout << "First String: " << MyTree.First() << endl;
       }
       catch (NonExistent myexception)
       {
         cerr << "There are data itemd in the tree" << endl; 
       }
    
       try
       {
         cout << "Last String: " << MyTree.Last() << endl;
       }
       catch (NonExistent myexception)
       {
         cerr << "There are data itemd in the tree" << endl; 
       }
    
       MyTree.Insert("into");  	// insert new root
       cout << "Tree after insert: " << MyTree << endl;;
    
       cin >> MyTree;		// read's insert
       cout << "Tree after second read: " << MyTree << endl; // This does inorder traversal
       cout << "Count: " << MyTree.Count() << endl;
       try
       {
          cout << "First String: " << MyTree.First() << endl;
       }
       catch (NonExistent myexception)
       {
         cerr << "There are data itemd in the tree" << endl; 
       }
    
       try
       {
         cout << "Last String: " << MyTree.Last() << endl;
       }
       catch (NonExistent myexception)
       {
         cerr << "There are data itemd in the tree" << endl; 
       }
       cin >> MyTree;		// read's into
       cin >> MyTree;		// read's link
       cin >> MyTree;		// read's list
       cout << "Tree after read: " << MyTree << endl; // This does inorder traversal
       cout << "Count: " << MyTree.Count() << endl;
       try
       {
         cout << "First String: " << MyTree.First() << endl;
       }
       catch (NonExistent myexception)
       {
         cerr << "There are data itemd in the tree" << endl; 
       }
       try
       {
         cout << "Last String: " << MyTree.Last() << endl;
       }
       catch (NonExistent myexception)
       {
         cerr << "There are data itemd in the tree" << endl; 
       }
       cin >> MyTree;		// read one string into the tree
       cout << "Tree after read: " << MyTree << endl; // This does inorder traversal
       cout << "Count: " << MyTree.Count() << endl;
       try
       {
         cout << "First String: " << MyTree.First() << endl;
       }
       catch (NonExistent myexception)
       {
         cerr << "There are data itemd in the tree" << endl; 
       }
       try
       {
         cout << "Last String: " << MyTree.Last() << endl;
       }
       catch (NonExistent myexception)
       {
         cerr << "There are data itemd in the tree" << endl; 
       }
       cin >> MyTree;		// read's next
       cin >> MyTree;		// read's last
       cout << "Tree after read: " << MyTree << endl; // This does inorder traversal
       cout << "Count: " << MyTree.Count() << endl;
       try
       {
         cout << "First String: " << MyTree.First() << endl;
       }
       catch (NonExistent myexception)
       {
         cerr << "There are data itemd in the tree" << endl; 
       }
       try
       {
         cout << "Last String: " << MyTree.Last() << endl;
       }
       catch (NonExistent myexception)
       {
         cerr << "There are data itemd in the tree" << endl; 
       }
       cout << "Inorder traversal: " << endl;
       MyTree.InOrderTraversal();
       cout << endl;
       cout << "Preorder traversal: " << endl;
       MyTree.PreOrderTraversal();
       cout << endl;
       cout << "Postorder traversal: " << endl;
       MyTree.PostOrderTraversal();
       cout << endl;
    
       cin >> MyTree;		// read's link
       cin >> MyTree;		// read's insurance
       cout << "Tree after read: " << MyTree << endl; // This does inorder traversal
       cout << "Count: " << MyTree.Count() << endl;
       try
       {
         cout << "First String: " << MyTree.First() << endl;
       }
       catch (NonExistent myexception)
       {
         cerr << "There are data itemd in the tree" << endl; 
       }
       try
       {
         cout << "Last String: " << MyTree.Last() << endl;
       }
       catch (NonExistent myexception)
       {
         cerr << "There are data itemd in the tree" << endl; 
       }
       cout << "Inorder traversal: " << endl;
       MyTree.InOrderTraversal();
       cout << endl;
       cout << "Preorder traversal: " << endl;
       MyTree.PreOrderTraversal();
       cout << endl;
       cout << "Postorder traversal: " << endl;
       MyTree.PostOrderTraversal();
       cout << endl;
    
       cin >> MyTree;		// read's help
       cin >> MyTree;		// read's insert
       cout << "Tree after read: " << MyTree << endl; // This does inorder traversal
       cout << "Count: " << MyTree.Count() << endl;
       try
       {
         cout << "First String: " << MyTree.First() << endl;
       }
       catch (NonExistent myexception)
       {
         cerr << "There are data itemd in the tree" << endl; 
       }
       try
       {
         cout << "Last String: " << MyTree.Last() << endl;
       }
       catch (NonExistent myexception)
       {
         cerr << "There are data itemd in the tree" << endl; 
       }
       cout << "Inorder traversal: " << endl;
       MyTree.InOrderTraversal();
       cout << endl;
       cout << "Preorder traversal: " << endl;
       MyTree.PreOrderTraversal();
       cout << endl;
       cout << "Postorder traversal: " << endl;
       MyTree.PostOrderTraversal();
       cout << endl;
    
       cout << "Count: " << MyTree.Count() << endl;
       try
       {
         cout << "First String: " << MyTree.First() << endl;
       }
       catch (NonExistent myexception)
       {
         cerr << "There are data itemd in the tree" << endl; 
       }
       try
       {
         cout << "Last String: " << MyTree.Last() << endl;
       }
       catch (NonExistent myexception)
       {
         cerr << "There are data itemd in the tree" << endl; 
       }
       cout << "Inorder traversal: " << endl;
       MyTree.InOrderTraversal();
       cout << endl;
       cout << "Preorder traversal: " << endl;
       MyTree.PreOrderTraversal();
       cout << endl;
       cout << "Postorder traversal: " << endl;
       MyTree.PostOrderTraversal();
       cout << endl;
    
       cin >> MyTree;		// read's justice
       cout << "Tree after read: " << MyTree << endl; // This does inorder traversal
       cout << "Count: " << MyTree.Count() << endl;
       try
       {
         cout << "First String: " << MyTree.First() << endl;
       }
       catch (NonExistent myexception)
       {
         cerr << "There are data itemd in the tree" << endl; 
       }
       try
       {
         cout << "Last String: " << MyTree.Last() << endl;
       }
       catch (NonExistent myexception)
       {
         cerr << "There are data itemd in the tree" << endl; 
       }
       cout << "Inorder traversal: " << endl;
       MyTree.InOrderTraversal();
       cout << endl;
       cout << "Preorder traversal: " << endl;
       MyTree.PreOrderTraversal();
       cout << endl;
       cout << "Postorder traversal: " << endl;
       MyTree.PostOrderTraversal();
       cout << endl;
    
       cin >> MyTree;		// read's just
       cout << "Tree after read: " << MyTree << endl; // This does inorder traversal
       cout << "Count: " << MyTree.Count() << endl;
       try
       {
         cout << "First String: " << MyTree.First() << endl;
       }
       catch (NonExistent myexception)
       {
         cerr << "There are data itemd in the tree" << endl; 
       }
       try
       {
         cout << "Last String: " << MyTree.Last() << endl;
       }
       catch (NonExistent myexception)
       {
         cerr << "There are data itemd in the tree" << endl; 
       }
       cout << "Inorder traversal: " << endl;
       MyTree.InOrderTraversal();
       cout << endl;
       cout << "Preorder traversal: " << endl;
       MyTree.PreOrderTraversal();
       cout << endl;
       cout << "Postorder traversal: " << endl;
       MyTree.PostOrderTraversal();
       cout << endl;
    
       // test copy constructor
       BSTree CopyTree(MyTree);
       cout << "Copy Tree: " << CopyTree << endl;;
    
       cout << "end of main"<<endl;
       return 0;
    }

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    On web forums, when you get compiler errors, post the exact errors, and in their entirety.
    Make sure that's never just your own summary, and never leaving out bits of the errors that you think are irrelevant such as hexadecimal memory addresses etc. In other words, your job is as easy as copy and paste.
    Last edited by iMalc; 04-30-2010 at 03:06 PM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Need help with binary search.
    By StateofMind in forum C Programming
    Replies: 6
    Last Post: 05-06-2009, 02:14 PM
  2. Binary Search Trees
    By lorannex in forum C Programming
    Replies: 3
    Last Post: 04-25-2009, 06:24 AM
  3. Performance issue!
    By maven in forum C Programming
    Replies: 42
    Last Post: 03-23-2009, 11:57 AM
  4. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM