Solution to 10.4-5 in Introduction to Algorithms, Third Edition

 

#include <stdio.h>

#define TRAVERSE 0
#define LEFT_BACKTRACK 1
#define RIGHT_BACKTRACK 2

struct node {
  int key;
  struct node* p;
  struct node* left;
  struct node *right;
};

void traverse(struct node* node);
void set_node(struct node* node, int key, struct node* p, struct node* left, 
    struct node* right);

void set_node(struct node* node, int key, struct node* p, struct node* left, 
    struct node* right) {
  node->key = key;
  node->p = p;
  node->left = left;
  node->right = right;
}

void traverse(struct node* node) {
  int pos = TRAVERSE;
  printf("Traversing tree...\n");
  while (node != NULL) {
    if (pos == TRAVERSE)
      printf("node.key: %d\n", node->key);
    if (node->left != NULL && pos == TRAVERSE) {
      pos = TRAVERSE;
      node = node->left;
    } else if (node->right != NULL && (pos == TRAVERSE || pos == 
          LEFT_BACKTRACK)) {
      pos = TRAVERSE;
      node = node->right;
    } else if (node->p != NULL) {
      pos = node->p->left == node ? LEFT_BACKTRACK : RIGHT_BACKTRACK;
      node = node->p;
    } else {
      node = NULL;
    }
  }
}

/*
 * Tree:
 *     1
 */
void test_1() {
  struct node node1;
  set_node(&node1, 1, NULL, NULL, NULL);
  traverse(&node1);
}
/*
 * Tree:
 *      1
 *    /   \
 *  2       3
 */
void test_2() {
  struct node node1;
  struct node node2;
  struct node node3;
  
  set_node(&node1, 1, NULL, &node2, &node3);
  set_node(&node2, 2, &node1, NULL, NULL);
  set_node(&node3, 3, &node1, NULL, NULL);

  traverse(&node1);
}

/*
 * Tree:
 *                 1
 *               /   \
 *              2     3
 *            /  \      \
 *          4     5      6
 */
void test_3() {
  struct node node1;
  struct node node2;
  struct node node3;
  struct node node4;
  struct node node5;
  struct node node6;

  set_node(&node1, 1, NULL, &node2, &node3);
  set_node(&node2, 2, &node1, &node4, &node5);
  set_node(&node3, 3, &node1, NULL, &node6);
  set_node(&node4, 4, &node2, NULL, NULL);
  set_node(&node5, 5, &node2, NULL, NULL);
  set_node(&node6, 6, &node3, NULL, NULL);

  traverse(&node1);
}

/* 
 * Tree:
 *             1
 *           /   \
 *         /       \
 *       /           \
 *      2             3
 *        \          /  \
 *         \       /      \
 *          4     5        6
 *        /  \     \      /
 *       7    8     9    10
 *                 /
 *                11 
 */
void test_4() {
  struct node node1, node2, node3, node4, node5, node6, node7, node8, node9, 
              node10, node11;

  set_node(&node1, 1, NULL, &node2, &node3);

  set_node(&node2, 2, &node1, NULL, &node4);
  set_node(&node3, 3, &node1, &node5, &node6);

  set_node(&node4, 4, &node2, &node7, &node8);
  set_node(&node5, 5, &node3, NULL, &node9);
  set_node(&node6, 6, &node3, &node10, NULL);

  set_node(&node7, 7, &node4, NULL, NULL);
  set_node(&node8, 8, &node4, NULL, NULL);
  set_node(&node9, 9, &node5, &node11, NULL);
  set_node(&node10, 10, &node6, NULL, NULL);

  set_node(&node11, 11, &node9, NULL, NULL);

  traverse(&node1);
}

int main(int argc, const char *argv[]) {
  test_1();  
  test_2();
  test_3();
  test_4();
  return 0;
}