Tree in C

I recently came back to C after a long time (about 12+ years).

For one thing pointers seem a lot less complicated than I remember, in fact they’re pretty easy to understand. Besides this I’ve found a like the simplicity of the language and the closeness to the machine.

I think what changed from my college days regarding pointers is a better understanding of the stack and exposure to languages like C# with reference and value types.

I’ve written a short program that creates a tree data structure and that allows to navigate it in three different ways:

Depth first pre-order
Depth first post-order
Breadth first

Depth first just means starting from one node and going as deep as possible until you find a leaf node (a node with no children) and then backtracking. You can do this in an iterative way but for me this is so much simpler to understand using recursion.

The difference between pre-order and post-order is when you apply your operation on the tree node, before or after continuing traversal of the tree. You can look at the example below.

Breadth first on the other hand is easier done in an iterative way. The key here is keeping a second data structure, a queue to store the nodes. After you visit a node you enqueue it’s children and visit them in turn, printing their value and enqueuing they’re children in turn.

It’s all pretty simple stuff but I needed a refresher on this topic and also something simple to start writing C code again.

The code is on GitHub.

Here is the code of the main file, tree.c:

#include <stdio.h>
#include <stdlib.h>
#include "queue.c"

struct tree_node {
  int value;
  struct tree_node *parent;
  struct tree_node *left, *right;
};

typedef struct tree_node node;
typedef void (*node_func)(node *);

node * create_node(int, node *);
node * build_tree();
void breadth_first(node *);
void create_or_enqueue(q_node **, node *);
void depth_first_pre(node *, node_func);
void depth_first_post(node *, node_func);
void print_node(node *);
void free_node(node *);

int main() {
  node *root = build_tree();

  // depth_first_pre(root, print_node);
  breadth_first(root);
  depth_first_post(root, free_node);

  return 0;
}

node * create_node(int value, node *parent) {
  node *new = malloc(sizeof(node));
  new->value = value;
  new->parent = parent;

  return new;
}

/* builds a tree with a preset of data */
node * build_tree() {
  node *root = create_node(2, NULL);
    root->left = create_node(7, root);
      root->left->left = create_node(2, root->left);
      root->left->right = create_node(6, root->left);
        root->left->right->left = create_node(5, root->left->right);
        root->left->right->right = create_node(11, root->left->right);
    root->right = create_node(5, root);
      root->right->right = create_node(9, root->right);
        root->right->right->left = create_node(4, root->right->right);

  return root;
}

/* Pre-order Depth-first traversal */
void depth_first_pre(node *current, node_func func) {
  if (current == NULL) {
    return;
  }

  (func(current));

  depth_first_pre(current->left, func);
  depth_first_pre(current->right, func);
}

/* Post-order Depth-first traversal */
void depth_first_post(node *current, node_func func) {
  if (current == NULL) {
    return;
  }

  depth_first_post(current->left, func);
  depth_first_post(current->right, func);

  (func(current));
}

/* breadth-first traversal */
void breadth_first(node *current) {
  if (current == NULL) {
    return;
  }

  q_node *head = create_qnode(current);

  while (head != NULL) {
    q_node *q_node_ptr = dequeue(&head);
    node *node_ptr = q_node_ptr->value;
    printf("%d, ", node_ptr->value);
    q_node **head_ptr = &head;

    if (node_ptr->left != NULL) {
      create_or_enqueue(head_ptr, node_ptr->left);
    }

    if (node_ptr->right != NULL) {
      create_or_enqueue(head_ptr, node_ptr->right);
    }
  }
}

void create_or_enqueue(q_node **head, node *next_node) {
  if (*head == NULL) {
    *head = create_qnode(next_node);
  }
  else {
    enqueue(*head, create_qnode(next_node));
  }
}

void print_node(node *current) {
  printf("%d, ", current->value);
}

void free_node(node *current) {
  free(current);
}

Here is my simple implementation of a queue (keep in mind that I haven’t done any C programming for more than a decade) which I use for the breadth first algorithm:

#include <stdlib.h>

struct queue_node {
  void * value;
  struct queue_node *next;
};

typedef struct queue_node q_node;

q_node * create_qnode(void *);
void enqueue(q_node *, q_node *);
q_node * dequeue(q_node **);

q_node * create_qnode(void * value) {
  q_node *new = malloc(sizeof(q_node));
  new->value = value;

  return new;
}

void enqueue(q_node *head, q_node *new) {
  if (new == NULL || head == NULL) {
    return;
  }

  q_node *node_ptr = head;
  while (node_ptr->next != NULL) {
    node_ptr = node_ptr->next;
  }

  node_ptr->next = new;
}

q_node * dequeue(q_node **head) {
  if (*head == NULL) {
    return NULL;
  }

  q_node *old_head = *head;
  *head = (*head)->next;

  return old_head;
}

The function to create the data uses the tree from the Wikipedia article on Tree.

Public domain Tree diagram.
Public domain Tree diagram.

Here is the output from traversing the tree depth first pre-order:
2, 7, 2, 6, 5, 11, 5, 9, 4

And here is the output from traversing the tree breadth first:
2, 7, 5, 2, 6, 9, 5, 11, 4

If you have any suggestions to improve the code or see any mistakes don’t hesitate to point them out in the comments.

I will probably look into doing some basic compression in C next and then as a further project I might end up converting these in Rust for the experience of comparing the two languages. Hopefully I might get some insights into Rust at the same time.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s