#include <cstddef>
#include <cassert>
typedef char* TreeType;
typedef void(*FunctionType)(TreeType& anItem);
class TreeNode
{
private:
TreeNode(){};
TreeNode(const TreeType& node, TreeNode *left=NULL, TreeNode *right=NULL):
item(node), lftPtr(left), rtPtr(right){}
TreeType item;
TreeNode *ancestor;//pointer to ancestor
TreeNode *lftPtr;//pointer to left child
TreeNode *rtPtr;//pointer to right child
friend class BinaryTree;//allow BinaryTree access to these pointers
};
class BinaryTree
{
public:
//basic tree functions
BinaryTree();
BinaryTree(const TreeType& rootItem);
BinaryTree(const BinaryTree& tree);
virtual ~BinaryTree();
virtual bool isEmpty()const;
virtual TreeType getRootData()const;
virtual void setRootData(const TreeType& newItem);
virtual void attachLeft(const TreeType& newItem);
virtual void attachRight(const TreeType& newItem);
virtual void preTrav(FunctionType visit);
virtual void inTrav(FunctionType visit);
virtual void postTrav(FunctionType visit);
virtual BinaryTree& operator=(const BinaryTree& rhs);
//iterator functions
virtual void moveLeft();
virtual void moveRight();
virtual void moveBack();
virtual void getTravData(TreeType& item);
virtual void setTravData(TreeType& item);
virtual void moveRoot();
virtual bool lftNull();
virtual bool rtNull();
protected:
//constructors and internal functions
BinaryTree(TreeNode *ptr);
void CopyTree(TreeNode *treePtr, TreeNode *& newTreePtr)const;
void DestroyTree(TreeNode *& treePtr);
TreeNode *rootPtr()const;
void setRootPtr(TreeNode *newRoot);
void getChildPtrs(TreeNode *nodePtr, TreeNode *& lftPtr, TreeNode *& rtPtr)const;
void setChildPtrs(TreeNode *nodePtr, TreeNode *& lftPtr, TreeNode *& rtPtr);
void preorder(TreeNode *treePtr, FunctionType visit);
void inorder(TreeNode *treePtr, FunctionType visit);
void postorder(TreeNode *treePtr, FunctionType visit);
private:
TreeNode *root;//root pointer
TreeNode *trav;//iterator
 
};
/***********************************************
begin class implementation of BinaryTree class
***********************************************/
/***********************************************
default constructor
***********************************************/
BinaryTree::BinaryTree(): root(NULL),trav(NULL){}
/***********************************************
constructor for setting the root item 
***********************************************/
BinaryTree::BinaryTree(const TreeType& rootItem)
{
root = new TreeNode(rootItem, NULL, NULL);
assert(root != NULL);
trav = root;
}
/***********************************************
copy constructor
***********************************************/
BinaryTree::BinaryTree(const BinaryTree& tree)
{
CopyTree(tree.root, root);
}
/***********************************************
constructor for basing this tree on another
***********************************************/
BinaryTree::BinaryTree(TreeNode *ptr):root(ptr)
{
trav = root;
}
/***********************************************
destructor
***********************************************/
BinaryTree::~BinaryTree()
{
DestroyTree(root);
}
/***********************************************
checks for empty tree state
***********************************************/
bool BinaryTree::isEmpty()const
{
return (root==NULL);
}
/***********************************************
returns root data item
***********************************************/
TreeType BinaryTree::getRootData()const
{
if(!isEmpty())
{
return root->item;
}
else
{
return 0;
}
}
/***********************************************
sets root data
***********************************************/
void BinaryTree::setRootData(const TreeType& newItem)
{
if(!isEmpty())
{
root->item = newItem;
}
else
{
root = new TreeNode(newItem, NULL, NULL);
trav = root;
}
}
/***********************************************
attaches item to left pointer
***********************************************/
void BinaryTree::attachLeft(const TreeType& newItem)
{
TreeNode *temp;
if(!isEmpty() && trav->lftPtr == NULL)
{
temp = trav;//save trav's position
trav->lftPtr = new TreeNode(newItem, NULL, NULL);//create new node
trav = trav->lftPtr;//move to new node
trav->ancestor = temp;//set new nodes ancestor pointer
trav = temp;//reset position
}
temp = NULL;
}
/***********************************************
attaches item to right pointer
***********************************************/
void BinaryTree::attachRight(const TreeType& newItem)
{
TreeNode *temp;
if(!isEmpty() && trav->rtPtr == NULL)
{
temp = trav;//save trav's position
trav->rtPtr = new TreeNode(newItem, NULL, NULL);//create new node
trav=trav->rtPtr;//move to new node
trav->ancestor = temp;//set new nodes ancestor pointer
trav = temp;//reset position
}
temp = NULL;
}
/***********************************************
preorder traversal
***********************************************/
void BinaryTree::preTrav(FunctionType visit)
{
preorder(root, visit);
}
/***********************************************
inorder traversal
***********************************************/
void BinaryTree::inTrav(FunctionType visit)
{
inorder(root,visit);
}
/***********************************************
postorder traversal
***********************************************/
void BinaryTree::postTrav(FunctionType visit)
{
postorder(root, visit);
}
/***********************************************
overloaded = operator for assigments
***********************************************/
BinaryTree& BinaryTree::operator = (const BinaryTree& rhs)
{
if(this != &rhs)
{
DestroyTree(root);
CopyTree(rhs.root, root);
}
return *this;
}
/***********************************************
actual copytree function that does a deep copy
***********************************************/
void BinaryTree::CopyTree(TreeNode *treePtr,TreeNode *&newTreePtr)const
{
if(treePtr != NULL)
{
newTreePtr = new TreeNode(treePtr->item, NULL, NULL);
CopyTree(treePtr->lftPtr, newTreePtr->lftPtr);
CopyTree(treePtr->rtPtr, newTreePtr->rtPtr);
}
else
{
newTreePtr = NULL;
}
}
/***********************************************
destructor function that destroys a tree
***********************************************/
void BinaryTree::DestroyTree(TreeNode *&treePtr)
{
if(treePtr != NULL)
{
DestroyTree(treePtr->lftPtr);
DestroyTree(treePtr->rtPtr );
delete treePtr;
treePtr = NULL;
}
}
/***********************************************
returns root pointer
***********************************************/
TreeNode *BinaryTree::rootPtr() const
{
return root;
}
/***********************************************
sets root pointer
***********************************************/
void BinaryTree::setRootPtr(TreeNode *newRoot)
{
root = newRoot;
}
/***********************************************
returns child pointers of a node
***********************************************/
void BinaryTree::getChildPtrs(TreeNode *nodePtr,TreeNode *& lftPtr,TreeNode *& rtPtr)const
{
lftPtr = nodePtr->lftPtr;
rtPtr = nodePtr->rtPtr;
}
/***********************************************
sets child pointers of a node
***********************************************/
void BinaryTree::setChildPtrs(TreeNode *nodePtr,TreeNode *& lftPtr,TreeNode *& rtPtr)
{
nodePtr->lftPtr = lftPtr;
nodePtr->rtPtr = rtPtr;
}
/***********************************************
does the actual preorder traversal
***********************************************/
void BinaryTree::preorder(TreeNode *treePtr, FunctionType visit)
{
if(treePtr != NULL)
{
visit(treePtr->item);
preorder(treePtr->lftPtr, visit);
preorder(treePtr->rtPtr, visit);
}
}
/***********************************************
does the actual inorder traversal
***********************************************/
void BinaryTree::inorder(TreeNode *treePtr, FunctionType visit)
{
if(treePtr != NULL)
{
inorder(treePtr->lftPtr, visit);
visit(treePtr->item);
inorder(treePtr->rtPtr, visit);
}
}
/***********************************************
does the actual postorder traversal
***********************************************/
void BinaryTree::postorder(TreeNode *treePtr, FunctionType visit)
{
if(treePtr != NULL)
{
postorder(treePtr->lftPtr, visit);
postorder(treePtr->rtPtr, visit);
visit(treePtr->item);
}
}
/***********************************************
moves iterator to the left pointer
***********************************************/
void BinaryTree::moveLeft()
{
if(trav->lftPtr != NULL)
{
trav = trav->lftPtr;
}
}
/***********************************************
moves iterator to the right pointer
***********************************************/
void BinaryTree::moveRight()
{
if(trav->rtPtr != NULL)
{
trav = trav->rtPtr;
}
}
/***********************************************
moves iterator to the ancestor pointer
***********************************************/
void BinaryTree::moveBack()
{
if(trav->ancestor != NULL)
{
trav = trav->ancestor;
}
}
/***********************************************
resets iterator to the root pointer
***********************************************/
void BinaryTree::moveRoot()
{
trav = root;
}
/***********************************************
returns the data from the current position
***********************************************/
void BinaryTree::getTravData(TreeType& item)
{
if (trav != NULL)
{
item = trav->item;
}
}
/***********************************************
sets the current positions data
***********************************************/
void BinaryTree::setTravData(TreeType& item)
{
if (trav!=NULL)
{
trav->item = item;
}
}
/***********************************************
checks to see if left child is null
***********************************************/
bool BinaryTree::lftNull()
{
return (trav->lftPtr == NULL);
}
/***********************************************
checks to see if right child is null
***********************************************/
bool BinaryTree::rtNull()
{
return (trav->rtPtr == NULL);
}
/***********************************************
library includes
***********************************************/
#include <iostream>
#include <ctype.h>
#include <stdlib.h>
#include <string>
#include <stdio.h>
using namespace std;
/***********************************************
converts a string to uppercase
***********************************************/
void convUp(char *s)
{
int i;//converts a string to all uppercase
i = strlen(s);
for(int y=0; y < i; y++)
{
s[y] = toupper(s[y]);
}
}
/***********************************************
gets a string from the user....I dont like
cin.getline.....or the string getline function
***********************************************/
void getstr( char *s, int len )
{
char buffer[81];
int i, ch;
fflush( stdin );//clear the input stream.......
/* Read in single line from "stdin": got this from msdn....*/
for( i = 0; (i < len) && ((ch = getchar()) != EOF) 
&& (ch != '\n'); i++ )
buffer[i] = (char)ch;
/* Terminate string with null character: */
buffer[i] = '\0';
 
strcpy(s,buffer);
}
/*************************************************
common input function for the whole program...takes
as a const a phrase to display....then calls getstr
to get the string from the user....does validation
and wont release the user till they type a valid 
string............................................
*************************************************/
void getInput(const char phrase[], char ret[], int len)
{
int l=0;
if(len > 0)//if user wants a string greater then 0
{
printf(phrase);//print thew phrase
getstr(ret, len);//get the user's input
if(strlen(ret) <=0)//check length
{
while(strlen(ret)<= 0)//while length is invalid
{
printf("Invalid input: ");//get user input
getstr(ret,len);
}//end while
}//end if
}//end if
}
/*************************************************
if user fails to add a question mark to a question
this will do it for them............................
*************************************************/
void fixPunc(char str[])//str must have extra spaces
{
int i = strlen(str);
if(i>0)
{
char c = str[i-1];
if(c != '?')
{
str[i] = '?';
str[i+1]='\0';
}//end if
}//end if
}
/*************************************************
passed to BinaryTree during traversals..........
used it during testing of the classes............
*************************************************/
void display(TreeType& anItem)
{
cout << anItem << endl;
}
/***************************************************
adds the nodes to the tree during the program
takes a binaryb tree as a parameter
***************************************************/
void addaNode(BinaryTree& t)
{
char *temp = new char[80];//declaring them this way because the class requires a pointer to a reference parameter
char *ques = new char[80];
char *ans = new char[80];
char *hld = new char[80];
char input[80];
t.getTravData(temp);//get the value of the current node
strcpy(input,"I give up. Type the animals name: ");
getInput(input,ans,80);//get user input
strcpy(hld,ans);
strcpy(ans,"Is it a ");
strcat(ans,hld);
strcat(ans, "?");//create the new node value
strcpy(input,"Please type a question about it: ");
getInput(input,ques,80);//get user input
fixPunc(ques);
t.setTravData(ques);//create the new node
t.attachLeft(ans);
t.attachRight(temp);
}
/**************************************************
does the bulk of the work such as get responses 
from the user.....................................
**************************************************/
void game(BinaryTree& t)
{
char *k;
char input[80];
char res[2];
bool null;
for(;;)
{
null = false;//reset for loop
t.moveRoot();//reset for loop
while(null == false)//if we have not reached a leaf
{
t.getTravData(k);
strcpy(input, k);//display node value
strcat(input," yes or no(y or n):");
getInput(input,res,2);//get user response
convUp(res);
if(res[0] == 'Y')//if ans is yes
{
if (t.lftNull() == false)//if the left node is not null
{
t.moveLeft();//move left on tree
}
else//else if we are at a leaf then game over
{
printf("I win!!!!!!\n");
strcpy(input, "Quit? yes or no(y or n):");
getInput(input,res,2);
convUp(res);
if(res[0] != 'N')//if ans is yes
{
exit(1);//exit program
}
null = true;
}
}
else if(res[0] == 'N')//if ans is no
{
if (t.rtNull() == false)//if we are not at a leaf
{
t.moveRight();//move right
}
else
{//check to see if user wants to quit
addaNode(t);//add a new node
strcpy(input, "Quit? yes or no(y or n):");
getInput(input,res,2);
convUp(res);
if(res[0] != 'N')//if ans is yes
{
exit(1);//exit program
}
null = true;
}
}
else//else indicate an error state...
{
printf("Error in entry...\n");
}
}
// break
}//end for loop
}
/***********************************************
creates and sets up the tree and calls game,
which is the main loop for the program.........
***********************************************/
int main()//entry point
{
BinaryTree tree1("Does the Animal Have Legs?");
tree1.attachLeft("Is it a cat?");
tree1.attachRight("Is it a Snake?");
game(tree1);//start main loop
return 0;
}