C++

Forum

 
BST Search Function Issue

ammar629 (30)
Hi Guys,
So I've been working on my semester project for data structures and I came across a problem here...
I insert data into the bst but it doesn't show proper output
I made a preorder traversal TEST function to check for the data but nothing shows except one piece of information

I don't know what im doing wrong here
Can someone guide me?

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
 
  //SM Class Function
void SearchEmployee() {
		//First Retrieve Data From File Then Insert One By One into BST and then Perform Search Operation
		ifstream input;
		string Names, Genders, Positions, Date_Of_Births, Contact_Nos,EmployeeIDs;
		int convert_To_int;
		int ID;
		//input.open("Employees.txt",ios::app);
		//while (!input.eof()) {
		//	getline(input, Names, ',');
		//	getline(input, Genders, ',');
		//	getline(input, Positions, ',');
		//	getline(input, Date_Of_Births, ',');
		//	getline(input, Contact_Nos, ',');
		//	getline(input, EmployeeIDs, '\n');
		//	convert_To_int = atoi(EmployeeIDs.c_str());
		//	//OK Till This point
		//	if (Root = NULL) {
		//		Root = Obj->Insert(Names, Genders, Positions, Date_Of_Births, Contact_Nos, convert_To_int,Root);
		//	}
		//	           Obj->Insert(Names, Genders, Positions, Date_Of_Births, Contact_Nos, convert_To_int, Root);
		//}
		
		// Works Too
		Root = Obj->Insert("XYZ", "M", "awf", "124", "15",15, Root);
		//Again Problem       
		Obj->Insert("XXZ", "M", "awf", "12412", "16", 14, Root);
		
		
		
		//Test Function (OK)
		Obj->PreOrder(Root);
		//Obj->Search(Root, 15);
		input.close();
	}

private:
	//Login Info
	string username, password;
	//Employee Variables
	string Name, Gender, Position, Date_Of_Birth, Contact_No;
	int EmployeeID;
	BST *Obj;



BST* Insert(string Names, string Genders, string Positions, string Date_Of_Births, string Contact_Nos,int EmployeeIDs,BST *root) {
		if (root == NULL) {
			root = new BST();
			root->Contact_No = Contact_Nos;
			root->Date_Of_Birth = Date_Of_Births;
			root->EmployeeID = EmployeeIDs;
			root->Gender = Genders;
			root->Name = Names;
			root->Position = Positions;
			root->Left = root->Right = NULL;
			return root;
		}

		if (EmployeeID < root->EmployeeID) {
			root->Left = Insert(Name, Gender, Position, Date_Of_Birth, Contact_No, EmployeeID, root->Left);
		}
		if (EmployeeID > root->EmployeeID) {
			root->Right = Insert(Name, Gender, Position, Date_Of_Birth, Contact_No, EmployeeID, root->Right);
		}
		return root;
	}

	BST* Search(BST *Root, int EmployeeIDs) {
		if (Root == NULL) {
			cout << "No Data Exists!" << endl;
			return NULL;
		}
		if (Root->EmployeeID == EmployeeIDs) {
			cout << "Employee Name:" << Root->Name << endl;
		}
		if (Root->EmployeeID < EmployeeIDs) {
			Root->Left = Search(Root->Left, EmployeeIDs);
		}
		if (Root->EmployeeID > EmployeeIDs) {
			Root->Right = Search(Root->Right, EmployeeIDs);
		}
		return Root;
	}
salem c (3700)
TBH, your root should be hidden inside your BST, so you don't have to keep passing and returning it.

That is, you do things like
1
2
 
myBst.insert("XYZ", "M", "awf", "124", "15",15);
myBst.search(12);


But if you're going to be passing root around, then you need to be consistent.
1
2
3
 
BST Root = NULL;
Root = Root->Insert("XYZ", "M", "awf", "124", "15",15, Root);
Root = Root->Insert("XXZ", "M", "awf", "12412", "16", 14, Root);



> BST *Obj;
What's the relationship between Obj and root?

ammar629 (30)
Root is a global variable
and BST is the Binary Search Tree ADT Implementation

The relation between Obj and root as you asked is..

