こんにちは、次のテンプレート コードは、「Computational Geometry and Computer Graphics in C++ by Michael J Laszlo」からのものです。
コード
#include <cstdlib>
template <class T> class SearchTree;
template<class T> class TreeNode{
private:
TreeNode * _lchild;
TreeNode * _rchild;
T val;
public:
TreeNode(T);
virtual ~TreeNode(void);
friend class SearchTree<T>;
};
template <class T> TreeNode<T> :: TreeNode(T v) : val(v) , _lchild(NULL) , _rchild(NULL)
{}
template <class T> TreeNode <T> :: ~TreeNode(void)
{
if ( _lchild) delete _lchild;
if ( _rchild) delete _rchild;
}
//////////////////////////////////////////////////////////////////////////////////////
///////-------------------------------------------------------------------------------
//////////////////////////////////////////////////////////////////////////////////////
//////+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
/////////////////////////////////////////////////////////////////////////////////////
template <class T> class SearchTree {
private:
TreeNode <T> * root;
int (*cmp) (T,T);
void _inorder(TreeNode <T>*,void(*)(T));
public:
SearchTree ( int (*) (T,T));
~SearchTree(void);
int isEmpty(void);
T find(T);
T findMin(void);
void inorder( void (*) (T));
void insert(T);void remove(T);T removeMin(void);
};
template <class T>
SearchTree<T>::SearchTree(int(*c) (T,T)): cmp(c) ,root(NULL)
{}
template <class T>
SearchTree<T>::~SearchTree()
{ if (root) delete root ;}
template <class T> void SearchTree <T>::_inorder(TreeNode <T> *n ,void (*visit) (T))
{
if (n) {
_inorder(n->_lchild ,visit);
(*visit)(n->val);
_inorder(n->_rchild,visit);
};
}
template <class T> void SearchTree<T> :: inorder(void (*visit)(T)) {_inorder(root,visit);}
template <class T>
void SearchTree<T>::insert(T val)
{
if (root ==NULL) {
root =new TreeNode <T> (val);
return;
}
else{
int result;
TreeNode <T> * n, *p =root;
while (n) {
p=n;
result=(*cmp)(val,p->val);
if (result <0)
{n = p->_lchild;}
else if (result >0)
{ n= p->_rchild;}
else
{return ;};
}
if (result <0) p->_lchild =new TreeNode <T> (val);
else p -> _rchild =new TreeNode <T> (val);
}
}
template <class T>
T SearchTree <T> :: find ( T val) {
int result;
TreeNode <T> * n =root;
while (n) {
result=(*cmp)(val,n->val);
if (result >0) n =n->_rchild;
else if (result <0 ) n=n->_lchild;
else return n->val;
};
return 0;
}
上記コードの使い方
#include "treenode.h"
#include<iostream>
int compare(int x , int y)
{
if (x > y) {return 1;}
else if (x ==y) { return 0 ;}
else {return -1;};
};
void printer(int x) {std::cout <<x<<"\n";};
int main(){
SearchTree <int> jo(compare);jo.insert(9);
jo.insert(2);jo.insert(10);jo.insert(3);
jo.inorder(printer);
std::cout<<jo.find(10)<<std::endl;
return 0;
}
出力
3 9 0
質問
著者はどこで間違っているのですか？または私はそれを間違って実装していますか？
個人的には、以前に挿入された一部のメンバーを検索すると否定が返されるため、挿入関数の動作がおかしいと思います..