13.6 問題7 解答を実装してみた(STL禁止)
終盤に来て実装の問題が増える….
答えは載ってるけど,どうせ実装しないと覚えなさそう.
ということで以下写経.(report関数は省略)
insert(int)の実装は楽しい.
ポインタのポインタを使うことで簡潔なコードで記述できる :)
(宿題で提出したコードはどんなんだったか…)
#include <iostream> #include <cstdlib> using namespace std; class Tree { int size_; public: struct node { int val; struct node * left; struct node * right; node() : left(NULL), right(NULL) {} }; node * tree; Tree() : size_(0), tree(new node()), sentinel(tree) { tree->left = tree->right = sentinel; } void insert( int x ) ; // void report( int * v ) const ; void print_tree( void ) const; int size() const { return size_; } private: void print_tree( node * ) const; node * sentinel; }; void Tree::insert( int x ){ sentinel->val = x; node ** p = &tree; while( (*p)->val != x ){ if( (*p)->val < x ){ p = &((*p)->right); }else{ p = &((*p)->left); } } if( (*p)==sentinel ){ (*p)=new node(); (*p)->val = x; (*p)->left = (*p)->right = sentinel; ++size_; cout << "insert : " << (*p)->val << endl; } } void Tree::print_tree( node * tree ) const { if(tree==sentinel){ return ; } cout << tree->val << endl; cout << " "; print_tree( tree->right ); cout << " "; print_tree( tree->left ); } void Tree::print_tree( void ) const { print_tree( this->tree ); } int main(){ Tree tree; const int N = 10; for(int i=0; i<N; i++){ int r=N*(double)rand()/RAND_MAX; tree.insert(r); } tree.print_tree(); return (0); }
内容と画像の関連はあんまりありません m(_ _)m
コード読んでたら思い出しただけですw