Thread: I would love some input on my BST tree.

  1. #1
    Registered User StevenGarcia's Avatar
    Join Date
    Nov 2006
    Posts
    22

    I would love some input on my BST tree.

    Hello. I have spent some time working on my BST tree and have finally gotten it to work. I was wondering if some people could take a look at my code and perhaps offer some criticism.
    I would really appreciate it. Thank you.

    Code:
    //======================
    // BST.h
    //======================
    
    struct node
    {
    	int element;
    	node * left;
    	node * right;
    };
    
    // My BST class
    class BST
    {
    
    public:
    	
    	BST();
    	~BST();
    	void insert();
    	void remove();
    	void display();
    
    private:
    
    	node * root;
    	int num_in_tree;
    
    	void insert(int, node *&);
    	int remove(int, node *&);
    	node * inorderSuccessor(node *&);
    	int children(node *);
    	void display(node *);
    	void destroy(node *&);
    };
    
    //=============
    // BST.cpp
    //=============
    
    #include <iostream>
    #include "BST.h"
    
    using namespace std;
    
    BST::BST()
    {
    	root = NULL;
    	num_in_tree = 0;
    }
    
    BST::~BST()
    {
    	destroy(root);
    }
    
    //================================================
    // INPUT: none
    // OUTPUT: none
    // gets input from user and calls recursive insert
    //================================================
    void BST::insert()
    {
    	int key;
    	cout << "Enter a number to insert:\n";
    	cin >> key;
    	cin.get();
    	insert(key, root);
    }
    
    //================================================
    // INPUT: none
    // OUTPUT: none
    // gets input from user and calls recursive remove
    //================================================
    void BST::remove()
    {
    	int key;
    	cout << "Enter a number to remove\n";
    	cin >> key;
    	cin.get();
    	if(remove(key, root) == 1)
    		cout << "Number not found.\n";
    }
    
    //============================================
    // INPUT: none
    // OUTPUT: none
    // wrapper function for display
    //============================================
    void BST::display()
    {
    	display(root);
    }
    
    //============================================
    // INPUT: pointer to a node
    // OUTPUT: none
    // recursively inserts a new node into the BST
    //============================================
    void BST::insert(int newElement, node *& troot)
    {
    	if(!troot)
    	{
    		troot = new node;
    		troot->element = newElement;
    		troot->left = NULL;
    		troot->right = NULL;
    		++num_in_tree;
    	}
    	else if(newElement < troot->element)
    	{
    		insert(newElement, troot->left);
    	}
    	else
    	{
    		insert(newElement, troot->right);
    	}
    }
    
    //================================================
    // INPUT: pointer to a node
    // OUTPUT: 1 if element to be deleted is not found
    //		   0 if element is successfully deleted
    //================================================
    int BST::remove(int oldElement, node *& troot)
    {
    	if(!troot)
    	{
    		return 1;  //error code
    	}
    	else if(oldElement < troot->element)
    	{
    		remove(oldElement, troot->left);
    	}
    	else if(oldElement > troot->element)
    	{
    		remove(oldElement, troot->right);
    	}
    	else if(children(troot) == 2)
    	{
    		troot->element = inorderSuccessor(troot->right)->element;
    		remove(troot->element, troot->right);
    	}
    	else
    	{
    		if(troot->left)
    		{
    			troot->element = troot->left->element;
    			remove(troot->element, troot->left);
    		}
    		else if(troot->right)
    		{
    			troot->element = troot->right->element;
    			remove(troot->element, troot->right);
    		}
    		else
    		{
    			node * oldNode = troot;
    			troot = NULL;
    			delete oldNode;
    			return 0;
    			--num_in_tree;
    		}
    	}
    }
    
    //=========================================
    // INPUT: pointer to a node
    // OUTPUT: pointer to the inorder successor 
    //         of the input node
    //=========================================
    node * BST::inorderSuccessor(node *& troot)
    {
    	if(!troot->left)
    	{
    		return troot;
    	}
    	else
    	{
    		inorderSuccessor(troot->left);
    	}
    }
    
    //==================================
    // INPUT: pointer to a node
    // OUTPUT: 0 if node has no children
    //		   1 if node has 1 child
    //         2 if node has 2 children
    //==================================
    int BST::children(node * troot)
    {
    	if(troot->left && troot->right)
    	{
    		return 2;
    	}
    	else if(troot->left || troot->right)
    	{
    		return 1;
    	}
    	else
    	{
    		return 0;
    	}
    }
    
    //=========================================
    // INPUT: pointer to a node
    // OUTPUT: contents of tree in sorted order
    // recursively prints contents of the BST
    //=========================================
    void BST::display(node * troot)
    {
    	if(troot)
    	{
    		display(troot->left);
    		cout << troot->element << endl;
    		display(troot->right);
    	}
    }
    
    //================================
    // INPUT: pointer to a node
    // OUTPUT: none
    // recursively deletes the BST 
    //================================
    void BST::destroy(node *& troot)
    {
    	if(troot)
    	{
    		destroy(troot->left);
    		destroy(troot->right);
    		delete troot;
    	}
    	troot = NULL;
    }

  2. #2
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,788
    Code:
    	void insert();
    	void remove();
    	void display();
    Not to useable interface in any real application. No application want your class interact directly with the user. Your class should represent a Tree, should provide methods to work with the tree, should be fully independend from the input method. If I take this class and want to fill it from the file - I fail, If I want to provide some GUI for user convinience - I fail, this class is unusable.

    You should remove all connection to <iostream> from your class

    Code:
    return 0;
    --num_in_tree;
    strange sequence of commands

    don't you get warning that not all paths in the BST::remove(int oldElement, node *& troot)
    return values?

    And why not to make it a little more generic making it a template replacing

    int element;
    by
    T element;?
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    – David J. Wheeler

  3. #3
    Kiss the monkey. CodeMonkey's Avatar
    Join Date
    Sep 2001
    Posts
    937
    I couldn't help but notice that you never destroy from anywhere but the root.
    Code:
    template <class T> struct node
    {
            T element;
            node<T> * left;
            node<T> * right;
    };
    
    template <class T> class BST
    {
    public:     
            BST();
            ~BST();
            //display(node<T> * = root);  
                 // -- consider returning an std::string or having it take a stream reference as a parameter
            void destroy(node<T> *& troot = root);
            void insert(T newElement, node<T> *& troot = root);
            int remove(T oldElement, node<T> *& troot = root);
            const int population() { return num_in_tree; }
    private:
            node<T> * root;
            int num_in_tree;
            node<T> * inorderSuccessor(node<T> *& troot);
            int children(node<T> * troot);
           
    };
    "If you tell the truth, you don't have to remember anything"
    -Mark Twain

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by CodeMonkey
    I couldn't help but notice that you never destroy from anywhere but the root.
    Incorrect.
    The recursive calls that pass in troot->left and troot->right, actually modify troot->left and troot->right, and being that they are the root of their own subtree it can delete from anywhere.
    I'm not saying the the rest of the function is totally correct though.

  5. #5
    Registered User StevenGarcia's Avatar
    Join Date
    Nov 2006
    Posts
    22
    I appreciate you taking the time to look at it guys. You've given me some areas I can improve on. Thanks.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Input Spatial Data for BSP Tree
    By thetinman in forum Game Programming
    Replies: 2
    Last Post: 10-03-2007, 01:26 PM
  2. searching and insertion in a binary search tree
    By galmca in forum C Programming
    Replies: 1
    Last Post: 03-26-2005, 05:15 PM
  3. Tutorial review
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 03-22-2004, 09:40 PM
  4. "if you love someone" :D
    By Carlos in forum A Brief History of Cprogramming.com
    Replies: 12
    Last Post: 10-02-2003, 01:10 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM