13.6 問題7 解答を実装してみた(STL禁止)

マトリックス コンプリート・トリロジー [Blu-ray]
終盤に来て実装の問題が増える….
答えは載ってるけど,どうせ実装しないと覚えなさそう.
ということで以下写経.(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