/*search_tree class interface
Make a search_tree
If passed a value, (start of game tree) make a node with that value
Also, be able to append nodes to another node:
-Search for the node, if not found return NULL
-If found, add a new successor node containing value
*/
#include "d_node.h"
template <class Entry>
class search_tree {
public:
search_tree(); //constructor
//Post: An empty game tree has been created.
search_tree(Entry x);
bool empty() const;
//Post: A result of true is returned if the binary tree is empty.
//Otherwise, false is returned.
d_node<Entry> *depth_search(Entry value);
//start depth_search at root, pass templated function to do what you want
private:
d_node<Entry> *recursive_depth_search(deque<d_node<Entry> > *&search_queue, Entry value);
d_node<Entry> *root;
};
template <class Entry>
search_tree<Entry>::search_tree()
{
root=new d_node<Entry>;
root=NULL;
if (debug > 0) cout << "\nEmpty tree created.";
}
template <class Entry>
search_tree<Entry>::search_tree(Entry x)
{
root = new d_node<Entry>;
root->data = x;
if (debug > 0) cout << "\nEmpty tree created.";
}
/*Use a queue to implement depth first search of our tree.
- Push the root node on, then call recursive depth_search
*/
template <class Entry>
d_node<Entry> *search_tree<Entry>::depth_search(Entry value)
{
deque<d_node<Entry> > *search_queue;
search_queue = new deque<d_node<Entry> >;
search_queue->push_front(*root);
return recursive_depth_search(search_queue, value);
}
/*Takes a deque of nodes, returns a node if value is found, otherwise, NULL
1. Make temp node called state
2.
*/
template <class Entry>
d_node<Entry> *search_tree<Entry>::recursive_depth_search(deque<d_node<Entry> > *&search_queue, Entry value)
{
d_node<Entry> *state = new d_node<Entry>;
while(!search_queue->empty())
{
state = search_queue->front();
if (state->data == value) return state; //If thats what we want, return that node
else search_queue->pop_front(); //Else dump it, then
//add its successors to queue
deque<d_node<Entry> >::iterator iter = state->leaves.begin();
while ((iter != state->leaves.end()) && (search_queue->push_front(iter))) iter++; //I think this will run both conditions. so it will work on the last node.
//then rerun search
recursive_depth_search(search_queue, value);
}
return null;
}