Solution to 10.4-6 in Introduction to Algorithms, Third Edition
#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 = {NIL};int count;int i;visit_children(node, children, &count);for (i = 0; i < count; i++) printf(" %d", children);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;}
页:
[1]