binary_search_tree.c

trees Implementation

101 lines
2038 bytes
C
1// Binary Search Tree (BST)
2#include <stdio.h>
3#include <stdlib.h>
4
5struct Node {
6    int data;
7    struct Node* left;
8    struct Node* right;
9};
10
11struct Node* createNode(int data) {
12    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
13    newNode->data = data;
14    newNode->left = NULL;
15    newNode->right = NULL;
16    return newNode;
17}
18
19struct Node* insert(struct Node* root, int data) {
20    if (root == NULL) {
21        return createNode(data);
22    }
23    
24    if (data < root->data) {
25        root->left = insert(root->left, data);
26    } else if (data > root->data) {
27        root->right = insert(root->right, data);
28    }
29    
30    return root;
31}
32
33struct Node* search(struct Node* root, int key) {
34    if (root == NULL || root->data == key) {
35        return root;
36    }
37    
38    if (key < root->data) {
39        return search(root->left, key);
40    }
41    
42    return search(root->right, key);
43}
44
45void inorder(struct Node* root) {
46    if (root != NULL) {
47        inorder(root->left);
48        printf("%d ", root->data);
49        inorder(root->right);
50    }
51}
52
53void preorder(struct Node* root) {
54    if (root != NULL) {
55        printf("%d ", root->data);
56        preorder(root->left);
57        preorder(root->right);
58    }
59}
60
61void postorder(struct Node* root) {
62    if (root != NULL) {
63        postorder(root->left);
64        postorder(root->right);
65        printf("%d ", root->data);
66    }
67}
68
69int main() {
70    struct Node* root = NULL;
71    
72    root = insert(root, 50);
73    insert(root, 30);
74    insert(root, 20);
75    insert(root, 40);
76    insert(root, 70);
77    insert(root, 60);
78    insert(root, 80);
79    
80    printf("Inorder traversal: ");
81    inorder(root);
82    printf("\n");
83    
84    printf("Preorder traversal: ");
85    preorder(root);
86    printf("\n");
87    
88    printf("Postorder traversal: ");
89    postorder(root);
90    printf("\n");
91    
92    struct Node* found = search(root, 40);
93    if (found != NULL) {
94        printf("Found: %d\n", found->data);
95    } else {
96        printf("Not found\n");
97    }
98    
99    return 0;
100}
101