Obj is an object of BST Class and *root is the root node that points at the start of the BST

I just can't figure out why my output isnt correct


and In case you're wondering here's my entire code
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
222
223
224
225
226
227
228
229
230
231
232
 
#include <iostream>
#include <string>
#include <fstream>
#include <cstdlib>
using namespace std;

//Ammar
void Welcome_Menu() {
	system("CLS");
	cout << "Welcome To Sales Management Program!\n------------------------------------\n";
	cout << "[1]Employee Info\n[2]Product Info\n[3]Sales Info\n[4]Order Info\n";
}
//Ammar
class BST {
public:
	BST() {

	}
	~BST() {
    
	}

	BST* Insert(string Names, string Genders, string Positions, string Date_Of_Births, string Contact_Nos,int EmployeeIDs,BST *root) {
		if (root == NULL) {
			root = new BST();
			root->Contact_No = Contact_Nos;
			root->Date_Of_Birth = Date_Of_Births;
			root->EmployeeID = EmployeeIDs;
			root->Gender = Genders;
			root->Name = Names;
			root->Position = Positions;
			root->Left = root->Right = NULL;
			return root;
		}

		if (EmployeeID < root->EmployeeID) {
			root->Left = Insert(Name, Gender, Position, Date_Of_Birth, Contact_No, EmployeeID, root->Left);
		}
		if (EmployeeID > root->EmployeeID) {
			root->Right = Insert(Name, Gender, Position, Date_Of_Birth, Contact_No, EmployeeID, root->Right);
		}
		return root;
	}

	BST* Search(BST *Root, int EmployeeIDs) {
		if (Root == NULL) {
			cout << "No Data Exists!" << endl;
			return NULL;
		}
		if (Root->EmployeeID == EmployeeIDs) {
			cout << "Employee Name:" << Root->Name << endl;
		}
		if (Root->EmployeeID < EmployeeIDs) {
			Root->Left = Search(Root->Left, EmployeeIDs);
		}
		if (Root->EmployeeID > EmployeeIDs) {
			Root->Right = Search(Root->Right, EmployeeIDs);
		}
		return Root;
	}
	//Test
	void PreOrder(BST* Root) {
		if (Root == NULL) {
			return;
		}
		cout << "Data:" << Root->Name << endl;
		PreOrder(Root->Left);
		PreOrder(Root->Right);
	}

private:
	string Name, Gender, Position, Date_Of_Birth, Contact_No;
	int EmployeeID;
	BST *Left, *Right;
};

//Ammar
class SM {
public:
	/*
	Constructor and Destructor
	*/
	SM() {
		Name = Gender = Position = Date_Of_Birth = Contact_No = username = password = "NULL";
	    EmployeeID = 0;
		Obj = new BST();
		Root = NULL;
	}

	~SM(){

	}
	//Login Function
	bool Login_Func() {
		cout << "Welcome, Please Enter your Username And Password To Continue!\n-------------------------------------------------------------\n[LOGIN]\n";
		cout << "Enter Username:";
		cin >> username;
		cout << "Enter Password:";
		cin >> password;
		if (username == "Ammar" && password == "123456") {
			system("CLS");
			cout << "Login Succsesful!" << endl;
			return true;
		}
		else {
			cout << "Username or Password is incorrect" << endl;
			return false;
		}
	}
	///////////////////////////Employee Functions///////////////////////////

	void EmployeeInfoMenu() {
		system("PAUSE");
		cout << endl;
		system("CLS");
		cout << "Employee Info Main Menu\n--------------------------------------\n[1]Add Employee\n[2]Search Employee\n[3]Display All Employees\n[4]Delete Employee\n[5]Return To Main Menu\n";
	}
	void EmployeeMenu() {
		int choice;
        EmployeeInfoMenu();
	
		do {
			
			EmployeeInfoMenu();
			cout << "Enter Choice:";
			cin >> choice;
			switch (choice) {
			case 1: AddEmployee();
				break;
			case 2: SearchEmployee();
				break;

			case 5: cout << "Exit!" << endl;
				Welcome_Menu();
				break;
			default: cout << "Error!" << endl;
				break;
			}
		} while (choice != 5);
	}
	//Add Employee
	void AddEmployee() {
		ofstream myfile;
		myfile.open("Employees.txt",ios::app |ios::ate);
		cout << "Enter Name:";
		cin >> Name;
		cout << "Enter Gender(M/F):";
		cin >> Gender;
		cout << "Enter Position:";
		cin >> Position;
		cout << "Enter Date Of Birth(DD/MM/YY):";
		cin >> Date_Of_Birth;
		cout << "Enter Contact No:";
		cin >> Contact_No;
		cout << "Enter Employee ID:";
		cin >> EmployeeID;
		myfile << Name << "," << Gender << "," << Position << "," << Date_Of_Birth << "," << Contact_No << "," << EmployeeID << endl;
		myfile.close();
		cout << "Employee Added To Database" << endl; //Ok
	}

