C Data Structures: Binary Trees, DFS, and Stack Logic

7th Experiment: Binary Tree Construction

This experiment demonstrates the construction of a binary tree from an array and its in-order traversal.

#include <stdio.h>
#include <stdlib.h>

struct node {
  struct node* left;
  char data;
  struct node* right;
};

struct node* constructTree(int index);
void inorder(struct node* root);

char array[] = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', '\0', '\0', 'H' };
int leftcount[] = { 1, 3, 5, -1, 9, -1, -1, -1, -1, -1 };
int rightcount[] = { 2, 4, 6, -1, -1, -1, -1, -1, -1, -1 };

int main() {
  struct node* root = constructTree(0);
  printf("In-order Traversal: \n");
  inorder(root);
  return 0;
}

struct node* constructTree(int index) {
  struct node* temp = NULL;
  if (index != -1) {
    temp = (struct node*)malloc(sizeof(struct node));
    temp->left = constructTree(leftcount[index]);
    temp->data = array[index];
    temp->right = constructTree(rightcount[index]);
  }
  return temp;
}

[03:21, 22/10/2024] Bhalendu Singh:

void inorder(struct node* root) {
  if (root != NULL) {
    inorder(root->left);
    printf("%c\t", root->data);
    inorder(root->right);
  }
}

8th Experiment: Depth First Search (DFS)

This program implements the Depth First Search (DFS) algorithm using an adjacency matrix to represent a graph.

#include <stdio.h>
#include <stdlib.h>

int source, V, E, time, visited[20], G[20][20];

void DFS(int i) {
  int j;
  visited[i] = 1;
  printf("%d ->", i + 1);
  for (j = 0; j < V; j++) {
    if (G[i][j] == 1 && visited[j] == 0)
      DFS(j);
  }
}

int main() {
  int i, j, v1, v2;
  printf("\t\t\tGraphs\n");
  printf("Enter the No. of Edges: ");
  scanf("%d", &E);
  printf("Enter the No. of Vertices: ");
  scanf("%d", &V);

  for (i = 0; i < V; i++) {
    for (j = 0; j < V; j++)
      G[i][j] = 0;
  }

  for (i = 0; i < E; i++) {

[03:32, 22/10/2024] Bhalendu Singh:

    printf("Enter the Edges (format: V1 V2): ");
    scanf("%d %d", &v1, &v2);
    G[v1 - 1][v2 - 1] = 1;
  }

  for (i = 0; i < V; i++) {
    for (j = 0; j < V; j++)
      printf(" %d ", G[i][j]);
    printf("\n");
  }

  printf("Enter the source: ");
  scanf("%d", &source);
  DFS(source - 1);
  return 0;
}

3rd Experiment: Infix to Postfix Conversion

This section demonstrates the conversion of an infix expression to postfix notation using a stack.

#include <stdio.h>
#include <ctype.h>

char stack[100];
int top = -1;

void push(char x) {
  stack[++top] = x;
}

char pop() {
  if (top == -1)
    return -1;
  else
    return stack[top--];
}

int priority(char x) {
  if (x == '(')
    return 0;
  if (x == '+' || x == '-')
    return 1;
  if (x == '*' || x == '/')
    return 2;
  return 0;
}

int main() {
  char exp[100];
  char *e, x;
  printf("Enter the Expression: ");
  scanf("%s", exp);
  printf("\n");
  e = exp;

  while (*e != '\0') {
    if (isalnum(*e))
      printf("%c ", *e);
    else if (*e == '(')
      push(*e);
    else if (*e == ')') {
      while ((x = pop()) != '(')
        printf("%c ", x);
    } else {
      while (top != -1 && priority(stack[top]) >= priority(*e))
        printf("%c ", pop());
      push(*e);
    }
    e++;
  }

  while (top != -1) {
    printf("%c", pop());
  }
  return 0;
}

3rd exp