12 Árvores

12.1 Árvores binárias

template <typename T> struct btree;

template <typename T>
using btree_ptr = std::shared_ptr<btree<T>>;

template <typename T> struct btree {
  T value;
  btree_ptr left_child = nullptr;
  btree_ptr right_child = nullptr;
};

enum class ordering {
  in_order,
  pre_order,
  post_order,
};

template <typename T>
using visitor = std::function<bool(const T&)>;

template <typename T>
void dfs(btree_ptr<T> root, ordering order, const visitor& visit) {
  if (root == nullptr)
    return;

  switch (order)
  {
  case in_order:
    dfs(root->left_child, order, visit);
    if (!visit(root->value))
      return;
    dfs(root->right_child, order, visit);
    break;
  case pre_order:
    dfs(root->left_child, order, visit);
    dfs(root->right_child, order, visit);
    if (!visit(root->value))
      return;
    break;
  case post_order:
    if (!visit(root->value))
      return;
    dfs(root->left_child, order, visit);
    dfs(root->right_child, order, visit);
    break;
  }
}

template <typename T>
void bfs(btree_ptr<T> root, const visitor& visit) {
  std::queue<btree_ptr> queue;
  queue.push(root);

  while (!queue.empty())
  {
    if (queue.front() == nullptr) {
      queue.pop();
      continue;
    }

    if (!visit(queue.front()->value))
      return;

    queue.push(queue.front()->left_child);
    queue.push(queue.front()->right_child);
    queue.pop();
  }
}