TeamCOINSECAVM/Tree

Created by JUNHWI KIM
 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110``` ```/* Example of Binary Tree from Ellis Horowitz, et al. Fundamentals of data structures in C. 2nd ed., Silicon Press, 2008, pp. 204-205. Written by Junhwi Kim */ #define MAX_STACK_SIZE 100 #define MAX_QUEUE_SIZE 100 #include #include typedef struct node *tree_pointer; typedef struct node { int data; tree_pointer left_child, right_child; }; void inorder (tree_pointer ptr) /* inorder tree traversal */ { if (ptr) { inorder(ptr->left_child); printf("%d", ptr->data); inorder(ptr->right_child); } } void preorder (tree_pointer ptr) /* preorder tree traversal */ { if (ptr) { printf("%d", ptr->data); inorder(ptr->left_child); inorder(ptr->right_child); } } void postorder (tree_pointer ptr) /* postorder tree traversal */ { if (ptr) { inorder(ptr->left_child); inorder(ptr->right_child); printf("%d", ptr->data); } } void iter_inorder(tree_pointer node) { int top = 0; tree_pointer stack[MAX_STACK_SIZE]; for (;;) { for(; node; node = node->left_child) { stack[++top] = node; } node = stack[top--]; if (!node) break; printf("%d", node->data); node = node->right_child; } } void level_order(tree_pointer ptr) /* level order tree traversal */ { int front = 0; int rear = 0; tree_pointer queue[MAX_QUEUE_SIZE]; if (!ptr) return; queue[++rear] = ptr; for (;;) { ptr = queue[++front]; if (ptr) { printf("%d", ptr->data); if(ptr->left_child) queue[++rear] = ptr->left_child; if(ptr->right_child) queue[++rear] = ptr->right_child; } else break; } } tree_pointer search(tree_pointer root, int key) /* return a pointer to the element whose key is k, if there is no such element, return NULL. */ { if (!root) return NULL; if (key == root->data) return root; if (key < root->data) return search(root->left_child, key); return search(root->right_child, key); } tree_pointer iter_search(tree_pointer tree, int k) { while (tree) { if (k == tree->data) return tree; if (k < tree->data) tree = tree->left_child; else tree = tree->right_child; } return NULL; } ```