Having some trouble with a Binary Search Tree & template class

liero (17)
I'm having a bit of trouble figuring out how to solve this one, so any help is appreciated.

I believe the problem might be something to do with this line in BSTree1.h -
root = new NodePtr(NULL, NULL, NULL, NULL, NULL);
I'm not sure what to use instead of NULL for the first two parameters, because KT and DT are unknown (it's a template class).

Then again, it could be that the problem isn't even with that line, which is why I'm asking for help here ;-)

I'd like to know what I need to do to get this to compile.

So, the code/error messages...

After using "Execute" > "Compile" in Dev-C++, the compile log says this:

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
 
Compiler: Default compiler
Building Makefile: "C:\Users\Shane\Documents\Data Structures\Dev-C++\Prac3\Makefile.win"
Executing  make...
make.exe -f "C:\Users\Shane\Documents\Data Structures\Dev-C++\Prac3\Makefile.win" all
g++.exe -c TestBSTree.cpp -o TestBSTree.o -I"C:/Dev-Cpp/lib/gcc/mingw32/3.4.2/include"  -I"C:/Dev-Cpp/include/c++/3.4.2/backward"  -I"C:/Dev-Cpp/include/c++/3.4.2/mingw32"  -I"C:/Dev-Cpp/include/c++/3.4.2"  -I"C:/Dev-Cpp/include"   

BSTree1.h: In constructor `BSTree<KT, DT>::BSTree() [with KT = int, DT = TestData]':
TestBSTree.cpp:48:   instantiated from here
BSTree1.h:47: error: new initializer expression list treated as compound expression

BSTree1.h:47: error: invalid conversion from `int' to `BSTree<int, TestData>::BSTreeNode*'

BSTree1.h:47: error: cannot convert `BSTree<int, TestData>::BSTreeNode**' to `BSTree<int, TestData>::BSTreeNode*' in assignment

BSTree1.h: In member function `void BSTree<KT, DT>::deleteSubtree(BSTree<KT, DT>::BSTreeNode*) const [with KT = int, DT = TestData]':
BSTree1.h:59:   instantiated from `BSTree<KT, DT>::~BSTree() [with KT = int, DT = TestData]'
TestBSTree.cpp:48:   instantiated from here
BSTree1.h:22: error: `BSTree<int, TestData>::BSTreeNode*BSTree<int, TestData>::BSTreeNode::rightPtr' is private

BSTree1.h:172: error: within this context

BSTree1.h:21: error: `BSTree<int, TestData>::BSTreeNode*BSTree<int, TestData>::BSTreeNode::leftPtr' is private

BSTree1.h:174: error: within this context

BSTree1.h:21: error: `BSTree<int, TestData>::BSTreeNode*BSTree<int, TestData>::BSTreeNode::leftPtr' is private

BSTree1.h:179: error: within this context

BSTree1.h: In member function `void BSTree<KT, DT>::showSubtree(BSTree<KT, DT>::BSTreeNode*, int) const [with KT = int, DT = TestData]':
BSTree1.h:132:   instantiated from `void BSTree<KT, DT>::showStructure() const [with KT = int, DT = TestData]'
TestBSTree.cpp:54:   instantiated from here
BSTree1.h:22: error: `BSTree<int, TestData>::BSTreeNode*BSTree<int, TestData>::BSTreeNode::rightPtr' is private

BSTree1.h:150: error: within this context

BSTree1.h:132:   instantiated from `void BSTree<KT, DT>::showStructure() const [with KT = int, DT = TestData]'

TestBSTree.cpp:54:   instantiated from here
BSTree1.h:22: error: `BSTree<int, TestData>::BSTreeNode*BSTree<int, TestData>::BSTreeNode::rightPtr' is private

BSTree1.h:156: error: within this context

BSTree1.h:21: error: `BSTree<int, TestData>::BSTreeNode*BSTree<int, TestData>::BSTreeNode::leftPtr' is private

BSTree1.h:156: error: within this context

BSTree1.h:22: error: `BSTree<int, TestData>::BSTreeNode*BSTree<int, TestData>::BSTreeNode::rightPtr' is private

