All Tree Functions C++ PDF

1 #include 2 #include 3 4 // Node structure 5 typedef struct node { 6 int data; 7 struct node* left; 8 struct node* right; 9 } node; 10 11 // Create a new node 12 node* createNode(int value) { 13 node* N; 14 N = (node*) malloc(sizeof(node)); 15...

1 #include 2 #include 3 4 // Node structure 5 typedef struct node { 6 int data; 7 struct node* left; 8 struct node* right; 9 } node; 10 11 // Create a new node 12 node* createNode(int value) { 13 node* N; 14 N = (node*) malloc(sizeof(node)); 15 N->data = value; 16 N->left = N->right = NULL; 17 return N; 18 } 19 20 // Insert a new node 21 void insertNewNode(node** root, int val) { 22 node* N, *temp; 23 N = createNode(val); 24 if (*root == NULL) { 25 *root = N; 26 return; 27 } 28 temp = *root; 29 while (1) { 30 if (N->data > temp->data) { 31 if (temp->right == NULL) { 32 temp->right = N; 33 break; 34 } else { 35 temp = temp->right; 36 } 37 } else { 38 if (temp->left == NULL) { 39 temp->left = N; 40 break; 41 } else { 42 temp = temp->left; 43 } 44 } 45 } 46 } 47 48 // Find minimum value node 49 node* minimum(node* root) { 50 node* temp; 51 if (root == NULL) 52 return NULL; 53 54 temp = root; 55 while (temp->left != NULL) 56 temp = temp->left; 57 return temp; 58 } 59 60 // Find maximum value node 61 node* maximum(node* root) { 62 node* temp; 63 if (root == NULL) 64 return NULL; 65 66 temp = root; 67 while (temp->right != NULL) 68 temp = temp->right; 69 return temp; 70 } 71 72 // Search for a value in the tree 73 node* search(node* root, int v) {  74 if (root == NULL) 75 return NULL; 76 77 if (v == root->data) 78 return root; 79 else if (v < root->data) 80 return search(root->left, v); 81 else 82 return search(root->right, v); 83 } 84 85 // Delete a node from the tree 86 node* deleteNode(node* root, int v) { 87 if (root == NULL) 88 return root; 89 90 if (v == root->data) { 91 // Case 1: Deleted node is a leaf (degree = 00) 92 if (root->left == NULL && root->right == NULL) { 93 free(root); 94 root = NULL; 95 } 96 // Case 2: Node has one child (degree = 01) 97 else if (root->left == NULL) { 98 node* temp = root; 99 root = root->right; 100 free(temp); 101 } else if (root->right == NULL) { 102 node* temp = root; 103 root = root->left; 104 free(temp); 105 } 106 // Case 3: Node has two children (degree = 02) 107 else { 108 node* temp = minimum(root->right); 109 root->data = temp->data; 110 root->right = deleteNode(root->right, temp->data); 111 } 112 } else if (v < root->data) 113 root->left = deleteNode(root->left, v); 114 else 115 root->right = deleteNode(root->right, v); 116 117 return root; 118 } 119 120 // Pre-order traversal 121 void preOrder(node* root) { 122 if (root == NULL) 123 return; 124 printf("%d ", root->data); 125 preOrder(root->left); 126 preOrder(root->right); 127 } 128 129 // In-order traversal 130 void inOrder(node* root) { 131 if (root == NULL) 132 return; 133 134 inOrder(root->left); 135 printf("%d ", root->data); 136 inOrder(root->right); 137 } 138 139 // Post-order traversal 140 void postOrder(node* root) { 141 if (root == NULL) 142 return; 143 144 postOrder(root->left); 145 postOrder(root->right); 146 printf("%d ", root->data); 147 } 148 149 // Function to find the maximum of two integers used in the next fucntion 150 int max(int a, int b) { 151 return (a > b) ? a : b; 152 } 153 154 // Calculate the height of the tree 155 int height(node* root) { 156 if (root == NULL) { 157 return -1; // If the tree is empty, height is -1 158 } 159 160 // Return the greater of the two heights + 1 161 return 1 + max(height(root->left), height(root->right)); 162 163 } 164 165 // Function to calculate the number of leaf nodes in the tree 166 int countLeaves(node* root) { 167 if (root == NULL) { 168 return 0; // If the tree is empty, there are no leaves 169 } 170 171 // If the node is a leaf (both left and right are NULL) 172 if (root->left == NULL && root->right == NULL) { 173 return 1; // It's a leaf, so count it as 1 174 } 175 176 // Recursively count leaves in the left and right subtrees 177 return countLeaves(root->left) + countLeaves(root->right); 178 } 179 180 // Function to find the size of the binary tree 181 int size(node* root) { 182 // If the tree is empty, return 0 183 if (root == NULL) { 184 return 0; 185 } 186 187 // Otherwise, recursively count the nodes in the left and right subtrees 188 return 1 + size(root->left) + size(root->right); 189 } 190 /////incluant root 191 int countInternalNodes(node* root) { 192 if (root == NULL) { 193 return 0; // If the tree is empty, there are no internal nodes 194 } 195 196 // If the node has at least one child, it's an internal node 197 if (root->left != NULL || root->right != NULL) { 198 return 1 + countInternalNodes(root->left) + countInternalNodes(root->right); 199 } 200 201 // If the node has no children, it's a leaf, so we don't count it as an internal node 202 return 0; 203 } 204 205 206 // Function to return the right subtree of a given node 207 node* getRightSubtree(node* root) { 208 if (root == NULL) { 209 return NULL; // If the root is NULL, there is no right subtree 210 } 211 return root->right; // Return the right child (right subtree) of the node 212 } 213 214 // Function to check if the tree is empty 215 int isEmpty(node* root) { 216 return root == NULL; // Returns 1 if the tree is empty, 0 otherwise 217 } 218 219 int main() { 220 node *arbre = NULL; 221 222 insertNewNode(&arbre, 70); 223 insertNewNode(&arbre, 60); 224 insertNewNode(&arbre, 45); 225 insertNewNode(&arbre, 30); 226 insertNewNode(&arbre, 52); 227 insertNewNode(&arbre, 64); 228 insertNewNode(&arbre, 62); 229 insertNewNode(&arbre, 77); 230 insertNewNode(&arbre, 81); 231 insertNewNode(&arbre, 75); 232 233 // In-order traversal before deletion 234 inOrder(arbre); 235 printf("\n*****************\n"); 236 237 // Deleting a node 238 arbre = deleteNode(arbre, 64); 239 240 // In-order traversal after deletion 241 inOrder(arbre); 242 printf("\n*****************\n"); 243 244 // Print the height of the tree 245 printf("Height of the tree: %d\n", height(arbre)); 246 printf("Number of leaf nodes: %d\n", countLeaves(arbre)); 247 248 249 // Get the right subtree of the root 250 node* rightSubtree = getRightSubtree(arbre); 251 252 // Check if the right subtree exists and print its root value 253 if (rightSubtree != NULL) { 254 printf("Root of the right subtree: %d\n", rightSubtree->data); 255 } else { 256 printf("No right subtree exists.\n"); 257 } 258 259 260 // Check if the tree is empty after inserting nodes 261 if (isEmpty(arbre)) { 262 printf("The tree is empty.\n"); 263 } else { 264 printf("The tree is not empty.\n"); 265 } 266 267 268 return 0; 269 } 270