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.

Disable mouse wheel zoom in Visual Studio

Today I’ve found a great extension for Visual Studio. I often hit the toggle that changes the mouse wheel from scrolling text to zooming text. For me that’s a really annoying interruption to my workflow and one of my Visual Studio pet peeve.

I tend to use the keyboard a lot with a bit of mouse on the side. This means one of my finger is often on or near the Ctrl key. The toggle is
`Ctrl + the scroll wheel` so I frequently end up hitting it.

Apparently I’m not the only one because someone made an extension to disable this very feature: Disable Mouse Wheel Zoom.

I can’t recommend it enough ;). There are other ways to change the zoom level and I really don’t need to toggle this feature (I’m scrolling and using Ctrl chords much more often than I need to change the text size).

Search for things faster in Visual Studio with these two weird tricks

Here are two ways to search within a document that won’t open the search dialog in Visual Studio 2010. The first one is also useful for 2013.

Incremental search (Ctrl-i): Ctrl-i will start an incremental search. In Visual Studio 2010 this won’t even open the search dialog. Your search pattern will be displayed on the bottom bar in 2010 and in the standard search box in 2013. You can cycle through various entries by continuing to press Ctrl-i.

I often use incremental search to quickly jump to a specific location on the same line or a nearby line. For example if I want to jump to the word string I can just press Ctrl-i followed by the first few characters of the words I am looking for, in this case: st and I’m usually there. By using this feature I am able to prevent using the mouse or the arrow keys to move the cursor.

This is a big gain as taking your hands away from the keyboard has a huge impact on your workflow and the arrow keys are a slow way to move around (even with shift-arrow key).

Keep in mind that as the distance you need to travel increases, you’ll tend to get more and more misses with this strategy and might need to keep repeating Ctrl-i too much.

Search for the word under the cursor (Ctrl-F3): This next one is specific to Visual Studio 2010. If you want to find other occurrences of a specific word just move your cursor to it and then press Ctrl-F3 which will automatically send you to the next occurrence. Again this will not bring up the search dialog, which would then necessitate at least one more click to confirm.

You can continue pressing F3 (no need for the Ctrl key) to move to the other occurrences of the same word within the current file.

This is particularly useful when you are already positioned on the word you want to search, say a variable or function, and contrary to Find all references it will also find commented out instances.

In Visual Studio 2013 search has been improved which rendered this shortcut obsolete. You can still press Ctrl-F3 which will have the same behaviour has Ctrl-F. F3 will also cycle to the next search hits.

In the same series:

Delete things faster in Visual Studio with these two weird tricks

Delete things faster in Visual Studio with these two weird tricks

Here are two nifty keyboard shortcuts in Visual Studio:

Cut whole line (Ctrl-L): This will cut/delete the whole line and send it to the clipboard. This is useful in two situations.

First, it let’s you remove a whole line in a single action reliably.

For white space lines, depending on the line configuration, using delete or backspace might necessitate more than a single key stroke per line. Ctrl-l always does it in one action.

For non white-space lines Ctrl-l prevents you from having to select the whole line and then deleting it, saving you again one action. Every action saved counts.

The second situation is when you want to select a whole line, cut it, move and then paste it. With Ctrl-l you can reduce this from 4 actions to 3.

When using Ctrl-l if you overwrite your current clipboard you can do a Ctrl-Shift-v to cycle through your clipboard history.

Delete next word (Ctrl-Del): This is a universal shortcut that works for many programs but I have included it here since I learned about it recently. This will delete the whole word in front of you instead of just a single character.

In the same series:

Search for things faster in Visual Studio with these two weird tricks