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

yaojingguo

#include <stdio.h>#define RIGHT_SIBLING 0#define PARENT 1#define NIL 0struct 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;}