Implementation of Binary Tree Using Dynamic Array
#include <stdio.h>
#include <stdlib.h>
typedef struct {
int *data; // Array to store tree nodes
int capacity; // Current capacity of the array
int size; // Current number of elements in the tree
} BinaryTree;
// Function to initialize the binary tree
BinaryTree* initializeTree(int initialCapacity) {
BinaryTree *tree = (BinaryTree*)malloc(sizeof(BinaryTree));
tree->data = (int*)malloc(initialCapacity * sizeof(int));
tree->capacity = initialCapacity;
tree->size = 0;
return tree;
}
// Function to resize the array when needed
void resizeTree(BinaryTree *tree) {
int newCapacity = tree->capacity * 2;
tree->data = (int*)realloc(tree->data, newCapacity *
sizeof(int));
tree->capacity = newCapacity;
}
// Function to add a new node to the binary tree
void addNode(BinaryTree *tree, int value) {
if (tree->size == tree->capacity) {
resizeTree(tree);
}
tree->data[tree->size] = value;
tree->size++;
}
// Function to get the left child index
int leftChildIndex(int index) {
return 2 * index + 1;
}
// Function to get the right child index
int rightChildIndex(int index) {
return 2 * index + 2;
}
// Function to print the tree elements
void printTree(BinaryTree *tree) {
printf("Binary Tree Elements:\n");
for (int i = 0; i < tree->size; i++) {
printf("%d ", tree->data[i]);
}
printf("\n");
}
// Function to free the tree memory
void freeTree(BinaryTree *tree) {
free(tree->data);
free(tree);
}
// Example usage
int main() {
BinaryTree *tree = initializeTree(4); // Initial capacity of 4
// Adding nodes
addNode(tree, 10); // Root
addNode(tree, 20); // Left child of root
addNode(tree, 30); // Right child of root
addNode(tree, 40); // Left child of node 20
addNode(tree, 50); // Right child of node 20
// Print tree elements
printTree(tree);
// Example: Accessing children of the root (index 0)
int rootIndex = 0;
printf("Root: %d\n", tree->data[rootIndex]);
printf("Left child of root: %d\n", tree-
>data[leftChildIndex(rootIndex)]);
printf("Right child of root: %d\n", tree-
>data[rightChildIndex(rootIndex)]);
// Free the tree memory
freeTree(tree);
return 0;
}
Implementation of Binary Tree Using Linked List
#include <stdio.h>
#include <stdlib.h>
// Define a structure for a tree node
typedef struct Node {
int data;
struct Node* left; // Pointer to the left child
struct Node* right; // Pointer to the right child
} Node;
// Function to create a new node
Node* createNode(int value) {
Node* newNode = (Node*)malloc(sizeof(Node));
if (newNode == NULL) {
printf("Memory allocation failed.\n");
return NULL;
}
newNode->data = value;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// In-order Traversal: Left -> Root -> Right
void inOrderTraversal(Node* root) {
if (root == NULL)
return;
inOrderTraversal(root->left);
printf("%d ", root->data);
inOrderTraversal(root->right);
}
// Pre-order Traversal: Root -> Left -> Right
void preOrderTraversal(Node* root) {
if (root == NULL)
return;
printf("%d ", root->data);
preOrderTraversal(root->left);
preOrderTraversal(root->right);
}
// Post-order Traversal: Left -> Right -> Root
void postOrderTraversal(Node* root) {
if (root == NULL)
return;
postOrderTraversal(root->left);
postOrderTraversal(root->right);
printf("%d ", root->data);
}
// Function to free the binary tree
void freeTree(Node* root) {
if (root == NULL)
return;
freeTree(root->left);
freeTree(root->right);
free(root);
}
// Main function to test the binary tree implementation
int main() {
// Manually create nodes
Node* root = createNode(10);
root->left = createNode(20);
root->right = createNode(30);
root->left->left = createNode(40);
root->left->right = createNode(50);
root->right->left = createNode(60);
root->right->right = createNode(70);
printf("In-order Traversal (Left, Root, Right):\n");
inOrderTraversal(root);
printf("\n");
printf("Pre-order Traversal (Root, Left, Right):\n");
preOrderTraversal(root);
printf("\n");
printf("Post-order Traversal (Left, Right, Root):\n");
postOrderTraversal(root);
printf("\n");
// Free the allocated memory
freeTree(root);
return 0;
}
