Don't like ads? PRO users don't see any ads ;-)

CS2370 Prog 8

By: mattfong on Jun 6th, 2011 | syntax: None | size: 10.55 KB | hits: 43 | expires: Never

download | raw | embed | report abuse | print

Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)

//Matthew Fong
//Program 8: maze
//description: create a maze and see if you can get to the end
#ifndef CHARBINARYTREE_H_INCLUDED
#define CHARBINARYTREE_H_INCLUDED
#include <iostream>
using namespace std;
class charBinaryTree
{
private:
struct TreeNode
{
char value; // The value in the node
TreeNode *left; // Pointer to left child node
TreeNode *right; // Pointer to right child node
};
TreeNode *root; // Pointer to the root node
// Private member functions
void insert(TreeNode *&, TreeNode *&);
void destroySubTree(TreeNode *);
void deleteNode(char, TreeNode *&);
void makeDeletion(TreeNode *&);
void displayInOrder(TreeNode *) const;
void displayPreOrder(TreeNode *) const;
void displayPostOrder(TreeNode *) const;
public:
// Constructor
charBinaryTree()
{ root = NULL; }
// Destructor
~charBinaryTree()
{ destroySubTree(root); }
// Binary tree operations
void insertNode(char);
bool searchNode(char);
void remove(char);
void displayInOrder() const
{ displayInOrder(root); }
void displayPreOrder() const
{ displayPreOrder(root); }
void displayPostOrder() const
{ displayPostOrder(root); }
};
#endif // CHARBINARYTREE_H_INCLUDED
#include <iostream>
#include "charBinaryTree.h"
using namespace std;
//*************************************************************
// insert accepts a TreeNode pointer and a pointer to a node. *
// The function inserts the node into the tree pointed to by *
// the TreeNode pointer. This function is called recursively. *
//*************************************************************
void charBinaryTree::insert(TreeNode *&nodePtr, TreeNode *&newNode)
{
if (nodePtr == NULL)
nodePtr = newNode; // Insert the node.
else if (newNode->value < nodePtr->value)
insert(nodePtr->left, newNode); // Search the left branch
else
insert(nodePtr->right, newNode); // Search the right branch
}
//**********************************************************
// insertNode creates a new node to hold num as its value, *
// and passes it to the insert function. *
//**********************************************************
void charBinaryTree::insertNode(char c)
{
TreeNode *newNode; // Pointer to a new node.
// Create a new node and store num in it.
newNode = new TreeNode;
newNode->value = c;
newNode->left = newNode->right = NULL;
// Insert the node.
insert(root, newNode);
}
//***************************************************
// destroySubTree is called by the destructor. It *
// deletes all nodes in the tree. *
//***************************************************
void charBinaryTree::destroySubTree(TreeNode *nodePtr)
{
if (nodePtr)
{
if (nodePtr->left)
destroySubTree(nodePtr->left);
if (nodePtr->right)
destroySubTree(nodePtr->right);
delete nodePtr;
}
}
//***************************************************
// searchNode determines if a value is present in *
// the tree. If so, the function returns true. *
// Otherwise, it returns false. *
//***************************************************
bool charBinaryTree::searchNode(char c)
{
TreeNode *nodePtr = root;
while (nodePtr)
{
if (nodePtr->value == c)
return true;
else if (c < nodePtr->value)
nodePtr = nodePtr->left;
else
nodePtr = nodePtr->right;
}
return false;
}
//**********************************************
// remove calls deleteNode to delete the *
// node whose value member is the same as num. *
//**********************************************
void charBinaryTree::remove(char c)
{
deleteNode(c, root);
}
//********************************************
// deleteNode deletes the node whose value *
// member is the same as num. *
//********************************************
void charBinaryTree::deleteNode(char c, TreeNode *&nodePtr)
{
if (c < nodePtr->value)
deleteNode(c, nodePtr->left);
else if (c > nodePtr->value)
deleteNode(c, nodePtr->right);
else
makeDeletion(nodePtr);
}
//***********************************************************
// makeDeletion takes a reference to a pointer to the node *
// that is to be deleted. The node is removed and the *
// branches of the tree below the node are reattached. *
//***********************************************************
void charBinaryTree::makeDeletion(TreeNode *&nodePtr)
{
// Define a temporary pointer to use in reattaching
// the left subtree.
TreeNode *tempNodePtr;
if (nodePtr == NULL)
cout << "Cannot delete empty node.\n";
else if (nodePtr->right == NULL)
{
tempNodePtr = nodePtr;
nodePtr = nodePtr->left; // Reattach the left child
delete tempNodePtr;
}
else if (nodePtr->left == NULL)
{
tempNodePtr = nodePtr;
nodePtr = nodePtr->right; // Reattach the right child
delete tempNodePtr;
}
// If the node has two children.
else
{
// Move one node the right.
tempNodePtr = nodePtr->right;
// Go to the end left node.
while (tempNodePtr->left)
tempNodePtr = tempNodePtr->left;
// Reattach the left subtree.
tempNodePtr->left = nodePtr->left;
tempNodePtr = nodePtr;
// Reattach the right subtree.
nodePtr = nodePtr->right;
delete tempNodePtr;
}
}
//****************************************************************
// The displayInOrder member function displays the values *
// in the subtree pointed to by nodePtr, via inorder traversal. *
//****************************************************************
void charBinaryTree::displayInOrder(TreeNode *nodePtr) const
{
if (nodePtr)
{
displayInOrder(nodePtr->left);
cout << nodePtr->value << endl;
displayInOrder(nodePtr->right);
}
}
//****************************************************************
// The displayPreOrder member function displays the values *
// in the subtree pointed to by nodePtr, via preorder traversal. *
//****************************************************************
void charBinaryTree::displayPreOrder(TreeNode *nodePtr) const
{
if (nodePtr)
{
cout << nodePtr->value << endl;
displayPreOrder(nodePtr->left);
displayPreOrder(nodePtr->right);
}
}
//****************************************************************
// The displayPostOrder member function displays the values *
// in the subtree pointed to by nodePtr, via postorder traversal.*
//****************************************************************
void charBinaryTree::displayPostOrder(TreeNode *nodePtr) const
{
if (nodePtr)
{
displayPostOrder(nodePtr->left);
displayPostOrder(nodePtr->right);
cout << nodePtr->value << endl;
}
}
#include "charBinaryTree.h"
#include <iostream>
using namespace std;
int main()
{
char path; //User input for the maze
int count = 1; //attempts at solving the maze
charBinaryTree tree;
bool win = false;
//sets the maze up
tree.insertNode('O');
tree.insertNode('K');
tree.insertNode('M');
tree.insertNode('B');
tree.insertNode('W');
tree.insertNode('X');
tree.insertNode('Z');
tree.insertNode('Q');
tree.insertNode('U');
tree.insertNode('V');
tree.insertNode('S');
tree.insertNode('R');
tree.insertNode('T');
while(!win)
{
cout << "You are at O." << endl;
cout << "Which path would you like to take? Left or Right? L/R" << endl;
cin >> path;
if(path == 'R' || path == 'r') //Go to W
{
cout << "You are at W." << endl;
cout << "Which path would you like to take? Left or Right? L/R" << endl;
cin >> path;
if(path == 'R' || path == 'r') //Go to X
{
cout << "You are at X." << endl;
cout << "X leads to Z." << endl;
cout << "Dead end." << endl;
cout << endl;
count++;
}
if(path == 'L' || path == 'l') //Go to Q
{
cout << "You are at Q." << endl;
cout << "Which path would you like to take? Left or Right? L/R" << endl;
cin >> path;
if(path == 'L' || path == 'l') //Go to S
{
cout << "You are at S." << endl;
cout << "Which path would you like to take? Left or Right? L/R" << endl;
cin >> path;
if(path == 'L' || path == 'l') //Go to R
{
cout << "You are at R." << endl;
cout << "You reached the end of the maze." << endl;
win = true;
break;
}
if(path == 'R' || path == 'r') //Go to T
{
cout << "You are at T." << endl;
cout << "Dead end." << endl;
cout << endl;
count++;
}
}
if(path == 'R' || path == 'r') //Go to U
{
count++;
cout << "You are at U." << endl;
cout << "U leads to V." << endl;
cout << "Dead end." << endl;
cout << endl;
}
}
}
if(path == 'L' || path == 'l') //Go to K
{
count++; //Seeing as they already went the wrong way...
cout << "You are at K." << endl;
cout << "Which path would you like to take? Left or Right? L/R" << endl;
cin >> path;
if(path == 'L' || path == 'l')
{
cout << "You are at B." << endl;
cout << "Dead end." << endl;
cout << endl;
}
if(path == 'R' || path == 'r')
{
cout << "You are at M." << endl;
cout << "Dead end." << endl;
cout << endl;
}
}
}
cout << "Times taken to solve the maze: " << count << endl;
return 0;
}