BSTree1.h:158: error: within this context

BSTree1.h:21: error: `BSTree<int, TestData>::BSTreeNode*BSTree<int, TestData>::BSTreeNode::leftPtr' is private

BSTree1.h:160: error: within this context

BSTree1.h:21: error: `BSTree<int, TestData>::BSTreeNode*BSTree<int, TestData>::BSTreeNode::leftPtr' is private

BSTree1.h:165: error: within this context

BSTree1.h: In member function `KT& BSTree<KT, DT>::BSTreeNode::key() [with KT = int, DT = TestData]':
BSTree1.h:155:   instantiated from `void BSTree<KT, DT>::showSubtree(BSTree<KT, DT>::BSTreeNode*, int) const [with KT = int, DT = TestData]'
BSTree1.h:132:   instantiated from `void BSTree<KT, DT>::showStructure() const [with KT = int, DT = TestData]'
TestBSTree.cpp:54:   instantiated from here
BSTree1.h:29: error: invalid type argument of `unary *'

make.exe: *** [TestBSTree.o] Error 1

Execution terminated


This is the code I'm using:

BSTree1.h
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
 
#ifndef BSTREE_1_H
#define BSTREE_1_H
template <typename KT, typename DT>
class BSTree {
	
	private:
		
		class BSTreeNode;
		typedef BSTreeNode* NodePtr; // Define a new type called "NodePtr", which points to a BSTreeNode's address in memory
		class BSTreeNode {
			BSTreeNode(const KT& key, const DT& data, NodePtr parent, NodePtr left, NodePtr right) {
				keyValue = key;
				dataItem = data;
				parentPtr = parent;
				leftPtr = left;
				rightPtr = right;
			}
			DT dataItem;
			KT keyValue;
			NodePtr parentPtr;
			NodePtr leftPtr;
			NodePtr rightPtr;
			
			public:
				KT key() const {
					return keyValue;
				}
				KT& key() {
					return *keyValue;
				}
				DT data() const {
					return dataItem;
				}
				DT& data() {
					return *dataItem;
				}
		};
		
	public:
		
		/**
		 * Default constructor
		 */
		BSTree() {
			return;
			nodeCount = 0;
			root = new NodePtr(NULL, NULL, NULL, NULL, NULL);
		}

//REST OF THE CODE REMOVED (not needed?)

};


TestBSTree.cpp
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
 
#include <cstdlib>
#include <iostream>
#include <string>
#include <stdexcept>
using namespace std;

#include "BSTree1.h"

//-------------------------------------------------------
//
// Declaration for the BSTree data item class
//

class TestData
{
	public:
		
		void setKey (int newKey) {
			keyField = newKey;		// Set the key
		}
		int key() const {
			return keyField;		// Returns the key
		}
		
	private:
		
		int keyField;				// Key for the data item
};

//-------------------------------------------------------

void print_help()
{
	cout << endl << "Commands:" << endl;
	cout << "  P    : Help (displays this message)" << endl;
	cout << "  +key : Insert (or update) data item" << endl;
	cout << "  ?key : Retrieve data item" << endl;
	cout << "  -key : Remove data item" << endl;
	cout << "  K    : Write keys in ascending order" << endl;
	cout << "  C    : Clear the tree" << endl;
	cout << "  E    : Empty tree?" << endl;
	cout << "  F    : Full tree?" << endl;
	cout << "  Q    : Quit the test program" << endl;
	cout << endl;
}

int main(int argc, char *argv[]) {
	BSTree<int, TestData> testTree;
	TestData testData;
	int inputKey;
	char cmd;
	print_help();

//REST OF THE CODE REMOVED (not needed?)

}
Last edited on
liero (17)
Bump?
firedraco (6243)
BSTreeNode must also be a template class in order to use templates given to BSTree.
liero (17)
Hmm... I didn't realise that. Thanks for replying, and for the tip. Will try making BSTreeNode into a template class.
Topic archived. No new replies allowed.