**Course Title:** Mastering C: From Fundamentals to Advanced Programming **Section Title:** Dynamic Memory and Advanced Topics **Topic:** Create a program that implements a tree or graph using dynamic memory. (Lab topic) **Introduction:** In this lab topic, we will put into practice the concepts of dynamic memory management to create a program that implements a tree or graph data structure. This will help reinforce your understanding of dynamic memory allocation, pointer manipulation, and data structure implementation. **Prerequisites:** * Understanding of C programming basics, including variables, data types, operators, control structures, functions, arrays, and strings. * Knowledge of dynamic memory management using malloc, calloc, and free. * Familiarity with data structures such as linked lists, trees, and graphs. * Ability to write and debug C programs using a development environment like Code::Blocks or Visual Studio. **Understanding Tree and Graph Data Structures:** Before we dive into the implementation, let's quickly review the basics of tree and graph data structures: * **Trees:** A tree is a hierarchical data structure consisting of nodes, where each node has a value and zero or more child nodes. Trees can be categorized into binary trees, AVL trees, and more. * **Graphs:** A graph is a non-linear data structure consisting of nodes (vertices) connected by edges. Graphs can be directed or undirected, weighted or unweighted. **Choosing a Data Structure:** For this lab, we will implement a binary tree data structure. You can choose to implement either a binary search tree (BST) or a simple binary tree. **Implementing a Binary Tree:** * **Node Structure:** Create a struct to represent a node in the binary tree. The node structure should contain an integer value and pointers to the left and right child nodes. ```c typedef struct Node { int value; struct Node* left; struct Node* right; } Node; ``` * **Dynamic Memory Allocation:** Use dynamic memory allocation to allocate memory for each node. ```c Node* createNode(int value) { Node* newNode = (Node*) malloc(sizeof(Node)); if (!newNode) { printf("Memory error\n"); return NULL; } newNode->value = value; newNode->left = newNode->right = NULL; return newNode; } ``` * **Insertion:** Create a function to insert a new node into the binary tree. ```c Node* insertNode(Node* root, int value) { if (root == NULL) { root = createNode(value); return root; } if (value < root->value) { root->left = insertNode(root->left, value); } else if (value > root->value) { root->right = insertNode(root->right, value); } return root; } ``` * **Traversal:** Create functions to perform in-order, pre-order, and post-order traversal of the binary tree. ```c void inOrderTraversal(Node* root) { if (root == NULL) { return; } inOrderTraversal(root->left); printf("%d ", root->value); inOrderTraversal(root->right); } void preOrderTraversal(Node* root) { if (root == NULL) { return; } printf("%d ", root->value); preOrderTraversal(root->left); preOrderTraversal(root->right); } void postOrderTraversal(Node* root) { if (root == NULL) { return; } postOrderTraversal(root->left); postOrderTraversal(root->right); printf("%d ", root->value); } ``` **Freeing Memory:** Don't forget to free the allocated memory using a function that recursively traverses the tree and deallocates memory for each node. ```c void freeTree(Node* root) { if (root == NULL) { return; } freeTree(root->left); freeTree(root->right); free(root); } ``` **Putting it All Together:** Here's the complete code for the binary tree implementation: ```c #include <stdio.h> #include <stdlib.h> typedef struct Node { int value; struct Node* left; struct Node* right; } Node; Node* createNode(int value) { Node* newNode = (Node*) malloc(sizeof(Node)); if (!newNode) { printf("Memory error\n"); return NULL; } newNode->value = value; newNode->left = newNode->right = NULL; return newNode; } Node* insertNode(Node* root, int value) { if (root == NULL) { root = createNode(value); return root; } if (value < root->value) { root->left = insertNode(root->left, value); } else if (value > root->value) { root->right = insertNode(root->right, value); } return root; } void inOrderTraversal(Node* root) { if (root == NULL) { return; } inOrderTraversal(root->left); printf("%d ", root->value); inOrderTraversal(root->right); } void preOrderTraversal(Node* root) { if (root == NULL) { return; } printf("%d ", root->value); preOrderTraversal(root->left); preOrderTraversal(root->right); } void postOrderTraversal(Node* root) { if (root == NULL) { return; } postOrderTraversal(root->left); postOrderTraversal(root->right); printf("%d ", root->value); } void freeTree(Node* root) { if (root == NULL) { return; } freeTree(root->left); freeTree(root->right); free(root); } int main() { Node* root = NULL; root = insertNode(root, 50); root = insertNode(root, 30); root = insertNode(root, 20); root = insertNode(root, 40); root = insertNode(root, 70); root = insertNode(root, 60); root = insertNode(root, 80); printf("In-order traversal: "); inOrderTraversal(root); printf("\n"); printf("Pre-order traversal: "); preOrderTraversal(root); printf("\n"); printf("Post-order traversal: "); postOrderTraversal(root); printf("\n"); freeTree(root); return 0; } ``` **Conclusion:** In this lab topic, you have successfully implemented a binary tree data structure using dynamic memory allocation. You have learned how to create a node structure, allocate memory for nodes, insert nodes into the tree, perform traversals, and free the allocated memory. **Additional Resources:** * GeeksforGeeks: [Binary Tree](https://www.geeksforgeeks.org/binary-tree-data-structure/) * Wikipedia: [Binary Tree](https://en.wikipedia.org/wiki/Binary_tree) * Tutorials Point: [Binary Tree](https://www.tutorialspoint.com/data_structures_algorithms/binary_tree.htm) **What's Next:** In the next topic, you will work on your final project presentation. You will share your project's code and provide a walkthrough of your implementation. **Leave a comment or ask for help:** If you have any questions or need help with any part of the code, please don't hesitate to ask in the comments below.