skwllsp
BAN USER#include <memory>
#include <iostream>
#include <queue>
#include <algorithm>
template <class T>
struct node {
public:
typedef node<T> node_t;
T value_;
std::unique_ptr<node_t> left_;
std::unique_ptr<node_t> right_;
node(T value) : value_ (value) { }
void add_left(T value) { left_ = std::move(std::unique_ptr<node_t>(new node<T>(value))); }
node& left() { return *left_; }
void add_right(T value) { right_ = std::move(std::unique_ptr<node_t>(new node<T>(value))); }
node& right() { return *right_; }
T value() const { return value_; }
bool is_leaf() const { return !right_ && !left_; }
};
template <class T>
void bfs_print(node<T>& start_node)
{
typedef node<T> node_t;
typedef std::pair<node_t*, int> node_and_level_t;
typedef std::deque< node_and_level_t > nodes_and_levels_t;
nodes_and_levels_t nodes;
nodes.push_back(std::make_pair(&start_node, 0) );
typename nodes_and_levels_t::iterator itr = nodes.begin();
while (itr != nodes.end()) {
node_and_level_t current_node = *itr;
if ( !current_node.first->is_leaf() ) {
if (current_node.first->left_ ) {
nodes.push_back(std::make_pair(&(current_node.first->left()), current_node.second+1));
}
if (current_node.first->right_ ) {
nodes.push_back(std::make_pair(&(current_node.first->right()), current_node.second+1));
}
}
++itr;
}
std::stable_sort(nodes.begin(), nodes.end(), [] (const node_and_level_t& a, const node_and_level_t& b) { return a.second > b.second; } );
std::for_each(nodes.begin(), nodes.end(), [] (const node_and_level_t& a) { std::cout << a.first->value() ; } );
}
int main()
{
node<int> root(1);
root.add_left(2);
root.add_right(3);
root.left().add_left(4);
root.left().add_right(5);
root.right().add_left(6);
root.right().add_right(7);
bfs_print(root);
return 0;
}
Look for "point stabbing queries for rectangles" on the Internet
- skwllsp October 18, 2012