create a new version of this paste RAW Paste Data

//Matthew Fong
//Program 8: maze
//description: create a maze and see if you can get to the end

#ifndef CHARBINARYTREE_H_INCLUDED
#define CHARBINARYTREE_H_INCLUDED

#include <iostream>
using namespace std;

class charBinaryTree
{
private:
   struct TreeNode
   {
      char value;         // The value in the node
      TreeNode *left;    // Pointer to left child node
      TreeNode *right;   // Pointer to right child node
   };

   TreeNode *root;       // Pointer to the root node

   // Private member functions
   void insert(TreeNode *&, TreeNode *&);
   void destroySubTree(TreeNode *);
   void deleteNode(char, TreeNode *&);
   void makeDeletion(TreeNode *&);
   void displayInOrder(TreeNode *) const;
   void displayPreOrder(TreeNode *) const;
   void displayPostOrder(TreeNode *) const;

public:
   // Constructor
   charBinaryTree()
      { root = NULL; }

   // Destructor
   ~charBinaryTree()
      { destroySubTree(root); }

   // Binary tree operations
   void insertNode(char);
   bool searchNode(char);
   void remove(char);

   void displayInOrder() const
      {  displayInOrder(root); }

   void displayPreOrder() const
      {  displayPreOrder(root); }

   void displayPostOrder() const
      {  displayPostOrder(root); }
};

