Bst Tree

This is a discussion on Bst Tree within the C++ Programming forums, part of the General Programming Boards category; I still can't get this to work I tried some of the early suggestions but I still can't either get ...

  1. #1
    Registered User
    Join Date
    Aug 2001
    Posts
    84

    Bst Tree

    I still can't get this to work I tried some of the early suggestions but I still can't either get the client file correct or my functions are not correct.

    This locks up. I am not sure how I should cll my functions in the client
    file to make the BST and do the different functions.PreOrder()etc...


    #include<iostream>
    #include<iomanip>
    #include<fstream>
    #include <cctype> // defines isalpha() function

    #include"TreeImplementation.cpp"

    using namespace std;


    int main()
    {



    btree bt;
    int num=0;
    char chr;
    int count=0;
    int *leaf1;

    ifstream fin("input.txt");
    ofstream fout("output1.txt");

    fin>>num;
    fin>>chr;
    while(fin)
    {
    bt.insert(num);
    //bt.search(num);
    bt.InorderTranverse(leaf1);

    fout<<num;
    count++;
    fout<<"Step: "<<count<<" "<<"Data Value = "<<num<<" "<<"Activity Signal = "<<chr<<endl;


    fout<<"Preorder Transversal = "<<endl<<endl;
    fout<<"Inorder Transversal = "<<endl<<endl;
    fout<<"Post order Transversal = "<<endl<<endl;
    fout<<"Level by Level Transversal = "<<endl<<endl;
    fout<<"Total Number of nodes = "<<count<<endl<<endl;

    fin>>num;
    fin>>chr;
    }


    return 0;
    }

    header
    struct node
    {
    int key_value;
    node *left;
    node *right;
    };


    class btree
    {
    public:
    // node *root;
    btree();
    // ~btree();
    void destroy_tree(node *leaf);
    void insert(int key, node *leaf);
    node *search(int key, node *leaf);
    //node *GetRoot(); {return (root);
    //public:
    void insert(int key);
    node *search(int key);
    //void destroy_tree();
    void InorderTranverse(node *leaf);
    //void preOrderTranverse(node *leaf);
    //void PostOrderTranverse(node *leaf);
    private:
    node *root;
    };
    node *RChild(node *leaf);
    node *LChild(node *leaf);

    Implementation

    #include<iostream.h>
    #include"Treeheader.h"



    //Constructor
    ///////////////////////////////////////////////////////////////////////
    btree::btree()
    {
    root=NULL;
    }


    ///////////////////////////////////////////////////////////////////////
    /*btree::~btree()
    {
    destroy_tree(root);
    }
    */
    //Destriy tree function
    //////////////////////////////////////////////////////////////////////
    void destroy_tree(node *leaf)
    {
    if(leaf!=NULL)
    {
    destroy_tree(leaf->left);
    destroy_tree(leaf->right);
    delete leaf;
    }
    }

    //Insert Tree
    //////////////////////////////////////////////////////////////////////
    void btree::insert(int key, node *leaf)
    {
    if(key< leaf->key_value)
    {
    if(leaf->left!=NULL)
    insert(key, leaf->left);
    else
    {
    leaf->left=new node;
    leaf->left->key_value=key;
    leaf->left->left=NULL; //Sets the left child of the child node to null
    leaf->left->right=NULL; //Sets the right child of the child node to null
    }
    }
    else if(key>=leaf->key_value)
    {
    if(leaf->right!=NULL)
    insert(key, leaf->right);
    else
    {
    leaf->right=new node;
    leaf->right->key_value=key;
    leaf->right->left=NULL; //Sets the left child of the child node to null
    leaf->right->right=NULL; //Sets the right child of the child node to null
    }
    }
    }


    ///////////////////////////////////////////////////////////////////////

    node *btree::search(int key, node *leaf)
    {
    if(leaf!=NULL)
    {
    if(key==leaf->key_value)
    return leaf;
    if(key<leaf->key_value)
    return search(key, leaf->left);
    else
    return search(key, leaf->right);
    }
    else return NULL;
    }


    ///////////////////////////////////////////////////////////////////////

    void btree::insert(int key)
    {
    if(root!=NULL)
    insert(key, root);
    else
    {
    root=new node;
    root->key_value=key;
    root->left=NULL;
    root->right=NULL;
    }
    }


    //////////////////////////////////////////////////////////////////////

    node *btree::search(int key)
    {
    return search(key, root);
    }


    ///////////////////////////////////////////////////////////////////////

    /*void btree::destroy_tree(node *root)
    {
    if(root != NULL)
    destroy_tree(
    destroy_tree(root);
    }
    */

    //////////////////////////////////////////////////////////////////////
    void btree::InorderTranverse(node *leaf)
    {

    if(leaf != NULL)
    InorderTranverse(LChild(leaf));
    cout<<leaf;
    InorderTranverse(RChild(leaf));
    }

    //////////////////////////////////////////////////////////////////////
    node *LChild(node *leaf)
    {
    return (leaf==NULL) ? NULL : leaf->left;
    }

    //////////////////////////////////////////////////////////////////////
    node *RChild(node *leaf)
    {
    return (leaf==NULL) ? NULL : leaf->right;
    }

    //PreOrder Tranverse
    ///////////////////////////////////////////////////////////////////////
    /*void btree:reOrderTranverse(node *leaf)
    {
    if(leaf != NULL){
    cout<<leaf;
    preOrderTranverse(LChild(leaf));
    preOrderTranverse(RChild(leaf));
    }
    }
    //PostOrderTranverse
    ///////////////////////////////////////////////////////////////////////
    void btree::PostOrderTranverse(node *leaf)
    {
    if(leaf != NULL){
    PostOrderTranverse(LChild(leaf));
    PostOrderTranverse(RChild(leaf));
    }
    }

    //////////////////////////////////////////////////////////////////////
    node *GetRoot(); {return (root);
    {


    }*/

  2. #2
    zen
    zen is offline
    of Zen Hall zen's Avatar
    Join Date
    Aug 2001
    Posts
    1,007
    OK, here's a cut down version of your tree that just inserts and does an InOrderTransversal (the other traversal functions can be done in the same manner) -

    Code:
    #include<iostream> 
    #include<iomanip> 
    #include<fstream> 
    #include <cctype> // defines isalpha() function 
    
    using namespace std; 
    
    
    struct node 
    { 
    	int key_value; 
    	node *left; 
    	node *right; 
    }; 
    
    
    class btree 
    { 
    public: 
    	btree(); 
    	void insert(int key); 
    	void InOrderTranverse();
    	
    private:
    	void insert(int key, node *leaf); 
    	void InOrderTranverse(node *leaf); 
    	node *root; 
    }; 
    
    int main() 
    { 
    
    	btree bt; 
    	int num=0; 
    	char chr; 
    	
    	cin>>num; 
    	cin>>chr; 
    	
    	while(cin) 
    	{ 
    		bt.insert(num);
    		cout << "InOrderTranverse: ";
    		bt.InOrderTranverse();
    		cout << endl;	 
    		cout<<"Step: "<<count<<" "<<"Data Value = "<<num<<" "<<"Activity Signal = "<<chr<<endl; 
    	
    		cin>>num; 
    		cin>>chr; 
    
    	} 
    
    
    	return 0; 
    } 
    
    
    
    
    
    //Constructor 
    /////////////////////////////////////////////////////////////////////// 
    btree::btree() 
    { 
    	root=NULL; 
    } 
    
    
    //Insert Tree 
    ////////////////////////////////////////////////////////////////////// 
    void btree::insert(int key, node *leaf) 
    { 
    	if(key< leaf->key_value) 
    	{ 
    		if(leaf->left!=NULL) 
    		insert(key, leaf->left); 
    		else 
    		{ 
    			leaf->left=new node; 
    			leaf->left->key_value=key; 
    			leaf->left->left=NULL; //Sets the left child of the child node to null 
    			leaf->left->right=NULL; //Sets the right child of the child node to null 
    		} 
    	} 
    	else if(key>=leaf->key_value) 
    	{ 
    		if(leaf->right!=NULL) 
    			insert(key, leaf->right); 
    		else 
    		{ 
    			leaf->right=new node; 
    			leaf->right->key_value=key; 
    			leaf->right->left=NULL; //Sets the left child of the child node to null 
    			leaf->right->right=NULL; //Sets the right child of the child node to null 
    		} 
    	} 
    } 
    
    
    
    
    /////////////////////////////////////////////////////////////////////// 
    
    void btree::insert(int key) 
    { 
    	if(root!=NULL) 
    		insert(key, root); 
    	else 
    	{ 
    		root=new node; 
    		root->key_value=key; 
    		root->left=NULL; 
    		root->right=NULL; 
    	} 
    } 
    
    
    
    ////////////////////////////////////////////////////////////////////// 
    
    void btree::InOrderTranverse(node *leaf) 
    { 
    
    	if(leaf->left != NULL) 
    		InOrderTranverse(leaf->left); 
    	cout<<leaf->key_value<< " ";
    	if(leaf->right !=NULL) 
    		InOrderTranverse(leaf->right); 
    } 
    ////////////////////////////////////////////////////////////////////// 
    void btree::InOrderTranverse() 
    { 
    	if(root!=NULL) 
    		InOrderTranverse(root); 
    	else 
    		return;
    }

    If you are unsure on anything post a reply instead of waiting a few days and then reposting the same question again.
    zen

  3. #3
    Registered User
    Join Date
    Aug 2001
    Posts
    84

    Zen or anyone else.

    In a BST, do you really need a destructor or a destroy tree?

  4. #4
    zen
    zen is offline
    of Zen Hall zen's Avatar
    Join Date
    Aug 2001
    Posts
    1,007
    If your tree is put into a class then you'll get a destructor whether you want one or not, so this would seem the logical place to delete all the nodes. If you don't delete them you'll get a memory leak.
    zen

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Interpreter.c
    By moussa in forum C Programming
    Replies: 4
    Last Post: 05-28-2008, 06:59 PM
  2. BST delete again, but this time I think I'm close
    By tms43 in forum C++ Programming
    Replies: 9
    Last Post: 11-05-2006, 06:24 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 04:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 11:45 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21