At the forefront of Artificial Intelligence

Search Tree Project

Create a program that allows you to create a binary tree and then search it for a given data item. It should allow the user to choose whether to use a breadth-first or depth-first algorithm and will display the nodes that the algorithm had on the OPEN and CLOSED lists. If you do not know how to implement these algorithms, read the Generation5 essay.

Guidelines

Here is some pseudo-code (well, C++!) that might be used to set up a data tree:


Tree tree;
TreeNode node1, node2, node3;

// AddNode([Parent Node], [Node Data])
// Returns: a TreeNode that represents the new node

node1 = tree.AddNode(NULL,  'A');
node2 = tree.AddNode(node1, 'B');
        tree.AddNode(node1, 'C');
        tree.AddNode(node2, 'D');
node3 = tree.AddNode(node2, 'E');
        tree.AddNode(node3, 'F');
        tree.AddNode(node3, 'G');

This code would set up the tree shown to the right (disregard the arrows).

Further Exploration

This project is relatively trivial, since it doesn't do very much that is interesting. You might want to try and implement a hybrid algorithm: a depth-first algorithm that has a depth-threshold. In the first iteration it will only check perhaps 5 levels deep, and if the goal state is not found the depth is incremented and the search it tried again. This may sound inefficient, but in some cases it is a better option than either depth or breadth-first.

Solutions

searchtree.zip (25Kb)

Solution submitted by James Matthews. Simple solution that pretty much follows the standard code above. A mode variable will set the code to search either breadth-first and depth-first.

Submitted: 24/05/2001

Article Toolbar

BibTeX entry