C++

Forum

 
Asking for help with binaryTreeType

Bopaki (407)
The code for the binaryTreeType is very long but follows next

Here is my main function:
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
 
using namespace std; 
void print(int& x); 
void update(int& x);
int main() 
{ 
    bSearchTreeType<int> treeRoot; 
    int num; 
    cout << "Line 10: Enter numbers ending with -999"
    << endl; 
    cin >> num; 
    while (num != -999) 
     { 
          treeRoot.insert(num); 
            cin >> num;
     }
     cout << endl << " Tree nodes in inorder: ";
    treeRoot.inorderTraversal(print);
     cout << endl << " Tree Height: "
          << treeRoot.treeHeight()
          << endl << endl; 
     cout << "******* Update Nodes *******"
          << endl;
     treeRoot.inorderTraversal(update);
     cout << " Tree nodes in inorder after "
          << "the update: " << endl << " ";
     treeRoot.inorderTraversal(print);
      cout << endl <<" Tree Height: "
           << treeRoot.treeHeight() << endl;
       return 0; 
}
void print(int& x)
{ 
     cout << x << " ";
} 
void update(int& x) 
{ 
    x = 2 * x;
}

I get these error messages when compiling:
1
2
3
4
5
6
7
8
9
10
11
 
 bSearchTree.cpp: In function `int main()':
C:\Dev-Cpp\Chapter11\bSearchTree.cpp:464: error: invalid conversion from `void (*)(int&)' to `int'
C:\Dev-Cpp\Chapter11\bSearchTree.cpp:464: error:   initializing argument 1 of `void bSearchTreeType<elemType>::inorderTraversal(const elemType&) [with elemType = int]'

C:\Dev-Cpp\Chapter11\bSearchTree.cpp:470: error: invalid conversion from `void (*)(int&)' to `int'
C:\Dev-Cpp\Chapter11\bSearchTree.cpp:470: error:   initializing argument 1 of `void bSearchTreeType<elemType>::inorderTraversal(const elemType&) [with elemType = int]'
C:\Dev-Cpp\Chapter11\bSearchTree.cpp:473: error: invalid conversion from `void (*)(int&)' to `int'
C:\Dev-Cpp\Chapter11\bSearchTree.cpp:473: error:   initializing argument 1 of `void bSearchTreeType<elemType>::inorderTraversal(const elemType&) [with elemType = int]'

Execution terminated
Bopaki (407)
here is the binaryTreeType:
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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
 
#include<iostream>
using namespace std;
//*************************************************************
// Author: D.S. Malik
//
// class binaryTreeType
// This class specifies the basic operations to implement a
// binary tree.
//*************************************************************
//Definition of the node
template <class elemType>
struct binaryTreeNode
{
elemType info;
binaryTreeNode<elemType> *llink;
binaryTreeNode<elemType> *rlink;
};
//Definition of the class
template <class elemType>
class binaryTreeType
{
public:
const binaryTreeType<elemType>& operator=
(const binaryTreeType<elemType>&);
//Overload the assignment operator.
bool isEmpty() const;
//Returns true if the binary tree is empty;
//otherwise, returns false.
void inorderTraversal() const;
//Function to do an inorder traversal of the binary tree.
void preorderTraversal() const;
//Function to do a preorder traversal of the binary tree.
void postorderTraversal() const;
//Function to do a postorder traversal of the binary tree.
int treeHeight() const;
//Returns the height of the binary tree.
int treeNodeCount() const;
//Returns the number of nodes in the binary tree.
int treeLeavesCount() const;
//Returns the number of leaves in the binary tree.
void destroyTree();
//Deallocates the memory space occupied by the binary tree.
//Postcondition: root = NULL;
binaryTreeType(const binaryTreeType<elemType>& otherTree);
//copy constructor
binaryTreeType();
//default constructor
~binaryTreeType();
//destructor
protected:
binaryTreeNode<elemType> *root;
private:
void copyTree(binaryTreeNode<elemType>* &copiedTreeRoot,
binaryTreeNode<elemType>* otherTreeRoot);
//Makes a copy of the binary tree to which
//otherTreeRoot points. The pointer copiedTreeRoot
//points to the root of the copied binary tree.
void destroy(binaryTreeNode<elemType>* &p);
//Function to destroy the binary tree to which p points.
//Postcondition: p = NULL
void inorder(binaryTreeNode<elemType> *p) const;
//Function to do an inorder traversal of the binary
//tree to which p points.
void preorder(binaryTreeNode<elemType> *p) const;
//Function to do a preorder traversal of the binary
//tree to which p points.
void postorder(binaryTreeNode<elemType> *p) const;
//Function to do a postorder traversal of the binary
//tree to which p points.
int height(binaryTreeNode<elemType> *p) const;
//Function to return the height of the binary tree
//to which p points.
int max(int x, int y) const;
//Returns the larger of x and y.
int nodeCount(binaryTreeNode<elemType> *p) const;
//Function to return the number of nodes in the binary
//tree to which p points
int leavesCount(binaryTreeNode<elemType> *p) const;
//Function to return the number of leaves in the binary
//tree to which p points
};
template <class elemType>
bool binaryTreeType<elemType>::isEmpty() const
{
return (root == NULL);
}
template <class elemType>
binaryTreeType<elemType>::binaryTreeType()
{
root = NULL;
}
template <class elemType>
void binaryTreeType<elemType>::inorderTraversal() const
{
inorder(root);
}
template <class elemType>
void binaryTreeType<elemType>::preorderTraversal() const
{
preorder(root);
}
template <class elemType>
void binaryTreeType<elemType>::postorderTraversal() const
{
postorder(root);
}
template <class elemType>
int binaryTreeType<elemType>::treeHeight() const
{
return height(root);
}
template <class elemType>
int binaryTreeType<elemType>::treeNodeCount() const
{
return nodeCount(root);
}
template <class elemType>
int binaryTreeType<elemType>::treeLeavesCount() const
{
return leavesCount(root);
}
template <class elemType>
void binaryTreeType<elemType>::
inorder(binaryTreeNode<elemType> *p) const
{
if (p != NULL)
{
inorder(p->llink);
cout << p->info << " ";
inorder(p->rlink);
}
}
template <class elemType>
void binaryTreeType<elemType>::
preorder(binaryTreeNode<elemType> *p) const
{
if (p != NULL)
{
cout << p->info << " ";
preorder(p->llink);
preorder(p->rlink);
}
}
template <class elemType>
void binaryTreeType<elemType>::
postorder(binaryTreeNode<elemType> *p) const
{
if (p != NULL)
{
postorder(p->llink);
postorder(p->rlink);
cout << p->info << " ";
}
}
template <class elemType>
int binaryTreeType<elemType>::
height(binaryTreeNode<elemType> *p) const
{
if (p == NULL)
return 0;
else
return 1 + max(height(p->llink), height(p->rlink));
}
template <class elemType>
int binaryTreeType<elemType>::max(int x, int y) const
{
if (x >= y)
return x;
else
return y;
}
template <class elemType>
void binaryTreeType<elemType>::copyTree
(binaryTreeNode<elemType>* &copiedTreeRoot,
binaryTreeNode<elemType>* otherTreeRoot)
{
if (otherTreeRoot == NULL)
copiedTreeRoot = NULL;
else
{
copiedTreeRoot = new binaryTreeNode<elemType>;
copiedTreeRoot->info = otherTreeRoot->info;
copyTree(copiedTreeRoot->llink, otherTreeRoot->llink);
copyTree(copiedTreeRoot->rlink, otherTreeRoot->rlink);
}
} //end copyTree
template<class elemType>
void binaryTreeType<elemType>::destroy(binaryTreeNode<elemType>* &p)
{
if (p != NULL)
{
destroy(p->llink);
destroy(p->rlink);
delete p;
p = NULL;
}
}
template <class elemType>
void binaryTreeType<elemType>::destroyTree()
{
destroy(root);
}
     //destructor
template<class elemType>
binaryTreeType<elemType>::~binaryTreeType()
{
   destroy(root);
}
                              
              //copy constructor
template<class elemType>
binaryTreeType<elemType>::binaryTreeType
                  (const binaryTreeType<elemType> &otherTree)
{
      if(otherTree.root == NULL)  //otherTree is empty
         root = NULL;
      else
        copyTree(root, otherTree.root);
}
Bopaki (407)
And the inherited bsearchTreeType:
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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
 
template <class elemType>
class bSearchTreeType: public binaryTreeType<elemType>
{
public:
bool search(const elemType& searchItem) const;
//Function to determine if searchItem is in the binary
//search tree.
//Postcondition: Returns true if searchItem is found in the
// binary search tree; otherwise, returns false.
void insert(const elemType& insertItem);
//Function to insert insertItem in the binary search tree.
//Postcondition: If no node in the binary search tree has the
// same info as insertItem, a node with the info insertItem
// is created and inserted in the binary search tree.
void deleteNode(const elemType& deleteItem);
//Function to delete deleteItem from the binary search tree.
//Postcondition: If a node with the same info as deleteItem
// is found, it is deleted from the binary search tree.
//void inorderTraversal(const elemType &root);
void inorderTraversal(const elemType&);
private:
void deleteFromTree(binaryTreeNode<elemType>* &p);
//Function to delete the node to which p points is deleted
//from the binary search tree.
//Postcondition: The node to which p points is deleted from
// the binary search tree.
};

template<class elemType>
void bSearchTreeType<elemType>::inorderTraversal(const elemType&)
    { };

//destructor
//template <class elemType>
//binaryTreeType<elemType>::~binaryTreeType()
//{
//destroy(root);
//}

//overloading the assignment operator
template <class elemType>
const binaryTreeType<elemType>& binaryTreeType<elemType>::operator=
(const binaryTreeType<elemType>& otherTree)
{
if (this != &otherTree) //avoid self-copy
{
if (root != NULL) //if the binary tree is not empty,
//destroy the binary tree
destroy(root);
if (otherTree.root == NULL) //otherTree is empty
root = NULL;
else
copyTree(root, otherTree.root);
}//end else
return *this;
}
template <class elemType>
bool bSearchTreeType<elemType>::
search(const elemType& searchItem) const
{
binaryTreeNode<elemType> *current;
bool found = false;
if (this->root == NULL)
cerr << "Cannot search the empty tree." << endl;
else
{
current = this->root;
while (current != NULL && !found)
{
if (current->info == searchItem)
found = true;
else if (current->info > searchItem)
current = current->llink;
else
current = current->rlink;
}//end while
}//end else
return found;
}//end search
template <class elemType>
void bSearchTreeType<elemType>::insert(const elemType& insertItem)
{
binaryTreeNode<elemType> *current; //pointer to traverse the tree
binaryTreeNode<elemType> *trailCurrent; //pointer behind current
binaryTreeNode<elemType> *newNode; //pointer to create the node
newNode = new binaryTreeNode<elemType>;
assert(newNode != NULL);
newNode->info = insertItem;
newNode->llink = NULL;
newNode->rlink = NULL;
if (this->root == NULL)
this->root = newNode;
else
{
current = this->root;
while (current != NULL)
{
trailCurrent = current;
if (current->info == insertItem)
{
cerr << "The insert item is already in the list-";
cerr << "duplicates are not allowed."
<< insertItem << endl;
return;
}
else if (current->info > insertItem)
current = current->llink;
else
current = current->rlink;
}//end while
if (trailCurrent->info > insertItem)
trailCurrent->llink = newNode;
else
trailCurrent->rlink = newNode;
}
}//end insert
template <class elemType>
void bSearchTreeType<elemType>::deleteFromTree
(binaryTreeNode<elemType>* &p)
{
binaryTreeNode<elemType> *current;//pointer to traverse the tree
binaryTreeNode<elemType> *trailCurrent; //pointer behind current
binaryTreeNode<elemType> *temp; //pointer to delete the node
if (p == NULL)
cerr << "Error: The node to be deleted is NULL." << endl;
else if(p->llink == NULL && p->rlink == NULL)
{
temp = p;
p = NULL;
delete temp;
}
else if(p->llink == NULL)
{
temp = p;
p = temp->rlink;
delete temp;
}
else if(p->rlink == NULL)
{
temp = p;
p = temp->llink;
delete temp;
}
else
{
current = p->llink;
trailCurrent = NULL;
while (current->rlink != NULL)
{
trailCurrent = current;
current = current->rlink;
}//end while
p->info = current->info;
if (trailCurrent == NULL) //current did not move;
//current == p->llink; adjust p
p->llink = current->llink;
else
trailCurrent->rlink = current->llink;
delete current;
}//end else
}//end deleteFromTree
template <class elemType>
void bSearchTreeType<elemType>::deleteNode(const elemType& deleteItem)
{
binaryTreeNode<elemType> *current; //pointer to traverse the tree
binaryTreeNode<elemType> *trailCurrent; //pointer behind current
bool found = false;
if (this->root == NULL)
cout << "Cannot delete from the empty tree." << endl;
else
{
current = this->root;
trailCurrent = this->root;
while (current != NULL && !found)
{
if (current->info == deleteItem)
found = true;
else
{
trailCurrent = current;
if (current->info > deleteItem)
current = current->llink;
else
current = current->rlink;
}
}//end while
if (current == NULL)
cout << "The delete item is not in the tree." << endl;
else if (found)
{
if (current == this->root)
deleteFromTree(this->root);
else if (trailCurrent->info > deleteItem)
deleteFromTree(trailCurrent->llink);
else
deleteFromTree(trailCurrent->rlink);
}//end if
}
}//end deleteNode

//template <class elemType>
//void binaryTreeType<elemType>::inorderTraversal
//(void (*visit) (elemType& item))
//{
//inorder(root, *visit);
//}
//template <class elemType>
//void binaryTreeType<elemType>::inorder(binaryTreeNode<elemType>* p,
//void (*visit) (elemType& item))
//{
//if (p != NULL)
//{
//inorder(p->llink, *visit);
//(*visit)(p->info);
//inorder(p->rlink, *visit);
//}
//}

//template <class elemType>
//bSearchTree(nodeType *root) : root {}
dhayden (5795)
Line 464:
treeRoot.inorderTraversal(print);
inorderTraversal() expects its argument to be an int but you're passing the name of function print

Line 470: Same problem. You're passing update, which is a function, not an int.
Line 473. Same problem again.

Looking at the code, it appears that inorderTraversal should use this commented out signature:
1
2
3
 
//template <class elemType>
//void binaryTreeType<elemType>::inorderTraversal
//(void (*visit) (elemType& item))

In other words, you need to fix inorderTraversal, not the calls to it.
Bopaki (407)
Thank you dhayden. I have re-done the program from scratch and it ran fine!!!
Here is the output:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
C:\Dev-Cpp\Chapter11>binaryTreeType2
Line 10: Enter numbers ending with -999
45 67 32 1 56 98 54
23 45 -999
The insert item is already in the list-duplicates are not allowed.45

Line 17: Tree nodes in inorder: 1 23 32 45 54 56 67 98
Line 19: Tree Height: 4

Line 20: ******* Update Nodes *******
Line 22: Tree nodes in inorder after the update:
 2 46 64 90 108 112 134 196
Line 24: Tree Height: 4

C:\Dev-Cpp\Chapter11>
Bopaki (407)
I had a good day!!!
After a very frustrating yesterday
dhayden (5795)
The biggest mistake that beginners make is that when they hit a wall, they just keep hitting it for hours or days before asking for help. If you find yourself stuck for more than an hour, seek out help. The solution is probably something simple that you just aren't seeing.
Topic archived. No new replies allowed.