	//Search Employee (BST)
	void SearchEmployee() {
		//First Retrieve Data From File Then Insert One By One into BST and then Perform Search Operation
		ifstream input;
		string Names, Genders, Positions, Date_Of_Births, Contact_Nos,EmployeeIDs;
		int convert_To_int;
		int ID;
		input.open("Employees.txt",ios::app);
		while (!input.eof()) {
			getline(input, Names, ',');
			getline(input, Genders, ',');
			getline(input, Positions, ',');
			getline(input, Date_Of_Births, ',');
			getline(input, Contact_Nos, ',');
			getline(input, EmployeeIDs, '\n');
			convert_To_int = atoi(EmployeeIDs.c_str());
			//OK Till This point
			if (Root = NULL) {
				Root = Obj->Insert(Names, Genders, Positions, Date_Of_Births, Contact_Nos, convert_To_int,Root);
			}
			           Obj->Insert(Names, Genders, Positions, Date_Of_Births, Contact_Nos, convert_To_int, Root);
		}
		
		//// Works Too
		Root = Obj->Insert("XYZ", "M", "awf", "124", "15",15, Root);
		////Again Problem       
		Obj->Insert("XXZ", "M", "awf", "12412", "16", 14, Root);
		
		
		
		//Test Function (OK)
		Obj->PreOrder(Root);
		//Obj->Search(Root, 15);
		input.close();
	}

private:
	//Login Info
	string username, password;
	//Employee Variables
	string Name, Gender, Position, Date_Of_Birth, Contact_No;
	int EmployeeID;
	BST *Obj;
	BST *Root;

};

int main() {
	SM *Obj;
	int choice;
	Obj = new SM();
	if (Obj->Login_Func()) {
		Welcome_Menu();
		do {
			cout << "Enter Choice:";
			cin >> choice;
			switch (choice) {
			case 1: Obj->EmployeeMenu();
				break;
			case 5: cout << "Exit" << endl;
				break;
			default: cout << "Error!" << endl;
				break;
			}
		} while(choice != 5);
	}


	system("PAUSE");
	return 0;
}



Maybe this might explain what I'm trying to achieve here
salem c (3700)
Well if (Root = NULL) on line 179 isn't what you want.

And SM only needs one BST, not two.
dhayden (5798)
I think you're getting tripped up by the difference between a tree, which you can perform operations on, and a node within the tree, which has left and right pointers. This is probably why you have both an Obj that you use to call Insert, etc., and a root that points to the root of the tree. You probably found that you can't call root->Insert() when root is NULL.

One way to resolve this is to make the BST methods static. Then you call Insert with
root = BST::Insert(name, gender, position, dob, contactNo, employeeID, root);

Lines 36 & 39: EmployeeID should be EmployeeIDs. You want to compare against the parameter passed in. Lines 37 & 40 should pass Names, Genders, etc. into Insert.

Lines 53 & 56: You have the sense of the comparison wrong. You want to go down the left tree if EmployeeIDs is less than Root->EmployeeID

Lines 54 & 57: why are you changing Root->Left and Root->Right? You want to do something else with the return value from the recursive calls.

Line 169: Remove , ios::app

Lines 210 and 212: Why are you allocating Obj on the heap? Why not simply SM Obj; and then Obj.Login_Func() and Obj.EmployeeMenu() at lines 213 and 219



Topic archived. No new replies allowed.