-
Notifications
You must be signed in to change notification settings - Fork 0
/
BinarySearchTree.c
154 lines (136 loc) · 3.83 KB
/
BinarySearchTree.c
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
/*Exp 7 : Write a C Program to implement a binary search tree(BST) that support dynamic node insertion and traversal in
IN-ORDER , PRE-ORDER and POSTORDER to efficiently organize and manage data*/
#include <stdio.h>
#include <stdlib.h>
// Definition of the Node structure
struct Node {
int data;
struct Node* left;
struct Node* right;
};
// Function to create a new node with given data
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// Function to insert a node in the BST
struct Node* insert(struct Node* root, int data) {
// If the tree is empty, create a new node and return it
if (root == NULL) {
return createNode(data);
}
// Otherwise, recur down the tree
if (data < root->data) {
root->left = insert(root->left, data); // Insert in left subtree
} else {
root->right = insert(root->right, data); // Insert in right subtree
}
// Return the (unchanged) node pointer
return root;
}
// Function for in-order traversal of the BST
void inorder(struct Node* root) {
if (root != NULL) {
inorder(root->left); // Visit left subtree
printf("%d ", root->data); // Print node data
inorder(root->right); // Visit right subtree
}
}
// Function for pre-order traversal of the BST
void preorder(struct Node* root) {
if (root != NULL) {
printf("%d ", root->data); // Print node data
preorder(root->left); // Visit left subtree
preorder(root->right); // Visit right subtree
}
}
// Function for post-order traversal of the BST
void postorder(struct Node* root) {
if (root != NULL) {
postorder(root->left); // Visit left subtree
postorder(root->right); // Visit right subtree
printf("%d ", root->data); // Print node data
}
}
// Main function
int main() {
struct Node* root = NULL;
int choice, data;
// Display menu options and handle user input
do {
printf("\nMenu:\n");
printf("1. Insert Node\n");
printf("2. In-order Traversal\n");
printf("3. Pre-order Traversal\n");
printf("4. Post-order Traversal\n");
printf("5. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
switch (choice) {
case 1:
printf("Enter data to insert: ");
scanf("%d", &data);
root = insert(root, data);
break;
case 2:
printf("In-order Traversal: ");
inorder(root);
printf("\n");
break;
case 3:
printf("Pre-order Traversal: ");
preorder(root);
printf("\n");
break;
case 4:
printf("Post-order Traversal: ");
postorder(root);
printf("\n");
break;
case 5:
printf("Exiting...\n");
break;
default:
printf("Invalid choice. Please try again.\n");
}
} while (choice != 5);
return 0; // Return success
}
//SAMPLE OUTPUT
/*
Menu:
1. Insert Node
2. In-order Traversal
3. Pre-order Traversal
4. Post-order Traversal
5. Exit
Enter your choice: 1
Enter data to insert: 50
Menu:
1. Insert Node
2. In-order Traversal
3. Pre-order Traversal
4. Post-order Traversal
5. Exit
Enter your choice: 1
Enter data to insert: 30
Menu:
1. Insert Node
2. In-order Traversal
3. Pre-order Traversal
4. Post-order Traversal
5. Exit
Enter your choice: 2
In-order Traversal: 30 50
Menu:
1. Insert Node
2. In-order Traversal
3. Pre-order Traversal
4. Post-order Traversal
5. Exit
Enter your choice: 5
Exiting...
*/