練習するために、私が再び慣れ親しんでいるトピックの1つは木です。深さ優先探索と幅優先探索の違いは、アルゴリズムをサポートするデータ構造の選択のみが異なることです。
テンプレートを使用してスタック（DFS）またはキュー（BFS）のいずれかにフィードする一般的なツリー検索を作成できると思いました。stack追加メンバーとqueue削除メンバーの名前が同じであるという点で十分です。残念ながら、アクセス関数は一度呼び出さtopれfront、もう一方は呼び出されます。このため、私は自分が望む場所に完全に到着しませんでした。私はそのラムダなしでそれを行うことができませんでした：
template<typename T, typename D, typename G>
bool ts(Tree<T> const & tree, T const value, D & ds, G getter)
{
if (empty(tree))
{
return false;
}
ds.push(tree.Root);
while (!ds.empty())
{
auto const current = getter();
ds.pop();
if (current->Value == value)
{
return true;
}
if (current->Left)
{
ds.push(current->Left);
}
if (current->Right)
{
ds.push(current->Right);
}
}
return false;
}
template<typename T>
bool dfs(Tree<T> const & tree, T const value)
{
stack<typename Tree<T>::Node const * const> ds;
return ts(tree, value, ds, [&ds](){ return ds.top(); });
}
template<typename T>
bool bfs(Tree<T> const & tree, T const value)
{
queue<typename Tree<T>::Node const * const> ds;
return ts(tree, value, ds, [&ds](){ return ds.front(); });
}
私は、それぞれのアクセス機能を提供するためにmem_fun（または）を使用できるはずですが。mem_fun_ref私は試した
template<typename T>
bool dfs(Tree<T> const & tree, T const value)
{
typedef stack<typename Tree<T>::Node const * const> DataStructure;
return ts(tree, value, DataStructure(), mem_fun(&DataStructure::top));
}
しかし、コンパイラは（バージョンconstと非constバージョンの間の）あいまいさについて文句を言います。
そこで私はインターネットを検索し、テンプレートタイプを明示的に提供する必要があることを学びました。
template<typename T>
bool dfs(Tree<T> const & tree, T const value)
{
typedef stack<typename Tree<T>::Node const * const> DataStructure;
return ts(tree, value, DataStructure(), mem_fun</*???*/>(&DataStructure::top));
}
悲しいことに、 ???の多くの可能性のどれも コンパイラを満足させることができたと思います。
誰かが私にヒントを与えることができますか？
更新：ここに完全な実例があります（NO_LAMBDAを定義する場合を除く）：
#include <iostream>
#include <stack>
#include <functional>
using namespace std;
template<typename T>
struct Tree
{
struct Node
{
T Value;
Node * Left;
Node * Right;
Node(T value) : Value(value), Left(nullptr), Right(nullptr) {}
virtual ~Node()
{
if (Left) delete Left;
if (Right) delete Right;
}
};
Node * Root;
Tree() : Root(nullptr) {}
virtual ~Tree() { if (Root) delete Root; }
};
template<typename T> void insert(typename Tree<T>::Node * node, T const & value)
{
typename Tree<T>::Node ** selected = &(value < node->Value ? node->Left : node->Right);
if (*selected)
insert(*selected, value);
else
*selected = new typename Tree<T>::Node(value);
}
template<typename T> void insert(Tree<T> & tree, T value)
{
if (!tree.Root)
tree.Root = new typename Tree<T>::Node(value);
else
insert(tree.Root, value);
}
template<typename T, typename D, typename G>
bool ts(Tree<T> const & tree, T const value, D & ds, G getter)
{
if (!tree.Root) return false;
ds.push(tree.Root);
while (!ds.empty())
{
auto const current = getter();
ds.pop();
if (current->Value == value) return true;
if (current->Left) ds.push(current->Left);
if (current->Right) ds.push(current->Right);
}
return false;
}
template<typename T>
bool dfs(Tree<T> const & tree, T const value)
{
typedef typename Tree<T>::Node const * DataStructureContent;
typedef stack<DataStructureContent> DataStructure;
#ifdef NO_LAMBDA // With this defined, it breaks.
return ts(tree, value, DataStructure(),
mem_fun(static_cast<DataStructureContent (DataStructure::*)() const>(&DataStructure::top)));
#else // This works.
DataStructure ds;
return ts(tree, value, ds, [&ds] () { return ds.top(); });
#endif
}
int main()
{
Tree<int> tree;
insert(tree, 5);
insert(tree, 2); insert(tree, 1); insert(tree, 3);
insert(tree, 7); insert(tree, 6); insert(tree, 9);
cout << "DFS(7) -> " << dfs(tree, 7) << endl;
cout << "DFS(8) -> " << dfs(tree, 8) << endl;
return 0;
}