1#include "btree.h"
  2#include "stack.h"
  3#include <stdio.h>
  4
  5/**
  6 * Prints a visual representation of a binary tree
  7 *
  8 * @param tree The tree or subtree to print
  9 * @param level The level in the tree that the subtree belongs to
 10 */
 11static void inspect(BTree *tree, int level) {
 12  if (!tree)
 13    return;
 14
 15  for (int i = 0; i < level; i++)
 16    printf("  ");
 17
 18  printf("%2d\n", tree->data);
 19  inspect(tree->left, level + 1);
 20  inspect(tree->right, level + 1);
 21}
 22
 23/**
 24 * Initializes a new instance of a binary tree.
 25 *
 26 * @param data The data to bind to the root of the new subtree.
 27 * @return Returns the new subtree.
 28 */
 29BTree *btree_init(int data) {
 30  BTree *tree = malloc(sizeof(BTree));
 31  tree->left = NULL;
 32  tree->right = NULL;
 33  tree->data = data;
 34  return tree;
 35}
 36
 37/**
 38 * Performs and caches the result of a pre order traversal
 39 * on a binary tree. Cached results are stored in the root of
 40 * the tree and not on each node of the tree.
 41 *
 42 * @param tree The subtree to perform the traversal on
 43 */
 44void btree_pre_order_number(BTree *tree) {
 45  BTree *original = tree;
 46  if (tree == NULL)
 47    return;
 48
 49  Stack *stack = stack_init();
 50  int i = 0;
 51
 52  stack_push(stack, tree);
 53  while (stack_size(stack) > 0) {
 54    tree = stack_pop(stack);
 55    original->pre_order[i++] = tree->data;
 56
 57    if (tree->right != NULL)
 58      stack_push(stack, tree->right);
 59    if (tree->left != NULL)
 60      stack_push(stack, tree->left);
 61  }
 62}
 63
 64/**
 65 * Performs and caches the result of an in order traversal
 66 * on a binary tree. Cached results are stored in the root of
 67 * the tree and not on each node of the tree.
 68 *
 69 * @param root The subtree to perform the traversal on
 70 */
 71void btree_in_order_number(BTree *root) {
 72  BTree *original = root;
 73  if (root == NULL)
 74    return;
 75
 76  Stack *stack = stack_init();
 77  int i = 0;
 78
 79  while (true) {
 80    if (root) {
 81      stack_push(stack, root);
 82      root = root->left;
 83    } else {
 84      if (stack_size(stack) == 0)
 85        break;
 86
 87      root = stack_pop(stack);
 88      original->in_order[i++] = root->data;
 89      root = root->right;
 90    }
 91  }
 92}
 93
 94/**
 95 * Performs and caches the result of an post order traversal
 96 * on a binary tree. Cached results are stored in the root of
 97 * the tree and not on each node of the tree.
 98 *
 99 * @param root The subtree to perform the traversal on
100 */
101void btree_post_order_number(BTree *root) {
102  BTree *original = root;
103  if (root == NULL)
104    return;
105
106  Stack *s1 = stack_init();
107  Stack *s2 = stack_init();
108
109  stack_push(s1, root);
110
111  while (stack_size(s1) > 0) {
112    root = stack_pop(s1);
113    stack_push(s2, root);
114
115    if (root->left)
116      stack_push(s1, root->left);
117    if (root->right)
118      stack_push(s1, root->right);
119  }
120
121  int i = 0;
122  while (stack_size(s2) > 0) {
123    root = stack_pop(s2);
124    original->post_order[i++] = root->data;
125  }
126}
127
128/**
129 * Insert a new items into a binary tree.
130 *
131 * @param tree The tree to insert the data into.
132 * @param data The data to insert into the tree.
133 * @return Returns the new root of the tree.
134 */
135BTree *btree_insert(BTree *tree, int data) {
136  if (!tree)
137    return btree_init(data);
138
139  if (data <= tree->data)
140    if (tree->left)
141      btree_insert(tree->left, data);
142    else
143      tree->left = btree_init(data);
144  else if (tree->right)
145    btree_insert(tree->right, data);
146  else
147    tree->right = btree_init(data);
148
149  return tree;
150}
151
152/**
153 * Prints a visual representation of a binary tree.
154 *
155 * @param tree The subtree to inspect.
156 */
157void btree_inspect(BTree *tree) { inspect(tree, 0); }