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

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

#include <stdio.h>

#define RIGHT_SIBLING 0
#define PARENT 1

#define NIL 0

struct node {
  int key;
  struct node* left_child;
  struct node* p;
  int flag;
};

int visit_parent(struct node* node);
void visit_children(struct node* node, int children[], int* cp);
void set_node(struct node* node, int key, struct node* left_child, struct node* p, int flag);
void visit(struct node* node);

int visit_parent(struct node* node) {
  if (node == NULL)
    return NIL;
  while (node->flag != PARENT) 
    node = node->p;
  if (node->p == NULL) 
    return NIL;
  else 
    return node->p->key;
}

void visit_children(struct node* node, int children[], int* cp) {
  if (node == NULL)
    return;
  *cp = 0;
  struct node* child = node->left_child;
  while (child != NULL) {
    children[*cp] = child->key;
    *cp = (*cp) + 1;
    if (child->flag == RIGHT_SIBLING)
      child = child->p;
    else
      child = NULL;
  }
}

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

void visit(struct node* node) {
  int parent_key = visit_parent(node);
  if (parent_key == NIL) 
    printf("parent: NIL, children: ");
  else 
    printf("parent: %d, children: ", parent_key);

  int children[10] = {NIL};
  int count;
  int i;
  visit_children(node, children, &count);
  for (i = 0; i < count; i++)
    printf(" %d", children[i]);
  printf("\n");
}
/*
 *          1
 *          |
 *          2
 *      |   |   |
 *      3   4   5
 */
void test_1() {
  struct node node1, node2, node3, node4, node5;

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

  visit(&node1);
  visit(&node2);
  visit(&node3);
  visit(&node4);
  visit(&node5);
}

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