#endif // CHARBINARYTREE_H_INCLUDED

#include <iostream>
#include "charBinaryTree.h"
using namespace std;

//*************************************************************
// insert accepts a TreeNode pointer and a pointer to a node. *
// The function inserts the node into the tree pointed to by  *
// the TreeNode pointer. This function is called recursively. *
//*************************************************************

void charBinaryTree::insert(TreeNode *&nodePtr, TreeNode *&newNode)
{
   if (nodePtr == NULL)
      nodePtr = newNode;                  // Insert the node.
   else if (newNode->value < nodePtr->value)
      insert(nodePtr->left, newNode);     // Search the left branch
   else
      insert(nodePtr->right, newNode);    // Search the right branch
}

//**********************************************************
// insertNode creates a new node to hold num as its value, *
// and passes it to the insert function.                   *
//**********************************************************

void charBinaryTree::insertNode(char c)
{
   TreeNode *newNode;      // Pointer to a new node.

   // Create a new node and store num in it.
   newNode = new TreeNode;
   newNode->value = c;
   newNode->left = newNode->right = NULL;

   // Insert the node.
   insert(root, newNode);
}

//***************************************************
// destroySubTree is called by the destructor. It   *
// deletes all nodes in the tree.                   *
//***************************************************

void charBinaryTree::destroySubTree(TreeNode *nodePtr)
{
   if (nodePtr)
   {
      if (nodePtr->left)
         destroySubTree(nodePtr->left);
      if (nodePtr->right)
         destroySubTree(nodePtr->right);
      delete nodePtr;
   }
}

//***************************************************
// searchNode determines if a value is present in   *
// the tree. If so, the function returns true.      *
// Otherwise, it returns false.                     *
//***************************************************

bool charBinaryTree::searchNode(char c)
{
   TreeNode *nodePtr = root;

   while (nodePtr)
   {
      if (nodePtr->value == c)
         return true;
      else if (c < nodePtr->value)
         nodePtr = nodePtr->left;
      else
         nodePtr = nodePtr->right;
   }
   return false;
}

//**********************************************
// remove calls deleteNode to delete the       *
// node whose value member is the same as num. *
//**********************************************

void charBinaryTree::remove(char c)
{
   deleteNode(c, root);
}


//********************************************
// deleteNode deletes the node whose value   *
// member is the same as num.                *
//********************************************

void charBinaryTree::deleteNode(char c, TreeNode *&nodePtr)
{
   if (c < nodePtr->value)
      deleteNode(c, nodePtr->left);
   else if (c > nodePtr->value)
      deleteNode(c, nodePtr->right);
   else
      makeDeletion(nodePtr);
}


//***********************************************************
// makeDeletion takes a reference to a pointer to the node  *
// that is to be deleted. The node is removed and the       *
// branches of the tree below the node are reattached.      *
//***********************************************************

void charBinaryTree::makeDeletion(TreeNode *&nodePtr)
{
   // Define a temporary pointer to use in reattaching
   // the left subtree.
   TreeNode *tempNodePtr;

   if (nodePtr == NULL)
      cout << "Cannot delete empty node.\n";
   else if (nodePtr->right == NULL)
   {
      tempNodePtr = nodePtr;
      nodePtr = nodePtr->left;   // Reattach the left child
      delete tempNodePtr;
   }
   else if (nodePtr->left == NULL)
   {
      tempNodePtr = nodePtr;
      nodePtr = nodePtr->right;  // Reattach the right child
      delete tempNodePtr;
   }
   // If the node has two children.
   else
   {
      // Move one node the right.
      tempNodePtr = nodePtr->right;
      // Go to the end left node.
      while (tempNodePtr->left)
         tempNodePtr = tempNodePtr->left;
      // Reattach the left subtree.
      tempNodePtr->left = nodePtr->left;
      tempNodePtr = nodePtr;
      // Reattach the right subtree.
      nodePtr = nodePtr->right;
      delete tempNodePtr;
   }
}

