1#include "btree.h"
  2#include <stdio.h>
  3#include <stdlib.h>
  4
  5/**
  6 * Print a visual representation of an binary tree.
  7 *
  8 * @param tree The subtree to print
  9 * @param level The level in the tree that this subtree is in
 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 an instance of an binary tree.
 25 *
 26 * @param data The value to assign to the new node in the tree.
 27 * @return Returns the new binary tree node instance.
 28 */
 29BTree *btree_initialize(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 * Inserts a new value into a binary subtree.
 39 *
 40 * @param tree The subtree to attempt to insert a new value into.
 41 * @param data The data to insert into the tree.
 42 * @return Returns the new root of the subtree.
 43 */
 44BTree *btree_insert(BTree *tree, int data) {
 45  if (!tree)
 46    return btree_initialize(data);
 47
 48  if (data <= tree->data)
 49    if (tree->left)
 50      btree_insert(tree->left, data);
 51    else
 52      tree->left = btree_initialize(data);
 53  else if (tree->right)
 54    btree_insert(tree->right, data);
 55  else
 56    tree->right = btree_initialize(data);
 57
 58  return tree;
 59}
 60
 61/**
 62 * Returns the height of a binary subtree.
 63 *
 64 * @param tree The subtree to interrogate.
 65 * @return The height of the subtree
 66 */
 67int btree_height(BTree *tree) {
 68  if (tree == NULL)
 69    return 0;
 70
 71  int left = btree_height(tree->left);
 72  int right = btree_height(tree->right);
 73
 74  return (left > right) ? left + 1 : right + 1;
 75}
 76
 77/**
 78 * Prints a visual inspection of
 79 * a binary tree for debugging purposes to stdout.
 80 *
 81 * @param tree The tree to visualize
 82 */
 83void btree_inspect(BTree *tree) { inspect(tree, 0); }
 84
 85int btree_leaves(BTree *tree) {
 86  if (tree == NULL)
 87    return 0;
 88
 89  if (tree->left == NULL && tree->right == NULL)
 90    return 1;
 91
 92  return btree_leaves(tree->left) + btree_leaves(tree->right);
 93}
 94
 95/**
 96 * Generates a binary tree with a desired number of leaf
 97 * nodes.
 98 *
 99 * @param leaves The total number of leaf nodes to generate in the tree.
100 * @return Returns a new binary tree.
101 */
102BTree *btree_generate(int leaves) {
103  BTree *tree = NULL;
104
105  while (btree_leaves(tree) < leaves)
106    tree = btree_insert(tree, rand());
107  return tree;
108}