C++

Forum

 
binary search tree

Pages: 12
LayMuon (41)
I am trying to create a binary search tree and then print it out. But it doesn't seem to work, can't find the problem. 

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
 
#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);

int main()
{
	srand(time(NULL));
	node* h = NULL;
	node* root = h;
	for (int i = 0; i < 20; ++i){

		insert(rand() % 50, h);
		
	};


	display(root, 5);


}

void insert(int key, node* pt){

	if (pt = NULL){


		node* n = new node;
		n->pl = NULL;
		n->pr = NULL;
		pt = n;

	}
	else{
		if (key < pt->key){
			insert(key, pt->pl);
		}

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


		}


	}

}


void display(node* h, int count){
	

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

		display(h->pl, count);
		



	}

}
keskiverto (10365)
Line 21: root has value NULL. root does not change when h changes.

Line 42: pt now points to a node. 'h' in main does not. Same repeats on every call. You do need a reference to a pointer.

You never set any keys.
LayMuon (41)
how about now?

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
 

#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);

int main()
{
	srand(time(NULL));
	
	node* n = new node;
	n->pl = NULL;
	n->pr = NULL;
	n->key = rand()%50;

	node* root = n;
	node* h = root;
	for (int i = 0; i < 20; ++i){

		insert(rand() % 50, h );
		
	};


	display(root, 5);


}

void insert(int key, node* pt){

	if (pt = NULL){


		node* n = new node;
		n->pl = NULL;
		n->pr = NULL;
		n->key = key;
		pt = n;

	}
	else{
		if (key < pt->key){
			insert(key, pt->pl);
		}

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


		}


	}

}


void display(node* h, int count){
	

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

		display(h->pl, count);
		



	}

}
LayMuon (41)
Guys, any ideas? i probably did a trivial mistake. 

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
 

#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);

int main()
{
	srand(time(NULL));
	
	node* n = new node;
	n->pl = NULL;
	n->pr = NULL;
	n->key = rand()%50;

	node* root = n;
	node* h = root;
	for (int i = 0; i < 20; ++i){

		insert(rand() % 50, h );
		
	};


	display(root, 5);


}

void insert(int key, node* pt){

	if (pt = NULL){


		node* n = new node;
		n->pl = NULL;
		n->pr = NULL;
		n->key = key;
		pt = n;

	}
	else{
		if (key < pt->key){
			insert(key, pt->pl);
		}

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


		}


	}

}


void display(node* h, int count){
	

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



	}

}
Last edited on
keskiverto (10365)
void insert(int key, node* pt)
Like I said earlier, the 'pt' is a by value parameter. You can change it to point to the moon, but that will not change the caller's pointer at all.

Try
void insert(int key, node* & pt)
LayMuon (41)
what does "by value parameter" mean?
keskiverto (10365)
LayMuon (41)
i put the ampersand before the pt, it still doesn't work.
keskiverto (10365)
Add debugging print commands on points of interest. You want to see what happens instead of "not seem to work".
LayMuon (41)
Guys, can you have a look at this version and tell me what's wrong? Thanks.

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
 

#include <iostream>


using namespace std;

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

void insert(int key, node** pt);


int main()
{
	
	
	node* h = NULL;

	insert(5, &h);

	cout << h->key;

	


}

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);
			}


		}
		

	}

}
Ganado (6784)
None of you have noticed Line 33 ;p
if (*pt = NULL){
= should be ==
(That might not be the only mistake, I didn't thoroughly check it)

Edit: Also be sure to clear up the 'memory leaks' made with the new operator.
Last edited on
LayMuon (41)
But isn't pt a double pointer? so *pt is just a pointer , pointing to NULL?
AbstractionAnon (6954)
That's not the problem. Line 33 is using the asignment operator (=), not the equality operator (==).
LayMuon (41)
Right, i corrected, but it still doesn't work.
cire (8284)
33
34
35
36
37
38
39
40
41
42
 
	if (*pt == NULL){


		node* n = new node;
		n->pl = NULL;
		n->pr = NULL;
		n->key = kkey;
		*pt = &n;
		
	}


This should not even compile. Line 40 should be *pt = n;

If "it still doesn't work" means "I can't even get this code to compile," then say that and supply the error messages you get. If it doesn't, describe what you expect to happen and how what actually happens differs from your expectation. "It doesn't work" is about helpful as someone telling you "Yes, I could make it work."

You're making it hard for people to help you. Don't do that unless you don't like being helped.
LayMuon (41)
It compiles, but the console crushes. pt is double pointer, so *pt = &n i suppose means that the pointer in the middle (pointer -> pointer->node) points to the node. Am I wrong?
LayMuon (41)
Unhandled exception at 0x00035832 in ConsoleApplication8.exe: 0xC0000005: Access violation reading location 0x00000000.
LayMuon (41)
thanks guys, it all works now. 

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
 

#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);

int main()
{
	srand(time(NULL));
	
	node* h = NULL;

	

	for (int i = 0; i < 20; ++i){
	
		insert(rand() % 50, &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);
	
	}

}
BobTheZealotIsEpic (32)
Please cut down on your useless rows:
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
 
#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);
int main()
{
	srand(time(NULL));
	node* h = NULL;
	for (int i = 0; i < 20; ++i){
		insert(rand() % 50, &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);
	}
}

You said the topic is solved. Click the green check that says topic solved at the top of the page.
cire (8284)
BobTheZealotIsEpic wrote:
Please cut down on your useless rows:

Please cut down on your no-content posts.
Pages: 12