Solution to 10.4-5 in Introduction to Algorithms, Third Edition
?
#include <stdio.h>#define TRAVERSE 0#define LEFT_BACKTRACK 1#define RIGHT_BACKTRACK 2struct 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;}