/// Input: The elements to add. Will be added in the same order as they are read to the tree. #include #include #include #include /// Helper class for Binary Search Tree I/O Operations. struct BST { enum class DFT { PREORDER, POSTORDER, INORDER, OUTORDER }; struct flags { static const std::ios_base::fmtflags preorder_mode = std::ios_base::fmtflags( 0x2000000), postorder_mode = std::ios_base::fmtflags( 0x4000000), inorder_mode = std::ios_base::fmtflags( 0x8000000), outorder_mode = std::ios_base::fmtflags(0x10000000), by_level_mode = std::ios_base::fmtflags(0x20000000); }; static std::ostream& preorder(std::ostream& os) { os.setf(flags::preorder_mode); os.unsetf(flags::postorder_mode); os.unsetf(flags::outorder_mode); os.unsetf(flags::by_level_mode); os.unsetf(flags::inorder_mode); return os; } static std::ostream& postorder(std::ostream& os) { os.setf(flags::postorder_mode); os.unsetf(flags::preorder_mode); os.unsetf(flags::by_level_mode); os.unsetf(flags::inorder_mode); os.unsetf(flags::outorder_mode); return os; } static std::ostream& inorder(std::ostream& os) { os.unsetf(flags::preorder_mode); os.unsetf(flags::postorder_mode); os.setf(flags::inorder_mode); os.unsetf(flags::by_level_mode); os.unsetf(flags::outorder_mode); return os; } static std::ostream& outorder(std::ostream& os) { os.unsetf(flags::postorder_mode); os.unsetf(flags::preorder_mode); os.unsetf(flags::inorder_mode); os.unsetf(flags::by_level_mode); os.setf(flags::outorder_mode); return os; } static std::ostream& by_level(std::ostream& os) { os.setf(flags::by_level_mode); os.unsetf(flags::preorder_mode); os.unsetf(flags::postorder_mode); os.unsetf(flags::outorder_mode); os.unsetf(flags::inorder_mode); return os; } }; /// Class to represent a Binary Search Tree. template> class binary_search_tree { private: class node { Type value; node * left, * right; friend class binary_search_tree; public: node(Type val, node* left_node = nullptr, node* right_node = nullptr) : value(val), left(left_node), right(right_node) {} }; public: using value_type = Type; using size_type = size_t; class vertex { node* p; public: using value_type = Type; using difference_type = std::ptrdiff_t; using pointer = Type*; using reference = Type&; explicit vertex(node* n = nullptr) : p(n) { } vertex(const vertex& it) : p(it.p) { } vertex(vertex&& it) : p(it.p) { it.p = nullptr; } bool is_null() { return p==nullptr; } reference operator*() { return p->value; } const reference operator*() const { return p->value; } pointer operator->() { return &(p->value); } vertex& operator=(node* n) { p=n; return *this; } vertex& operator=(const vertex& i) { if(this!=&i) { p=i.p; } return *this; } vertex& operator=(vertex&& i) { if(this!=&i) { p=i.p; i.p=nullptr; } return *this; } bool operator==(const vertex& i) const noexcept { return p==i.p; } bool operator!=(const vertex& i) const noexcept { return p!=i.p; } bool has_left_child() { return p!=nullptr && p->left!=nullptr; } bool has_right_child() { return p!=nullptr && p->right!=nullptr; } bool has_child() { return has_left_child() || has_right_child(); } vertex left_child() { return static_cast(p->left); } vertex right_child() { return static_cast(p->right); } node*& left() { return p->left; } node*& right() { return p->right; } vertex& operator++() { p=p->right; return *this; } vertex& operator--() { p=p->left; return *this; } vertex operator++(int) { vertex clone = *this; ++*this; return clone; } vertex operator--(int) { vertex clone = *this; --*this; return clone; } size_type height() { if(p==nullptr) { return 0; } else if(!has_child()) { return 1; } else return 1+std::max(left_child().height(), right_child().height()); } bool operator==(const node*& i) const noexcept { return p==i; } bool operator!=(const node*& i) const noexcept { return p!=i; } friend bool operator==(const node*& i, const vertex& it) { return it.p==i; } friend bool operator!=(const node*& i, const vertex& it) { return it.p!=i; } operator node*& () { return p; } }; binary_search_tree() : root(nullptr), end_iter(nullptr), compare(Predicate{}) { csize=0; } binary_search_tree(const binary_search_tree& bst) : root(nullptr), end_iter(nullptr), compare(Predicate{}) { compare = bst.compare; bst.traverse_preorder([this](const vertex& node){ this->insert(*node); }); } binary_search_tree(binary_search_tree&& bst) : binary_search_tree() { compare=std::move(bst.compare); root=bst.root; csize=bst.csize; bst.csize=0; bst.root=bst.end_iter; } ~binary_search_tree() { clear(); } /// Assigns binary search tree with content from another binary search tree (deep copying). binary_search_tree& operator=(const binary_search_tree& bst) { if(this!=&bst) { this->clear(); this->compare = bst.compare; bst.traverse_preorder([this](const vertex& node){ this->insert(*node); }); } return *this; } /// Assigns the binary search tree with content from an rvalue binary search tree (move). binary_search_tree& operator=(binary_search_tree&& bst) { if(this!=&bst) { root=bst.root; csize=bst.csize; compare=std::move(bst.compare); end_iter=bst.end_iter; bst.root=bst.end_iter; bst.csize=0; } return *this; } vertex begin() { return root; } vertex end() const { return end_iter; } const vertex& begin() const { return root; } /// Checks if the tree is empty. bool empty() const noexcept { return csize==0; } /// Returns the size of the binary search tree. size_type size() const noexcept { return csize; } /// Clears the tree, deleting all elements and subtrees. void clear() { erase_recursive(root); root = end_iter; } /// Erases a node given by 'begin', and its subtrees. void erase_recursive(vertex begin) { if(begin!=end_iter) { erase_recursive(begin.left_child()); erase_recursive(begin.right_child()); delete begin; csize--; } } /// Inserts a new element into the binary search tree. binary_search_tree& insert(const value_type& value) { vertex it = root, prev_it = root; if(root==end_iter) { root = new node(value); csize++; } else { while(it!=end_iter) { prev_it = it; compare(value, *it) ? --it : ++it ; } if(compare(value, *prev_it)) prev_it.left() = new node(value); else { prev_it.right() = new node(value); } csize++; } return *this; } /// Performs breadth-wise or level by level traversal of the tree. void breadth_traverse(std::function action, vertex begin) const noexcept; /// Performs depth-wise traversal of the tree, and processes nodes as per traversal type. void depth_traverse(std::function action, vertex begin, BST::DFT mode = BST::DFT::PREORDER) const noexcept; void traverse_preorder(std::function action) const { depth_traverse(action, root, BST::DFT::PREORDER); } void traverse_postorder(std::function action) const { depth_traverse(action, root, BST::DFT::POSTORDER); } void traverse_inorder(std::function action) const { depth_traverse(action, root, BST::DFT::INORDER); } void traverse_outorder(std::function action) const { depth_traverse(action, root, BST::DFT::OUTORDER); } void breadth_traverse(std::function action) const { breadth_traverse(action, root); } /// Returns a mirrored binary tree, with the opposite predicate. binary_search_tree mirror() const noexcept; /// Reads the elements of the binary search tree from an input stream. friend std::istream& operator>>(std::istream& is, binary_search_tree& bst) { bst.clear(); std::string s; std::getline(is, s); value_type val; std::stringstream ss(s); while(ss.good()) { ss>>val; bst.insert(val); } return is; } /// Prints the binary search tree to an output stream. friend std::ostream& operator<<(std::ostream& os, const binary_search_tree& bst) { if(bst.empty()) return os; else if((os.flags()&BST::flags::preorder_mode)==BST::flags::preorder_mode) { bst.traverse_preorder([&os](vertex v){ os<<*v<<", "; }); if(bst.csize>0) { os<<"\b\b "; } } else if((os.flags()&BST::flags::postorder_mode)==BST::flags::postorder_mode) { bst.traverse_postorder([&os](vertex v){ os<<*v<<", "; }); if(bst.csize>0) { os<<"\b\b "; } } else if((os.flags()&BST::flags::inorder_mode)==BST::flags::inorder_mode) { bst.traverse_inorder([&os](vertex v){ os<<*v<<", "; }); if(bst.csize>0) { os<<"\b\b "; } } else if((os.flags()&BST::flags::outorder_mode)==BST::flags::outorder_mode) { bst.traverse_outorder([&os](vertex v){ os<<*v<<", "; }); if(bst.csize>0) { os<<"\b\b "; } } else if((os.flags()&BST::flags::by_level_mode)==BST::flags::by_level_mode) { bst.breadth_traverse([&os](vertex v){ os<<*v<<", "; }); if(bst.csize>0) { os<<"\b\b "; } } return os; } private: vertex root, end_iter; size_type csize = 0; std::function compare = Predicate{}; }; template void binary_search_tree::breadth_traverse (std::function::vertex&)> action, binary_search_tree::vertex begin) const noexcept { std::queue to_visit; if(root!=end_iter) { to_visit.push(begin); } while(!to_visit.empty()) { if(to_visit.front().has_left_child()) { to_visit.push(to_visit.front().left_child()); } if(to_visit.front().has_right_child()) { to_visit.push(to_visit.front().right_child()); } action(to_visit.front()); to_visit.pop(); } } template void binary_search_tree::depth_traverse (std::function::vertex&)> action, binary_search_tree::vertex begin, BST::DFT mode) const noexcept { switch(mode) { case BST::DFT::PREORDER: if(begin!=end_iter) { action(begin); depth_traverse(action, begin.left_child(), mode); depth_traverse(action, begin.right_child(), mode); } break; case BST::DFT::POSTORDER: if(begin!=end_iter) { depth_traverse(action, begin.left_child(), mode); depth_traverse(action, begin.right_child(), mode); action(begin); } break; case BST::DFT::INORDER: if(begin!=end_iter) { depth_traverse(action, begin.left_child(), mode); action(begin); depth_traverse(action, begin.right_child(), mode); } break; case BST::DFT::OUTORDER: if(begin!=end_iter) { depth_traverse(action, begin.right_child(), mode); action(begin); depth_traverse(action, begin.left_child(), mode); } break; } } template binary_search_tree binary_search_tree::mirror() const noexcept { binary_search_tree mirror_bst(*this); std::queue to_visit; if(mirror_bst.root!=end_iter) { to_visit.push(mirror_bst.root); } while(!to_visit.empty()) { vertex& node = to_visit.front(); if(node.has_child()) std::swap(node.left(), node.right()); if(node.has_left_child()) { to_visit.push(node.left_child()); } if(node.has_right_child()) { to_visit.push(node.right_child()); } to_visit.pop(); } mirror_bst.compare = [this](value_type v1, value_type v2)->bool{ return !this->compare(v1,v2); }; return mirror_bst; } int main() { binary_search_tree bst; std::cin>>bst; std::cout<<"Preorder: "<

BST - Mirror Tree