C++

Forum

 
find a key in binary search tree

LayMuon (41)
Hi, I wrote a small function which i think should find a specified key in the binary search tree (given by root h). However i get error: Unhandled exception at 0x012964BE in ConsoleApplication8.exe: 0xC0000005: Access violation reading location 0x0000002B.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
  node** findkey(node* h, int kkey){
	if (h == NULL){
		return NULL;
	}
	else{
		if (h->key == kkey){
			return &h;
		}
		else{
			
				findkey(h->pl, kkey);
			
				findkey(h->pr, kkey);
		}
	}
}
Last edited on
cire (8284)
Line 7 returns the address of a local variable which ceases existing when the function returns. Dereferencing that pointer results in undefined behavior. Why are you returning a pointer to a pointer to type node?
LayMuon (41)
I was trying to write a program that would generate a binary tree and then delete some nodes in. Generating part works fine, deleting didn't work yet.

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
 

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <cstdio>

using namespace std;

struct node{
	int key;
	node* pl;
	node* pr;
};

void insert(int key, node** pt);
void display(node* h, int count);
void tdelete(node* h, int kkey);
node** findkey(node* h, int kkey);
node** findmax(node* h);

int main()
{

	cout << "kuku" << endl;

	srand(time(NULL));
	
	node* h = NULL;
	node** k = &h;
	int t,g;

	for (int i = 0; i < 11; ++i){

		t = rand() % 50;
		insert(t, &h );
		
		if (i == 1){
			g = t;
		};
		
	};

	//cout << 5 << endl;

display(h, 5);

//cout << g << endl;

cout << g<<endl<<(*(findkey(h, g)))->key << endl;
//cout << findmax(h) << endl;


/*
cout << h;
cout << "\n\n\n\n";
//cout << (*k)->key << endl << h->key;
cout << g << endl<<endl;

tdelete(h, g);
cout << h;
display(h, 5);

*/


}

void insert(int kkey, node** pt){

	if (*pt == NULL){

		node* n = new node;
		n->pl = NULL;
		n->pr = NULL;
		n->key = kkey;
		*pt = n;
		
	}
	else{
		if (kkey < (*pt)->key){
			insert(kkey,& (*pt)->pl);
		}

		else{
			if (kkey>(*pt)->key){
				insert(kkey,& (*pt)->pr);
			}


		}
		

	}

}


void display(node* h, int count){
	

	if (h != NULL){
		
		display(h->pr, count+10);
		
		printf("%*d\n", count, h->key);
		
		display(h->pl, count+10);
		
		}

}


void tdelete(node* h, int kkey){

	node* f = (findkey(h, kkey));

	if ((f)->pr == NULL && (f)->pl == NULL){

		delete (f);
		f = NULL;
	}
	else{
		if ((f)->pl == NULL){

			node* k = (*f)->pr;
			delete (*f);
			*f = k;

		}
		else{
			node** t = findmax((*f)->pl);
			(*f)->key = (*t)->key;
			delete *t;
			*t = NULL;

		}
	}
}



node** findkey(node* h, int kkey){
	if (h == NULL){
		return NULL;
	}
	else{
		if (h->key == kkey){
			return &h;
		}
		else{
			if (h->pl != NULL)
				findkey(h->pl, kkey);
			if (h->pr != NULL)
				findkey(h->pr, kkey);
		}
	}
}

node** findmax(node* h){
	if (h == NULL)
		return NULL;
	if (h->pr == NULL){

		return &h;
	}
	else
	{
		findmax(h->pr);
	}
}
LayMuon (41)
But why is it local? Doesn't the function propagate through the tree?
closed account (j3Rz8vqX)
But why is it local?
Pointers are pass by value, by default.
Pass it by reference to get the actual address of the variable.

Example:
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
 
#include <iostream>
using namespace std;
int** fun(int *&t)
{
    return &t;//returning correct address (referenced)
}
int** bad(int *t)
{
    return &t;//Bad, address of local variable returned!
}
int main()
{
    int i=2, *j=&i, *k=&i;
    cout<<"Observe the addresses!\n";

    cout<<"\nPrinting with bad function: \n";
    cout<<bad(j)<<'\n';
    cout<<bad(k)<<'\n';

    cout<<"\nPrinting with fun function: \n";
    cout<<fun(j)<<'\n';
    cout<<fun(k)<<'\n';

    cout<<"\nPress <enter> to exit: ";
    cin.get();
    return 0;
}
 
Observe the addresses!

Printing with bad function:
0x28fea0
0x28fea0

Printing with fun function:
0x28fef8
0x28fef4

Press <enter> to exit:

Notice how the bad function returns faulty addresses; local addresses. Pass by reference is probably what you'd want; do this if you are planning to make changes to the variable or if its real address is necessary.
LayMuon (41)
I removed the reference, but now instead of finding the key, it finds the maximum in the tree:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 

node* findkey(node* h, int kkey){
	if (h == NULL){
		return NULL;
	}
	else{
		if (h->key == kkey){
			return h; 
			
		}
		else{
			if (h->pl != NULL){
				findkey(h->pl, kkey);
			};
			if (h->pr != NULL)
				findkey(h->pr, kkey);
		};
	};
}


then i print out findkey(h, g)->key.
Last edited on
cire (8284)
If we reach line 12 in your function, will any value be returned?
Topic archived. No new replies allowed.