二分探索木で最大値を返したい

Question

C++初心者です。
二分探索木の中の最大値を求めるコードを作りたいのですが、コンパイル中にcollect2というエラーが発生します。原因と解決方法がわからないのでご教授をお願いしたいと思います。
コードはファイルの一部をコピペしてきたものなので、余計な定義などが入っているかもしれませんが、気にしないでください。
よろしくお願いします。

エラーメッセージ

/tmp/ccBj1FvS.o: 関数 `main' 内:
bstmax.cpp:(.text+0x2da): `BinarySearchTree::findLargest() const' に対する定義されていない参照です
collect2: エラー: ld はステータス 1 で終了しました

ソースコード

#include <iostream> 
#include <vector> 
#include <cassert>
using namespace std;

// 二分木の頂点のクラス
template <class T> class BinNode {
private:
    T key; // 各頂点のキー
    BinNode<T> *left, *right; // 左子・右子頂点
public:
    // コンストラクタでメンバを初期化
    BinNode(T d, BinNode<T> *l=NULL, BinNode<T> *r=NULL) {
        key = d; left =l; right=r;
    }
    // BinarySearchTree のメンバ関数からこのクラス BinNode のプライベートメンバを操作可能にする
    friend class BinarySearchTree; 
};

// 二分探索木のクラス
class BinarySearchTree { 
    BinNode <int>* root; // 根頂点
public:
    BinarySearchTree( ) { root = NULL; };  // 初期状態 
    ~BinarySearchTree( ) { makeEmpty( root ); }; // デストラクタ
    bool insert( int data ) { return insert( data, root ); };  
    void show() const { show( root ); cout << endl; };
    int findLargest() const; // 
private:
    bool insert( int data, BinNode<int>* & tree); 
    void makeEmpty( BinNode<int>* tree );
    void show( BinNode<int>* tree ) const;
    int findLargest( BinNode<int>* tree ) const;
   };

void BinarySearchTree::makeEmpty( BinNode<int>* tree ) { 
    if( tree !=NULL ) {
        makeEmpty( tree->left ); 
        makeEmpty( tree->right ); 
        delete tree;
    }
}

bool BinarySearchTree::insert( int data, BinNode<int>* & tree ) {
    if (tree == NULL) { 
        tree = new BinNode<int> (data); 
        return true;
    }
    else if (tree->key == data)  
        return false;
    else if (tree->key > data) 
        return insert(data, tree->left); 
    else 
        return insert(data, tree->right);
}
void BinarySearchTree::show( BinNode<int>* tree ) const {
    if (tree != NULL) {
        show( tree->left );
        cout << tree->key << ". ";
        show( tree->right );
    }
}

// 二分木全体の最大値を求める関数
int BinarySearchTree::findLargest( BinNode<int>* tree ) const { 
  if(tree==NULL) return false;
  else{
    int max = tree->key;
    int lmax = findLargest(tree->left);
    int rmax = findLargest(tree->right);
    if (lmax>rmax) max=lmax;
    else max=rmax;
  return max;
  }
}

int main(void) {
    BinarySearchTree bst; // 二分探索木   
    int data; // 現在の読み込みデータ

    while ( cin >> data )  
        bst.insert(data);
    bst.show();

    cout << "最大値は " <<  bst.findLargest() << endl;
   
    return 0;
} 

Answer 1

× int findLargest() const;
○ int findLargest() const { return findLargest(root); }

[ついでに]

× else max=rmax;
○ if (rmax>max) max=rmax;
※ max, rmax, lmax の最大値を求めるんだから。

[おまけ]

int BinarySearchTree::findLargest( BinNode<int>* tree ) const { 
　if(tree==NULL) return false;

treeが空のとき、false(=0)を返す。
空のときは最大値は存在しないのだからなにも返せないはず。
たとえば range_error例外をthrowせんならんのでは?
※ int* を返すことにすれば、NULL(nullptr)で"存在しない"ことを表現できるけど。

...で、僕ならこう書く:

#include <iostream> 

// 二分探索木のクラス
template<typename T>
class BinarySearchTree { 
    struct BinNode {
      T key; // 各頂点のキー
      BinNode* left;
      BinNode* right;
      BinNode(T d, BinNode *l=nullptr, BinNode *r=nullptr) : key(d), left(l), right(r) {}
    };
    BinNode* root; // 根頂点
public:
    BinarySearchTree( ) { root = nullptr; };  // 初期状態 
    ~BinarySearchTree( ) { makeEmpty( root ); }; // デストラクタ
    bool insert( const T& data ) { return insert( data, root ); };  
    void show() const { show( root ); std::cout << std::endl; };
    bool findLargest(T& result) const { return findLargest(root, result); }
private:
    bool insert( const T& data, BinNode* & tree); 
    void makeEmpty( BinNode* tree );
    void show( BinNode* tree ) const;
    bool findLargest( BinNode* tree, T& result) const;
};

template<typename T>
void BinarySearchTree<T>::makeEmpty( BinarySearchTree<T>::BinNode* tree ) { 
    if( tree !=nullptr ) {
        makeEmpty( tree->left ); 
        makeEmpty( tree->right ); 
        delete tree;
    }
}

template<typename T>
bool BinarySearchTree<T>::insert( const T& data, BinarySearchTree<T>::BinNode* & tree ) {
    if (tree == nullptr) { 
        tree = new BinNode(data); 
        return true;
    }
    else if (tree->key == data)  
        return false;
    else if (tree->key > data) 
        return insert(data, tree->left); 
    else 
        return insert(data, tree->right);
}

template<typename T>
void BinarySearchTree<T>::show( BinarySearchTree<T>::BinNode* tree ) const {
    if (tree != nullptr) {
        show( tree->left );
        std::cout << tree->key << ". ";
        show( tree->right );
    }
}

// 二分木全体の最大値を求める関数
template<typename T>
bool BinarySearchTree<T>::findLargest( BinarySearchTree<T>::BinNode* tree, T& result) const { 
  if(tree==nullptr) return false;
  else{
    result = tree->key;
    T cmax;
    if ( findLargest(tree->left,  cmax) && cmax > result ) result = cmax;
    if ( findLargest(tree->right, cmax) && cmax > result ) result = cmax;
    return true;
  }
}

int main() {
    BinarySearchTree<int> bst; // 二分探索木   

    for ( int data : { 1, 3, 5, 7, 9, 0, 2, 4, 6, 8} ) {
        std::cout << "insert: " << data << std::endl;
        bst.insert(data);
        bst.show();
        int max;
        if ( bst.findLargest(max) ) {
          std::cout << "最大値は " << max << std::endl << std::endl;
        }
    }
} 

Comments

[Ryuji_T]

早速の回答ありがとうございます。episteme様の回答自体は理解できたのですが、「関数の宣言を変更せずに」このエラーを取り除くことは可能でしょうか。先生からそのような制限がかかっているものでして…

[episteme]

できますよもちろん。

[Ryuji_T]

それはどういう風に書き直せばいいのでしょうか

[episteme]

関数の宣言を変更せずに、コレ↓を追加。

int BinarySearchTree::findLargest() const {
return findLargest(root);
}

[Ryuji_T]

無事エラーがなくなりました。ありがとうございました。

Answer 2

エラーメッセージのとおりです。BinarySearchTree::findLargest() const（引数なしのオーバーロード）の定義がありません。

Comments

[Ryuji_T]

ありがとうございます。