btree.cpp


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

/* btree.cpp
 * Date: 2021-11-22
 * Author: Aryadev Chavali
 */

#include <iostream>

enum Order
{
  LT,
  GT,
  EQ
};

template <typename T>
struct BinaryTree
{
  T value;
  BinaryTree<T> *left, *right;
  enum Order (*compare)(T, T);
  ~BinaryTree()
  {
    delete left;
    delete right;
  }
};

template <typename T>
BinaryTree<T> *insert(BinaryTree<T> *tree, T value)
{
  BinaryTree<T> **node = &tree;
  switch (tree->compare(value, tree->value))
  {
  case LT:
    node = &tree->left;
    break;
  case EQ:
  case GT:
    node = &tree->right;
    break;
  }

  if (*node)
  {
    *node = insert(*node, value);
    return tree;
  }
  *node          = new BinaryTree<T>;
  (*node)->value = value;
  (*node)->left = (*node)->right = nullptr;
  (*node)->compare               = tree->compare;
  return tree;
}

int main(void)
{
  auto tree     = new BinaryTree<int>;
  tree->value   = 5;
  tree->compare = [](int x, int y)
  {
    if (x < y)
      return LT;
    else if (x > y)
      return GT;
    else
      return EQ;
  };

  for (int i = 0; i <= 5; ++i)
    tree = insert(tree, i * 2);

  std::cout << tree->left->value << ", "
            << tree->value << ", "
            << tree->right->value << std::endl;
  delete tree;
  return 0;
}