# BST

Jun 1st, 2023 (edited)
1,421
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. //Implemented by: Tariq Zaghal
2. #include <stdlib.h>
3. #include <stdio.h>
4. #include <math.h>
5.
6.
7. typedef struct BstNode* TNode;
8.
9. struct BstNode{
10.     int data;
11.     TNode left;
12.     TNode right;
13.     int count;
14. };
15.
16.
17. TNode makeEmpty(TNode root);
18. TNode find(int x, TNode root);
19. TNode findMin(TNode root);
20. TNode findMax(TNode root);
21. TNode insert(int data, TNode root);
22. TNode delete(int x, TNode T);
23. int findHeight(TNode root);
24. int max(int x, int y);
25. void trace(TNode T);
26. struct BstNode* getNewNode(int data);
27.
28. int main(){
29.     TNode root = NULL;
30.
31.     root = insert(13,root);
32.     root = insert(3,root);
33.     root = insert(7,root);
34.     root = insert(20,root);
35.     root = insert(8,root);
36.     root = delete(5,root);
37.     trace(root);
38.
39.     return 0;
40. }
41.
42.
43. void trace(TNode T){
44.     if(T!=NULL){
45.         trace(T->left);
46.         printf("%d\n ",T->data);
47.         trace(T->right);
48.     }
49.
50. }
51.
52. int findHeight(TNode root){
53.
54.     if(root == NULL)
55.         return -1;
56.     else
57.         return max(findHeight(root->left),findHeight(root->left))+1;
58. }
59.
60.
61.
62. int max(int x, int y){
63.     if(x>=y)
64.         return x;
65.     else
66.         return y;
67. }
68.
69.
70. TNode makeEmpty(TNode root){
71.     if(root!=NULL){
72.         return makeEmpty(root->left);
73.         return makeEmpty(root->right);
74.         free(root);
75.     }
76.
77.     return NULL;
78. }
79.
80.
81. TNode find(int x, TNode root){
82.     if(root == NULL)
83.         return NULL;
84.     if(root->data == x){
85.         return root;
86.     }else if(x<root->data){
87.         return find(x,root->left);
88.     }else{
89.         return find(x,root->right);
90.     }
91. }
92.
93.
94. TNode findMin(TNode root){
95.     if(root == NULL)
96.         return NULL;
97.     else if (root->left == NULL)
98.         return root;
99.     else
100.         return findMin(root->left);
101. }
102.
103.
104.
105. TNode findMax(TNode root){
106.     if(root == NULL)
107.         return NULL;
108.     else if (root->right == NULL)
109.         return root;
110.     else
111.         return findMax(root->right);
112. }
113.
114.
115.
116.
117.
118. TNode delete(int x, TNode T){
119.     TNode temp;
120.     if(T==NULL){
121.         printf("Didn't find the node to be deleted!\n");
122.         return NULL;
123.     }
124.     else if (x<T->data) T->left = delete(x,T->left);
125.     else if (x>T->data) T->right = delete(x,T->right);
126.
127.     else{//element Found!!
128.
129.
130.
131.
132.         if(T->left == NULL && T->right == NULL){//No children
133.             free(T);
134.             T = NULL;
135.         }else if(T->left == NULL){  //one right child
136.             TNode temp = T;
137.             T = T->right;
138.             free(temp);
139.         }else if(T->right == NULL){ //one left child
140.             TNode temp = T;
141.             T = T->left;
142.             free(temp);
143.         }else{  //two children
144.             TNode temp = findMin(T->right);
145.             T->data = temp->data;
146.             delete(T->data, T->right);
147.         }
148.
149.
150.
151.     }
152.
153.     return T;
154.
155.
156. }
157.
158.
159.
160.
161. struct BstNode* getNewNode(int data){
162.     struct BstNode* newNode = malloc(sizeof(struct BstNode));
163.
164.     newNode->data = data;
165.     newNode->left = NULL;
166.     newNode->right = NULL;
167.     newNode->count = 1;
168.
169.     return newNode;
170. }
171.
172.
173. struct BstNode* insert (int data, TNode root){
174.     if(root == NULL ){//the tree is empty
175.         root = getNewNode(data);
176.        // printf("%d\n",root->data);
177.         return root;
178.     }else if(data == root->data){
179.         //printf("%d\n",root->data);
180.         root->count++;
181.     }else if (data<root->data)
182.     {
183.         root->left = insert(data , root->left);
184.     }else{
185.         root->right = insert(data , root->right);
186.     }
187.
188. }
189.
190.
191.