Binary Search Tree

cbrew (7)
I am making a binary search tree to print the elements of a tree. everything seems to be fine except when i run the program with inorder i get "7, -1, " with an input of
38
57
93
23
11
18
50
30
25
53
71
80
52
35
20
7
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
 
#include <iostream>
#include <fstream>
#include <iomanip>
#include <string>

using namespace std;

struct treetype
{
	int id;
	treetype *left, *right;
};
void createtree(treetype *&root)
{
	root = new treetype;
	root->id = -1;
	root->left = NULL;
	root->right = NULL;
}
bool emptytree(treetype *root)
{
	return root->id == 0;
}
void inorder(treetype *c)
{
	if(c != NULL)
	{
			inorder(c->left);
			cout << c->id << ", ";
			inorder(c->right);
	}
	else return;
}
void preorder(treetype *c)
{
	if(c != NULL)
	{
		cout << c->id << ", ";
		inorder(c->left);
		inorder(c->right);
	}
	else return;
}
void postorder(treetype *c)
{
	if(c != NULL)
	{
		inorder(c->left);
		inorder(c->right);
		cout << c->id;
	}
	else return;
}
void ipreorder(treetype *c)
{
}
void inserttree(treetype *root, int id)
{
	treetype *Knew, *parent, *c;
	if(!emptytree(root))
	{
		Knew = new treetype;
		Knew->id = id;
		Knew->left = NULL;
		Knew->right = NULL;
		c = root;
		parent = NULL;
		while(c != NULL)
		{
			parent = c;
			if(id < c->id)
			{
				c = c->left;
			}
			else
			{
				c = c->right;
			}
		}
		if(id > parent->id)
		{
			parent->left = Knew;
		}
		else
		{
			parent->right = Knew;
		}
	}
	else
	{
		root->id = id;
	}
}
void readem(treetype *root)
{
	int id;
	ifstream inf;
	inf.open("data.dat");
	while(!inf.eof())
	{
		inf >> id;
		inserttree(root, id);
	}
	inf.close();
}
void deletetree()
{
}
int main()
{
	treetype *root;
	int xyz;
	createtree(root);
	readem(root);
	inorder(root);
	/*cout << endl;
	deletetree();
	postorder(root);
	cout << endl;
	deletetree();
	preorder(root);
	cout << endl;
	ipreorder(root);*/
	cin >> xyz;
}
ne555 (10692)
1
2
3
4
5
6
7
8
9
10
 
//insert
			if(id < c->id)
				c = c->left;
			else
				c = c->right;
//...
		if(id > parent->id)
			parent->left = Knew;
		else
			parent->right = Knew;

Also createtree() and emptytree() make no sense.

You ought to encapsulate the behaviour in a tree class.
cbrew (7)
i finished up the program and also changed some things. but the program seems to only read one section of the tree by outputting "52 7 38" for the inorder. Im not sure what is wrong..
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
 
#include <iostream>
#include <fstream>
#include <iomanip>
#include <string>

using namespace std;

struct treetype
{
	int id;
	treetype *left, *right;
};

const int initvalue = -1;

void createtree(treetype *&root)
{
	root = new treetype;
	root->id = initvalue;
	root->left = NULL;
	root->right = NULL;
}
bool emptytree(treetype *root)
{
	return root->id == initvalue;
}
void inorder(treetype *c)
{
	if(c != NULL)
	{
			inorder(c->left);
			cout << setw(4) << c->id;
			inorder(c->right);
	}
}
void preorder(treetype *c)
{
	if(c != NULL)
	{
		cout << setw(4) << c->id;
		inorder(c->left);
		inorder(c->right);
	}
}
void postorder(treetype *c)
{
	if(c != NULL)
	{
		inorder(c->left);
		inorder(c->right);
		cout << setw(4) << c->id;
	}
}
void ipreorder(treetype *c)
{
}
void inserttree(treetype *root, int id)
{
	treetype *Knew, *parent, *c;
	if(!emptytree(root))
	{
		Knew = new treetype;
		Knew->id = id;
		Knew->left = NULL;
		Knew->right = NULL;
		c = root;
		parent = NULL;
		while(c != NULL)
		{
			parent = c;
			if(id < c->id)
				c = c->left;
			else
				c = c->right;
		}
		if(id > parent->id)
			parent->left = Knew;
		else
			parent->right = Knew;
	}
	else
		root->id = id;
}
void readem(treetype *root)
{
	int id;
	ifstream inf;
	inf.open("data.dat");
	while(!inf.eof())
	{
		inf >> id;
		inserttree(root, id);
	}
	inf.close();
}
void deleteleaf(treetype *c, treetype *parent, treetype *root)
{
	if(c == root)
		root->id = initvalue;
	else
	{
		if(c->id < parent->id)
			parent->left = NULL;
		else
			parent->right = NULL;
	}
	delete c;
}
void deleteone(treetype *c, treetype *parent, treetype *root)
{
	treetype *child;
	if(c->left != NULL)
		child = c->left;
	else 
		child = c->right;
	if(c->id < parent->id)
		parent->left = child;
	else
		parent->right = child;
	delete c;
}
void deletetwo(treetype *c, treetype *root)
{
	treetype *replace, *por;
	por = c;
	replace = c->right;
	while(replace->left != NULL)
	{
		por = replace;
		replace = replace->left;
	}
	c->id = replace->id;
	if(replace->right == NULL)
		deleteleaf(replace, por, root);
	else
		deleteone(replace, por, root);
}
void deletetree(treetype *root, int id)
{
	treetype *c, *parent;
	c=root;
	parent = NULL;
	while(c != NULL && c->id != id)
	{
		parent = c;
		if(id > c->id)
			c = c->left;
		else
			c = c->right;
	}
	if(c->id == id)
	{
		if(c->left == NULL && c->right == NULL)
			deleteleaf(c, parent, root);
		else if(c->left != NULL && c->right != NULL)
			deletetwo(c, root);
		else
			deleteone(c, parent, root);
	}
	else
		cout << "Not Found" << endl;
}
int main()
{
	treetype *root;
	int xyz;
	createtree(root);
	readem(root);
	inorder(root);
	cout << endl;
	//deletetree(root, 71);
	postorder(root);
	cout << endl;
	//deletetree(root, 38);
	preorder(root);
	cout << endl;
	ipreorder(root);
	cin >> xyz;
}
ne555 (10692)
I wasn't clear the first time.
1
2
3
4
5
 
//insert
		if(id > parent->id)
			parent->left = Knew;
		else
			parent->right = Knew;
That's backwards. If you are greater, you should go to the right child
cbrew (7)
Thanks, that just fixed everything
Topic archived. No new replies allowed.