Help with Binary Search Tree

newberrydc (4)
I am having a couple of problems implementing a Remove() function into my Binary Search Tree.

My tree.cpp file is:

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
 
#include <iostream>
#include "tree.h"

using namespace std;

Tree::Tree(int val) {
    data = val;
    left = right = NULL;
}

Tree::~Tree() {
    if(left != NULL) {
        delete left;
    }
    if(right != NULL) {
        delete right;
    }
}

void Tree::insert(int val) {
    if(val <= data) {
        if(left != NULL) {
            left->insert(val);
        }
        else {
            left = new Tree(val);
        }
    }
    else {
        if(right != NULL) {
            right->insert(val);
        }
        else {
            right = new Tree(val);
        }
    }
}

void Tree::print() {
    if(left != NULL) {
        left->print();
    }
    cout << data << " ";
    if(right != NULL) {
        right->print();
    }
}

bool Tree::search(int val)
{

     if(left==NULL || right==NULL)
		   return false;
	 else if(val<data)
	 {
	    data=left->data;
	    search(data);
	 }
	 else if(val>data)
	 {
	     data=right->data;
	     search(data);
	 }
	else
	   return true;
}
int Tree::count(int val)
{

     if(left==NULL && right==NULL)
	 return 0;
	 if(val<data)
	 {
     	data=left->data;
	    return count(data);
	 }
	 else if(val>data)
	 {
	     data=right->data;
	     return count(data);
	 }
	else if(val==data)
	   return 1+count(left->data)+count(right->data);


}
void Tree::remove(int val)
{
if(left==NULL && right==NULL)
	 cout << "Value not found" << endl << endl;
else
{
    if(val==data)
	{
   remove(data);
	}
    else if(val <= data)
	{
        if(left != NULL)
		{
            left->remove(val);
        }
        else
		{
            //left = remove(val);
        }
    }
    else if(val>data)
	{
        if(right != NULL)
		{
            right->remove(val);
        }
        else
		{
           // right = remove(val);
        }
    }
}
}


My tree.h is:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
#ifndef TREE_H_INCLUDED
#define TREE_H_INCLUDED

class Tree {
    public:
        Tree(int val);
        ~Tree();

        void insert(int val);
        bool search(int val);
        int count(int val);
		void remove(int val);
        void print();

    private:
        int data;
        Tree *left;
        Tree *right;
};


#endif // TREE_H_INCLUDED


My main.cpp is:

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
 
#include <iostream>
#include <String>
#include "Tree.h"

using namespace std;

#define NUM 9

int main()
{
    int num[NUM] = {4, 2, 7, 3, 6, 8, 0, 112, 9};
	int n1,n2,n3;
	bool tag = false;
    Tree *t = new Tree(5);
    for(int i = 0; i < NUM; i++) {
        t->insert(num[i]);
    }
    t->print();
    cout << endl << endl;

	cout<<"Enter the element to search :";
	cin>>n1;
	tag=t->search(n1);
     if(tag)
		 cout<<"Found" << endl << endl;
	 else
		 cout<<"not found" << endl;
	cout<<"Enter the element to remove : ";
	cin>>n2;
	t->remove(n2);
	t->print();
	cout << endl << endl;
     cout<<"Enter the number to find its occurances : ";
	 cin>>n3;
	 int occur=t->count(n3);
	 cout<<"Number of Occurances is :"<<occur;
    delete t;
    return 0;
}


I have two problems...first, the remove function isn't working properly and when I try to print() the tree after removing an element, I get a "Process returned -1073741819" message. I realize I have portions of the remove function commented out but it won't compile because remove(val) is not a pointer.

Also, my search function is always returning true...telling me that the element, regardless of what I enter, is found.

Any help?
LB (13399)
In your search function, what if the element is at the beginning or end? In both cases it returns false. And of course it always returns true, you're asking it to search for the element in the left/right of itself, and calling the function of itself ratehr than the left/right. It should search for the given val parameter and call the search function of the left or right.
Last edited on
newberrydc (4)
No, I'm not trying to achieve something different. We were supplied the class itself and just have to implement the remove() function. I also implemented a search function, for my own experience, but am having problems getting the remove() to work properly.
Topic archived. No new replies allowed.