C++

Forum

 
Binary Search Tree With Templates

hbcpp (197)
I have written a working binary search tree, then I went on to change it so that it working with different types. All is well excep for one line that stops the program from compiling.

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
 
#Include <iostream>

using namespace std;

template<typename T>
struct Node
{
public:
    Node<T> *pLeft;
    Node<T> *pRight;
    T val;

    Node<T>(T val)
    {
        this->val = val;
        pLeft = pRight = nullptr;
    }
};

template<typename T>
class Tree
{
    Node<T> *root;

    Node<T> *insert_at_sub(T i, Node<T> *p);
    void print_sub(Node<T> *p);
    int t_size = 0;

public:
    Tree ()
    {
        root = nullptr;
    }

    void add(T i)
    {
        ++t_size;
        root = insert_at_sub(i, root);
    }
    void print()
    {
        print_sub(root);
    };

    bool contain(T i)
    {
        return contain_sub(i, root);
    }
    bool contain_sub(T i, Node<T> *p);

    void test()
    {
        cout << root->pRight->pRight->pRight->pLeft->pRight->val << endl;
    }

    int get_size()
    {
        return t_size;
    }
};

template<typename T>
Node* Tree<T>::insert_at_sub(T i, Node<T> *p) // this is where the error occurs
{
    if( ! p )
        return new Node<T>(i);
    else if (i <= p->val)
        p->pLeft = insert_at_sub(i, p->pLeft);
    else if (i > p->val)
        p->pRight = insert_at_sub(i, p->pRight);

    return p;
}

template<typename T>
void Tree<T>::print_sub(Node<T> *p)
{
    if(p)
    {
        print_sub(p->pLeft);
        cout << p->val << endl;
        print_sub(p->pRight);
    }
}

template<typename T>
bool Tree<T>::contain_sub(T i, Node<T> *p)
{
    if (!p)
        return false;
    else if(i == p->val)
        return true;
    else if (i <= p->val)
        contain_sub(i, p->pLeft);
    else
        contain_sub(i, p->pRight);
}

int main()
{
    Tree<int> tr;

    tr.add(4);
    tr.add(6);
    tr.add(1);
    tr.add(9);
    tr.add(2);
    tr.add(0);
    tr.add(89);
    tr.add(12);
    tr.add(32);
    tr.add(5);
    tr.add(22);

    tr.print();

    return 0;
}


The error occurs in the line 59
the error that this program produces:
error: deduced class type 'Node' in function return type
Last edited on
lastchance (6980)
The error probably comes from line 21, which isn't fully templated. For int write T.

On line 59 the return type should be Node<T>*
i.e. you need to template that also.

Please include the relevant #includes when you post code.
Last edited on
hbcpp (197)
I corrected that line but the problem continues the same.
lastchance (6980)
I was editing my post to include a comment about line 59. Have you done that also?
lastchance (6980)
To confirm:

Line 21, currently
Node<T> *insert_at_sub(int i, Node<T> *p);
should be:
Node<T> *insert_at_sub(T i, Node<T> *p);


Line 59, currently
Node* Tree<T>::insert_at_sub(T i, Node<T> *p)
should be
Node<T>* Tree<T>::insert_at_sub(T i, Node<T> *p)


Please make sure that you have the relevant headers to allow us to compile this online. In this instance, to avoid other changes in your code, you require
1
2
 
#include <iostream>
using namespace std;



The output (on cpp.sh) is then
0
1
2
4
5
6
9
12
22
32
89
Last edited on
hbcpp (197)
@lastchance Thanks it works.
Topic archived. No new replies allowed.