//****************************************************************
// The displayInOrder member function displays the values        *
// in the subtree pointed to by nodePtr, via inorder traversal.  *
//****************************************************************

void charBinaryTree::displayInOrder(TreeNode *nodePtr) const
{
   if (nodePtr)
   {
      displayInOrder(nodePtr->left);
      cout << nodePtr->value << endl;
      displayInOrder(nodePtr->right);
   }
}

//****************************************************************
// The displayPreOrder member function displays the values       *
// in the subtree pointed to by nodePtr, via preorder traversal. *
//****************************************************************

void charBinaryTree::displayPreOrder(TreeNode *nodePtr) const
{
   if (nodePtr)
   {
      cout << nodePtr->value << endl;
      displayPreOrder(nodePtr->left);
      displayPreOrder(nodePtr->right);
   }
}

//****************************************************************
// The displayPostOrder member function displays the values      *
// in the subtree pointed to by nodePtr, via postorder traversal.*
//****************************************************************

void charBinaryTree::displayPostOrder(TreeNode *nodePtr) const
{
   if (nodePtr)
   {
      displayPostOrder(nodePtr->left);
      displayPostOrder(nodePtr->right);
      cout << nodePtr->value << endl;
   }
}

#include "charBinaryTree.h"
#include <iostream>
using namespace std;

int main()
{
    char path; //User input for the maze
    int count = 1; //attempts at solving the maze
    charBinaryTree tree;
    bool win = false;

    //sets the maze up
    tree.insertNode('O');
    tree.insertNode('K');
    tree.insertNode('M');
    tree.insertNode('B');
    tree.insertNode('W');
    tree.insertNode('X');
    tree.insertNode('Z');
    tree.insertNode('Q');
    tree.insertNode('U');
    tree.insertNode('V');
    tree.insertNode('S');
    tree.insertNode('R');
    tree.insertNode('T');

    while(!win)
    {
        cout << "You are at O." << endl;
        cout << "Which path would you like to take? Left or Right? L/R" << endl;
        cin >> path;

        if(path == 'R' || path == 'r') //Go to W
        {
            cout << "You are at W." << endl;
            cout << "Which path would you like to take? Left or Right? L/R" << endl;
            cin >> path;

            if(path == 'R' || path == 'r') //Go to X
            {
                cout << "You are at X." << endl;
                cout << "X leads to Z." << endl;
                cout << "Dead end." << endl;
                cout << endl;
                count++;
            }

            if(path == 'L' || path == 'l') //Go to Q
            {
                cout << "You are at Q." << endl;
                cout << "Which path would you like to take? Left or Right? L/R" << endl;
                cin >> path;

                if(path == 'L' || path == 'l') //Go to S
                {
                    cout << "You are at S." << endl;
                    cout << "Which path would you like to take? Left or Right? L/R" << endl;
                    cin >> path;

                    if(path == 'L' || path == 'l') //Go to R
                    {
                        cout << "You are at R." << endl;
                        cout << "You reached the end of the maze." << endl;
                        win = true;
                        break;
                    }

                    if(path == 'R' || path == 'r') //Go to T
                    {
                        cout << "You are at T." << endl;
                        cout << "Dead end." << endl;
                        cout << endl;
                        count++;
                    }
                }

                if(path == 'R' || path == 'r') //Go to U
                {
                    count++;
                    cout << "You are at U." << endl;
                    cout << "U leads to V." << endl;
                    cout << "Dead end." << endl;
                    cout << endl;
                }
            }
        }

        if(path == 'L' || path == 'l') //Go to K
        {
            count++; //Seeing as they already went the wrong way...
            cout << "You are at K." << endl;
            cout << "Which path would you like to take? Left or Right? L/R" << endl;
            cin >> path;

            if(path == 'L' || path == 'l')
            {
                cout << "You are at B." << endl;
                cout << "Dead end." << endl;
                cout << endl;
            }

            if(path == 'R' || path == 'r')
            {
                cout << "You are at M." << endl;
                cout << "Dead end." << endl;
                cout << endl;
            }
        }
    }

    cout << "Times taken to solve the maze: " << count << endl;
    return 0;
}

Pastebin.com Tools & Applications

iPhone/iPad

Windows

Firefox

Chrome

WebOS

Android

Mac

Opera

Click.to

UNIX

WinPhone