C++

Forum

 
Binary Search Tree Implementation

stdeez (70)
It's been a year since I've coded so I apologize for being a noob. Anyways I'm implementing a Binary Search Tree class and I understand the concepts but my coding practice is rusty.

below is my code, the class, excluding the public functions is the basis for which I am to build my tree. Each node in the tree is supposed to be "by definition, the root of a binary search tree".


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
 

template <typename Comparable>
class BinarySearchTree{
    
    public:
        BinarySearchTree(); //default constructor.
        BinarySearchTree(Comparable & thisElement); //parameterized constructor.
        //void insert(const Comparable & x, BinaryNode *root); //insert node into the tree.
        
        
    private:
        struct BinaryNode{
            Comparable element;
            BinarySearchTree<Comparable> *left;
            BinarySearchTree<Comparable> *right;
            
            BinaryNode(const Comparable & theElement, BinarySearchTree<Comparable> *leftTree, BinarySearchTree<Comparable> *rightTree) : element(theElement), left(leftTree), right(rightTree){}
        };
        
        BinaryNode *root;
};


template <typename Comparable>
BinarySearchTree<Comparable>::BinarySearchTree(){

    BinaryNode *newTree;
    newTree=new BinaryNode;
    newTree->element=NULL;
    newTree->left=NULL;
    newTree->right=NULL;
    root=NULL;
    
}

template<typename Comparable>
BinarySearchTree<Comparable>::BinarySearchTree(Comparable & thisElement){
    
    BinaryNode *newTree;
    newTree=new BinaryNode(thisElement,NULL,NULL);
    
    if (root==NULL)
        root=newTree;
    
}




when i declare an object of it in main i get errors if i try to apply parameters like so:

 
 
BinarySearchTree<int> *t(6);


but without the parentheses and input it will build a normal no argument binaryTree, just wondering if someone can point out the problem i cant remember how to do this... would i have to make a function to set the value of its element? im hoping there is a simpler way.
Smac89 (1727)
That is because you are declaring a pointer type and pointers do not take parameters.

Dynamically allocate the object instead if you plan to use pointers:
1
2
3
4
5
 
BinarySearchTree<int> *t;
t = new BinarySearchTree<int>(6);

// or stack allocation
BinarySearchTree<int> t(6);
Last edited on
stdeez (70)
neither of these solutions work :/ sorry
Smac89 (1727)
Implement the following constructor for your class:

explicit BinarySearchTree(const Comparable &thisElement);

This should fix it
ne555 (10692)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
template <typename Comparable>
BinarySearchTree<Comparable>::BinarySearchTree(){

    BinaryNode *newTree;
    newTree=new BinaryNode;
    newTree->element=NULL;
    newTree->left=NULL;
    newTree->right=NULL;
    root=NULL;
    
} //newTree dies here. Memory leak


template<typename Comparable>
BinarySearchTree<Comparable>::BinarySearchTree(Comparable & thisElement){
    
    BinaryNode *newTree;
    newTree=new BinaryNode(thisElement,NULL,NULL);
    
    if (root==NULL) //root is uninitialized at this point
        root=newTree;
    
}
stdeez (70)
i dont get it
stdeez (70)
the biggest problem is for me, that we have to initialize each one as a binaryysearchtree and the node is a private data member. So to access its values and such ill have to make a function that returns its stored value and from main access it via the function call?
stdeez (70)
the only way i can make it work logically in my head is that the first object created is the root, unless of course i made another BinaryNode data member in the class, say "BinaryNode *TheRoot;"

and use TheRoot for the first object created and use root for each other object, since they all have to be "the root of a binarySearchTree by definition", any advice?
Topic archived. No new replies allowed.