Data-Structures-Algorithms/BST.h at master · artun3e/Data-Structures-Algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
//
//  BST.h
//  artunsarioglu_cs300_hw2
//
//  Created by Artun on 20.07.2019.
//  Copyright © 2019 Artun. All rights reserved.
//

#ifndef BST_h
#define BST_h

#include <string>
#include <sstream>
#include <iostream>
#include <vector>

using namespace std;


// Node for our Binary Search Tree
template<class Comparable,class value>
struct BinaryNode
{
    Comparable element;
    value val;
    BinaryNode *left;
    BinaryNode *right;

    BinaryNode(const Comparable & theElement,const value & theVal ,BinaryNode *lt, BinaryNode *rt)
    :   element(theElement) , val(theVal),left(lt) , right(rt) {}
};

template <class Comparable,class value>
class BinarySearchTree
{

public:

    explicit BinarySearchTree( const Comparable & notFound,const value & Val );

    BinarySearchTree(); // Constructor --- comparable
  //  ~BinarySearchTree( ); // Destructor

    const Comparable & findMin( ) const;
    const Comparable & findMax( ) const;
    const Comparable & find( const Comparable & x ) const; //updated and okay now
    bool isEmpty( ) const;
    void makeEmpty( );
    void insert( const Comparable & x,value theValue ); //updated -- now checking -- and okey now --   COMPARABLE
    void remove( const Comparable & x );  //updated -- now checking -- and okey now -COMPARABLE
    BinaryNode<Comparable, value> * updateNode(Comparable & element); // updated
    value getNode(Comparable & element);
    const BinarySearchTree & operator=(const BinarySearchTree & rhs );

private:

    BinaryNode<Comparable,value> *root;
    const Comparable ITEM_NOT_FOUND;
    const Comparable & elementAt( BinaryNode<Comparable,value> *t ) const; //check this
    void insert( const Comparable & x,value theValue ,BinaryNode<Comparable,value> * & t ) const; //updated -- and okey now
    void remove( const Comparable & x, BinaryNode<Comparable,value> * & t ) const; // updated -- and okey now
    BinaryNode<Comparable,value> * findMin( BinaryNode<Comparable,value> *t ) const;
    BinaryNode<Comparable,value> * findMax( BinaryNode<Comparable,value> *t ) const;
    BinaryNode<Comparable,value> * find( const Comparable & x,BinaryNode<Comparable,value> *t ) const;
    void makeEmpty( BinaryNode<Comparable,value> * & t ) const;
    BinaryNode<Comparable,value> * clone( BinaryNode<Comparable,value> *t ) const;

};

#endif /* BST_h */