dimanche 1 octobre 2017

c++ template binary search tree

What I want is a rather simple binary search tree that via the template tag, allows for any numerical data to be used within it, but I'm having some rather obnoxious issues that I have no clue of how to get rid off, if anyone can help, it would be much appreciated. The error message that keeps popping up for me is "Invalid use of template-name 'BST' without an argument list" - and quite frankly I have no clue how to solve it. It occurs on line 31, 89, 105, 120, 130, 141 in the bst.cpp file:

Main.cpp

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

using namespace std;

int main()
{

BST <int> tree;
tree.insert(8);
tree.insert(25);
tree.insert(99);
tree.insert(20);
tree.insert(25);
tree.insert(20);
tree.insert(2);
tree.insert(89);
tree.insert(15);
tree.insert(10);
tree.insert(30);
tree.insert(50);
tree.displayorder();



int number;

int Inputnumber;
while (true){
    cout << "Choose what you want to do: " << endl << "1# Insert" << endl << "2# Display Orders" << endl <<  "3# Search" << endl << "4# Delete" << endl << endl << endl;
    cin >> Inputnumber;
    if (Inputnumber==1){
        cout << endl << "Enter the number you want inserted: ";
        cin >> number;
        tree.insert(number);
        cout << endl << endl << endl;
    }
    if (Inputnumber==2){
        cout<<"Display Orders: " << endl;
        tree.displayorder();
        cout << endl << endl << endl;
    }

    if (Inputnumber==3){
        cout<<"Enter the number you want to search for: ";
        cin >> number;
        tree.search(number);
        cout << endl << endl << endl;
    }
    if (Inputnumber==4){
        cout << "Enter the number you want to remove: ";
        cin >> number;
        tree.remove(number);
        cout << endl << endl << endl;
    }
}
}

bst.h

#ifndef BST_H
#define BST_H


template <class T>
class BST
{
struct node
{
    T data;
    node* left;
    node* right;
};

node* root;

node* makeEmpty(node* tree);

node* insert(T x, node* tree);

node* findMin(node* tree);

node* findMax(node* tree);

node* remove(T x, node* tree);

void inorder(node* tree);

void preorder(node* tree);



void postorder(node* tree);


public:
BST();

~BST();


node* find(node* tree, T x);

void insert(T x);

void remove(T x);

void displayorder();

void search(T x);
};

#endif // BST_H

bst.cpp

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

using namespace std;

template <class T>
void BST<T>::preorder(node* tree)
{
    if(tree == NULL){
        return;
    }
    cout << tree->data << " ";
    inorder(tree->left);
    inorder(tree->right);
}



template <class T>
void BST<T>::postorder(node* tree)
{
    if(tree == NULL){
        return;
    }
    inorder(tree->left);
    inorder(tree->right);
    cout << tree->data << " ";
}

template <typename T>
BST::node* BST<T>::find(node* tree, T x)        //AN ERROR OCCURS HERE
{
    if(tree == NULL)
        return NULL;
    else if(x < tree->data)
        return find(tree->left, x);
    else if(x > tree->data)
        return find(tree->right, x);
    else
        return tree;
}
template <typename T>
BST<T>::BST()
{
    root = NULL;
}

template <typename T>
BST<T>::~BST()
{
    root = makeEmpty(root);
}

template <class T>
void BST<T>::insert(T x)
{
    root = insert(x, root);
}

template <class T>
void BST<T>::remove(T x)
{
    root = remove(x, root);
}

template <class T>
void BST<T>::displayorder()
{
    inorder(root);
    cout << endl;
    preorder(root);
    cout << endl;
    postorder(root);
    cout << endl << endl;
}

template <class T>
void BST<T>::search(T x)
{
    if(root = find(root, x)){
        cout << endl << "Found!" << endl;
    }
    else{
        cout << endl << "Not Found!" << endl;
    }
}

template <class T>
BST::node* BST<T>::makeEmpty(node* tree)        //AN ERROR OCCURS HERE
{
    if(tree == NULL)
        return NULL;
    {
        makeEmpty(tree->left);
        makeEmpty(tree->right);
        delete tree;
    }
    return NULL;
}




template <class T>
BST::node* BST<T>::insert(T x, node* tree)      //AN ERROR OCCURS HERE
{
    if(tree == NULL)
    {
        tree = new node;
        tree->data = x;
        tree->left = tree->right = NULL;
    }
    else if(x < tree->data)
        tree->left = insert(x, tree->left);
    else if(x >= tree->data)
        tree->right = insert(x, tree->right);
    return tree;
}

BST::node* BST::findMin(node* tree)             //AN ERROR OCCURS HERE
{
    if(tree == NULL)
        return NULL;
    else if(tree->left == NULL)
        return tree;
    else
        return findMin(tree->left);
}

BST::node* BST::findMax(node* tree)             //AN ERROR OCCURS HERE
{
    if(tree == NULL)
        return NULL;
    else if(tree->right == NULL)
        return tree;
    else
        return findMax(tree->right);
}

template <typename T>
BST::node* BST<T>::remove(T x, node* tree)      //AN ERROR OCCURS HERE
{
    node* temp;
    if(tree == NULL)
        return NULL;
    else if(x < tree->data)
        tree->left = remove(x, tree->left);
    else if(x > tree->data)
        tree->right = remove(x, tree->right);
    else if(tree->left && tree->right)
    {
        temp = findMin(tree->right);
        tree->data = temp->data;
        tree->right = remove(tree->data, tree->right);
    }
    else
    {
        temp = tree;
        if(tree->left == NULL)
            tree = tree->right;
        else if(tree->right == NULL)
            tree = tree->left;
        delete temp;
    }

    return tree;
}

template <class T>
void BST<T>::inorder(node* tree)
{
    if(tree == NULL){
        return;
    }
    inorder(tree->left);
    cout << tree->data << " ";
    inorder(tree->right);
}

Aucun commentaire:

Enregistrer un commentaire