#include <conio.h>
#include <stdio.h>
int main()
{
int a[10];
for(int x=0; x<10; x++)
{
scanf("%d",&a[x]);
}
printf("\n\nODD EVEN\n");
for( int i = 0; i < 10; i++ )
{
if(a[i]%2==0)
{
printf("\t%d\n",a[i]);
}
if(a[i]%2==1)
{
printf("%d",a[i]);
}
}
getch();
}
Binary Tree data structure.
//******************************************************************//
// Demonstration of simple binary tree implementation
//******************************************************************//
#include <iostream>
#include <cstdlib> // For exit()
#include <vector> // For storing characters
#include <iomanip> // For setw(), setfill()
#include <string>
using namespace std;
//******************************************************************//
// Tree class. //
//******************************************************************//
class Tree
{
public:
Tree()
{ root = NULL; }
~Tree()
{ destroySubTree(root); }
void insertNode(char);
bool searchNode(char);
void remove(char);
void displayInOrder() const
{ displayInOrder(root); }
void displayPreOrder() const
{ displayPreOrder(root); }
void displayPostOrder() const
{ displayPostOrder(root); }
void FindExitNode(char item)
{ FindExitNode(root, item); }
void TracePath();
private:
struct TreeNode
{
char item;
TreeNode *left;
TreeNode *right;
};
TreeNode *root;
static int tries;
vector<char> itemPlaceholder;
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;
void FindExitNode(TreeNode *, char);
};
// Holds the number of attempts in finding the target character.
int Tree::tries = 0;
//******************************************************************//
// insertNode creates a new node to hold item as its value, and //
// passes it to the insert function. //
//******************************************************************//
void Tree::insertNode(char item)
{
TreeNode *newNode;
newNode = new TreeNode;
newNode->item = item;
newNode->left = newNode->right = NULL;
insert(root, newNode);
}
//******************************************************************//
// 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 Tree::insert(TreeNode *&nodePtr, TreeNode *&newNode)
{
if(nodePtr == NULL)
nodePtr = newNode;
else if(newNode->item < nodePtr->item)
insert(nodePtr->left, newNode);
else
insert(nodePtr->right, newNode);
}
//******************************************************************//
// destroySubTree is called by the destructor. It deletes all nodes //
// in the tree. //
//******************************************************************//
void Tree::destroySubTree(TreeNode *nodePtr)
{
if(nodePtr)
{
if(nodePtr->left)
destroySubTree(nodePtr->left);
if(nodePtr->right)
destroySubTree(nodePtr->right);
delete nodePtr;
}
}
//******************************************************************//
// The displayInOrder member function display the values in the //
// subtree pointed to by nodePtr, via inorder traversal. //
//******************************************************************//
void Tree::displayInOrder(TreeNode *nodePtr) const
{
if(nodePtr)
{
displayInOrder(nodePtr->left);
cout << nodePtr->item << endl;
displayInOrder(nodePtr->right);
}
}
//******************************************************************//
// The displayPreOrder member function displays the values in the //
// subtree pointed to by nodePtr, via preorder traversal. //
//******************************************************************//
void Tree::displayPreOrder(TreeNode *nodePtr) const
{
if(nodePtr)
{
cout << nodePtr->item << 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 Tree::displayPostOrder(TreeNode *nodePtr) const
{
if(nodePtr)
{
displayPostOrder(nodePtr->left);
displayPostOrder(nodePtr->right);
cout << nodePtr->item << endl;
}
}
//******************************************************************//
// searchNode determines whether a value is present in the tree. //
// If so, the function returns true. Otherwise, it returns false. //
//******************************************************************//
bool Tree::searchNode(char item)
{
TreeNode *nodePtr = root;
while(nodePtr)
{
if(nodePtr->item == item)
return true;
else if(item < nodePtr->item)
nodePtr = nodePtr->left;
else
nodePtr = nodePtr->right;
}
return false;
}
//******************************************************************//
// remove calls deleteNode to delete the node whose item member is //
// the same as item. //
//******************************************************************//
void Tree::remove(char item)
{
deleteNode(item, root);
}
//******************************************************************//
// deleteNode deletes the node whose value member is the same as //
// item. //
//******************************************************************//
void Tree::deleteNode(char item, TreeNode *&nodePtr)
{
if(item < nodePtr->item)
deleteNode(item, nodePtr->left);
else if(item > nodePtr->item)
deleteNode(item, 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 Tree::makeDeletion(TreeNode *&nodePtr)
{
TreeNode *tempNodePtr;
if(nodePtr == NULL)
cout << "Cannot delete an empty node.\n";
else if(nodePtr->right == NULL)
{
tempNodePtr = nodePtr;
nodePtr = nodePtr->left;
delete tempNodePtr;
}
else if(nodePtr->left == NULL)
{
tempNodePtr = nodePtr;
nodePtr = nodePtr->right;
delete tempNodePtr;
}
else
{
tempNodePtr = nodePtr->right;
while(tempNodePtr->left)
tempNodePtr = tempNodePtr->left;
tempNodePtr->left = nodePtr->left;
tempNodePtr = nodePtr;
nodePtr = nodePtr->right;
delete tempNodePtr;
}
}
//******************************************************************//
// Function: Traverses the tree based on user selected direction. //
// Compare the current node with the current item. //
// Pre-condition: A valid character item must be in the tree. //
// Post-condition: A printout is sent to the output stream. //
//******************************************************************//
void Tree::FindExitNode(TreeNode *nodePtr, char item)
{
if(nodePtr)
{
itemPlaceholder.push_back(nodePtr->item);
if(nodePtr->item == item)
{
itemPlaceholder.push_back(nodePtr->item);
cout << endl << "Tracing your path..." << endl << endl;
TracePath();
cout << endl << "Congratulations! " << "After " << ++tries;
(tries > 1) ? cout << " tries, " : cout << " try, ";
cout << "you have found the exit to the maze!" << endl;
itemPlaceholder.clear();
exit(EXIT_SUCCESS);
}
cout << "Select turn (left/right): ";
string answer;
getline(cin, answer);
if(answer == "left" || answer == "LEFT" || answer == "l" || answer == "L")
{
itemPlaceholder.push_back('/');
FindExitNode(nodePtr->left, item);
}
else if(answer == "right" || answer == "RIGHT" || answer == "r" || answer == "R")
{
itemPlaceholder.push_back('\\');
FindExitNode(nodePtr->right, item);
}
else
{
cout << endl << "Invalid direction." << endl;
cout << "Going back to the beginning of maze..." << endl << endl;
while(!itemPlaceholder.empty())
itemPlaceholder.pop_back();
}
}
else
{
cout << endl << "Tracing your path..." << endl << endl;
TracePath();
cout << endl << "You've reached a dead end." << endl;
cout << "Going back to the beginning of maze..." << endl << endl;
tries++;
}
}
//******************************************************************//
// Function: Traces the path the player has visited. //
// Post-condition: The visited path is sent to the output stream. //
//******************************************************************//
void Tree::TracePath()
{
int x, currentPosition;
x = currentPosition = 15;
for(unsigned int i=0; i<itemPlaceholder.size()-1; i++)
{
if(itemPlaceholder[i] == '/')
{
currentPosition -= 1;
for(int j=0; j<currentPosition; j++)
cout << " ";
cout << "/" << endl;
x=currentPosition-1;
}
else if(itemPlaceholder[i] == '\\')
{
currentPosition += 1;
for(int j=0; j<currentPosition; j++)
cout << " ";
cout << "\\" << endl;
x=currentPosition+1;
}
else // letter
{
for(int j=0; j<x; j++)
cout << " ";
cout << itemPlaceholder[i] << endl;
currentPosition = x;
}
}
itemPlaceholder.clear();
}
//******************************************************************//
// Show introduction to game. //
//******************************************************************//
void ShowBanner()
{
cout << left << setfill('-') << setw(79) << "-" << endl;
cout << left << setfill(' ') << setw(20) << " ";
cout << "WELCOME TO THE BINARY TREE MAZE GAME!" << endl;
cout << left << setfill('-') << setw(79) << "-" << endl << endl;
}
//******************************************************************//
// Main function //
//******************************************************************//
int main()
{
Tree *tree = new Tree();
// Create the tree structure
tree->insertNode('O');
tree->insertNode('K');
tree->insertNode('W');
tree->insertNode('B');
tree->insertNode('M');
tree->insertNode('S');
tree->insertNode('X');
tree->insertNode('Q');
tree->insertNode('U');
tree->insertNode('Z');
tree->insertNode('R');
tree->insertNode('T');
tree->insertNode('V');
ShowBanner();
// Begin the game
while(true)
{
// Look for character 'R'
tree->FindExitNode('R');
}
return 0;
}
// Demonstration of simple binary tree implementation
//******************************************************************//
#include <iostream>
#include <cstdlib> // For exit()
#include <vector> // For storing characters
#include <iomanip> // For setw(), setfill()
#include <string>
using namespace std;
//******************************************************************//
// Tree class. //
//******************************************************************//
class Tree
{
public:
Tree()
{ root = NULL; }
~Tree()
{ destroySubTree(root); }
void insertNode(char);
bool searchNode(char);
void remove(char);
void displayInOrder() const
{ displayInOrder(root); }
void displayPreOrder() const
{ displayPreOrder(root); }
void displayPostOrder() const
{ displayPostOrder(root); }
void FindExitNode(char item)
{ FindExitNode(root, item); }
void TracePath();
private:
struct TreeNode
{
char item;
TreeNode *left;
TreeNode *right;
};
TreeNode *root;
static int tries;
vector<char> itemPlaceholder;
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;
void FindExitNode(TreeNode *, char);
};
// Holds the number of attempts in finding the target character.
int Tree::tries = 0;
//******************************************************************//
// insertNode creates a new node to hold item as its value, and //
// passes it to the insert function. //
//******************************************************************//
void Tree::insertNode(char item)
{
TreeNode *newNode;
newNode = new TreeNode;
newNode->item = item;
newNode->left = newNode->right = NULL;
insert(root, newNode);
}
//******************************************************************//
// 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 Tree::insert(TreeNode *&nodePtr, TreeNode *&newNode)
{
if(nodePtr == NULL)
nodePtr = newNode;
else if(newNode->item < nodePtr->item)
insert(nodePtr->left, newNode);
else
insert(nodePtr->right, newNode);
}
//******************************************************************//
// destroySubTree is called by the destructor. It deletes all nodes //
// in the tree. //
//******************************************************************//
void Tree::destroySubTree(TreeNode *nodePtr)
{
if(nodePtr)
{
if(nodePtr->left)
destroySubTree(nodePtr->left);
if(nodePtr->right)
destroySubTree(nodePtr->right);
delete nodePtr;
}
}
//******************************************************************//
// The displayInOrder member function display the values in the //
// subtree pointed to by nodePtr, via inorder traversal. //
//******************************************************************//
void Tree::displayInOrder(TreeNode *nodePtr) const
{
if(nodePtr)
{
displayInOrder(nodePtr->left);
cout << nodePtr->item << endl;
displayInOrder(nodePtr->right);
}
}
//******************************************************************//
// The displayPreOrder member function displays the values in the //
// subtree pointed to by nodePtr, via preorder traversal. //
//******************************************************************//
void Tree::displayPreOrder(TreeNode *nodePtr) const
{
if(nodePtr)
{
cout << nodePtr->item << 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 Tree::displayPostOrder(TreeNode *nodePtr) const
{
if(nodePtr)
{
displayPostOrder(nodePtr->left);
displayPostOrder(nodePtr->right);
cout << nodePtr->item << endl;
}
}
//******************************************************************//
// searchNode determines whether a value is present in the tree. //
// If so, the function returns true. Otherwise, it returns false. //
//******************************************************************//
bool Tree::searchNode(char item)
{
TreeNode *nodePtr = root;
while(nodePtr)
{
if(nodePtr->item == item)
return true;
else if(item < nodePtr->item)
nodePtr = nodePtr->left;
else
nodePtr = nodePtr->right;
}
return false;
}
//******************************************************************//
// remove calls deleteNode to delete the node whose item member is //
// the same as item. //
//******************************************************************//
void Tree::remove(char item)
{
deleteNode(item, root);
}
//******************************************************************//
// deleteNode deletes the node whose value member is the same as //
// item. //
//******************************************************************//
void Tree::deleteNode(char item, TreeNode *&nodePtr)
{
if(item < nodePtr->item)
deleteNode(item, nodePtr->left);
else if(item > nodePtr->item)
deleteNode(item, 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 Tree::makeDeletion(TreeNode *&nodePtr)
{
TreeNode *tempNodePtr;
if(nodePtr == NULL)
cout << "Cannot delete an empty node.\n";
else if(nodePtr->right == NULL)
{
tempNodePtr = nodePtr;
nodePtr = nodePtr->left;
delete tempNodePtr;
}
else if(nodePtr->left == NULL)
{
tempNodePtr = nodePtr;
nodePtr = nodePtr->right;
delete tempNodePtr;
}
else
{
tempNodePtr = nodePtr->right;
while(tempNodePtr->left)
tempNodePtr = tempNodePtr->left;
tempNodePtr->left = nodePtr->left;
tempNodePtr = nodePtr;
nodePtr = nodePtr->right;
delete tempNodePtr;
}
}
//******************************************************************//
// Function: Traverses the tree based on user selected direction. //
// Compare the current node with the current item. //
// Pre-condition: A valid character item must be in the tree. //
// Post-condition: A printout is sent to the output stream. //
//******************************************************************//
void Tree::FindExitNode(TreeNode *nodePtr, char item)
{
if(nodePtr)
{
itemPlaceholder.push_back(nodePtr->item);
if(nodePtr->item == item)
{
itemPlaceholder.push_back(nodePtr->item);
cout << endl << "Tracing your path..." << endl << endl;
TracePath();
cout << endl << "Congratulations! " << "After " << ++tries;
(tries > 1) ? cout << " tries, " : cout << " try, ";
cout << "you have found the exit to the maze!" << endl;
itemPlaceholder.clear();
exit(EXIT_SUCCESS);
}
cout << "Select turn (left/right): ";
string answer;
getline(cin, answer);
if(answer == "left" || answer == "LEFT" || answer == "l" || answer == "L")
{
itemPlaceholder.push_back('/');
FindExitNode(nodePtr->left, item);
}
else if(answer == "right" || answer == "RIGHT" || answer == "r" || answer == "R")
{
itemPlaceholder.push_back('\\');
FindExitNode(nodePtr->right, item);
}
else
{
cout << endl << "Invalid direction." << endl;
cout << "Going back to the beginning of maze..." << endl << endl;
while(!itemPlaceholder.empty())
itemPlaceholder.pop_back();
}
}
else
{
cout << endl << "Tracing your path..." << endl << endl;
TracePath();
cout << endl << "You've reached a dead end." << endl;
cout << "Going back to the beginning of maze..." << endl << endl;
tries++;
}
}
//******************************************************************//
// Function: Traces the path the player has visited. //
// Post-condition: The visited path is sent to the output stream. //
//******************************************************************//
void Tree::TracePath()
{
int x, currentPosition;
x = currentPosition = 15;
for(unsigned int i=0; i<itemPlaceholder.size()-1; i++)
{
if(itemPlaceholder[i] == '/')
{
currentPosition -= 1;
for(int j=0; j<currentPosition; j++)
cout << " ";
cout << "/" << endl;
x=currentPosition-1;
}
else if(itemPlaceholder[i] == '\\')
{
currentPosition += 1;
for(int j=0; j<currentPosition; j++)
cout << " ";
cout << "\\" << endl;
x=currentPosition+1;
}
else // letter
{
for(int j=0; j<x; j++)
cout << " ";
cout << itemPlaceholder[i] << endl;
currentPosition = x;
}
}
itemPlaceholder.clear();
}
//******************************************************************//
// Show introduction to game. //
//******************************************************************//
void ShowBanner()
{
cout << left << setfill('-') << setw(79) << "-" << endl;
cout << left << setfill(' ') << setw(20) << " ";
cout << "WELCOME TO THE BINARY TREE MAZE GAME!" << endl;
cout << left << setfill('-') << setw(79) << "-" << endl << endl;
}
//******************************************************************//
// Main function //
//******************************************************************//
int main()
{
Tree *tree = new Tree();
// Create the tree structure
tree->insertNode('O');
tree->insertNode('K');
tree->insertNode('W');
tree->insertNode('B');
tree->insertNode('M');
tree->insertNode('S');
tree->insertNode('X');
tree->insertNode('Q');
tree->insertNode('U');
tree->insertNode('Z');
tree->insertNode('R');
tree->insertNode('T');
tree->insertNode('V');
ShowBanner();
// Begin the game
while(true)
{
// Look for character 'R'
tree->FindExitNode('R');
}
return 0;
}
Subscribe to:
Posts (Atom)