binary tree
いきなりだが以下の code を見てくれ。こいつをどう思う ?
/* * main.cpp * binary tree * * written by janus_wel<janus.wel.3@gmail.com> * This source code is in public domain, and has NO WARRANTY. * */ #include <iostream> namespace data { namespace binarytree { template<typename Elem> struct basic_node { typedef Elem element_type; element_type element; basic_node* left; basic_node* right; basic_node(void) : element(NULL), left(NULL), right(NULL) {} basic_node(const element_type& element) : element(element), left(NULL), right(NULL) {} std::ostream& output_leave(std::ostream& o) const { if (left != NULL) left->output_leave(o); if (right != NULL) right->output_leave(o); return o << element; } std::ostream& output_through(std::ostream& o) const { if (left != NULL) left->output_through(o); o << element; if (right != NULL) right->output_through(o); return o; } std::ostream& output_enter(std::ostream& o) const { o << element; if (left != NULL) left->output_enter(o); if (right != NULL) right->output_enter(o); return o; } }; template<typename Elem> std::ostream& operator <<(std::ostream& o, const basic_node<Elem>& n) { n.output_enter(o); return o; } template<typename Elem> std::ostream& operator <<(std::ostream& o, const basic_node<Elem>* const n) { n->output_enter(o); return o; } } } int main(void) { typedef data::binarytree::basic_node<char> node_type; node_type* root = new node_type('/'); root->left = new node_type('*'); root->left->left = new node_type('+'); root->left->left->left = new node_type('a'); root->left->left->right = new node_type('b'); root->left->right = new node_type('-'); root->left->right->left = new node_type('c'); root->left->right->right = new node_type('d'); root->right = new node_type('/'); root->right->left = new node_type('e'); root->right->right = new node_type('f'); std::cout << root << std::endl; return 0; }
すごく…、二分木です…。
というか C++ って標準で binary tree を扱えないんだな。あれーたしか std::map は木で実装してたはずーと思って調べてみたら fundamental class が binary search tree みたいなので枝や葉を自分好みに偏らせて二分木を構築するのは標準じゃ無理ということがわかった。つまり自前で data structure から作るしかない、と。
でまぁ愚直に上記の code を書いたわけなんだけどこれだけだと使い物にならないんだよな…。 node をひとつひとつ new するのは面倒だし効率悪いし delete 忘れるしで。 allocator … ? あたりでどうにかなるのかもしれないけどなんか違う気がする。
ちょっと放置。