5-Trees

The following program demonstrates how to implement a binary tree in C++.  It contains an animal guessing game that uses tree nodes to build a question/answer decision tree.  The member functions implement some basic tree handling routines.

//	animal game -- test of binary trees 
//
//	Described in Chapter 13 of
//	Data Structures in C++ using the STL
//	Published by Addison-Wesley, 1997
//	Written by Tim Budd, budd@cs.orst.edu
//	Oregon State University
//      Updates by Jeff Blessing, 2000s

#include <iostream>
#include <string>
#include <assert.h>
using namespace std;

template<class T>
class node {
public:
	node(T& v, node<T>* par = NULL, node<T>* left = NULL, node<T>* right = NULL)
		: value(v), parent(par), leftChild(left), rightChild(right) { }
	// operations
	node<T>* copy(node<T>*);	// declared only; no definition provided
	void release();				// declared only; no definition provided
	int count(T& testElement);	// declared only; no definition provided
	void insert(node<T>*);
	int size();
	node<T>* merge(node<T>*, node<T>*);

	// data fields
	T value;
	node<T>* parent;
	node<T>* leftChild;
	node<T>* rightChild;
};

template<class T> int node<T>::size()
{ // count number of elements in subtree rooted at node
	int count = 1;
	if (leftChild != NULL)
		count += leftChild->size();		// corrected . operator use
	if (rightChild != NULL)
		count += rightChild->size();	// corrected . operator use
	return count;
}

template<class T> void node<T>::insert(node<T>* newNode)
{ // insert a new element into a binary search tree
	if (newNode->value < value)		// used to have newElement
		if (leftChild != NULL)
			leftChild->insert(newNode);
		else {
			newNode->parent = this;
			leftChild = newNode;
		}
	else
		if (rightChild != NULL)
			rightChild->insert(newNode);
		else {
			newNode->parent = this;
			rightChild = newNode;
		}
}

template<class T>
node<T>* node<T>::merge(node<T>* left, node<T>* right)
{ // merge two subtrees into one
	if (left == NULL)
		return right;
	if (right == NULL)
		return left;
	node<T>* child = merge(left, right->leftChild);
	child->parent = right;
	right->leftChild = child;
	return right;
}

bool answer()
{	// get yes no answer
	while (true) {
		string ans;
		getline(cin, ans);
		if ((ans[0] == 'y') || (ans[0] == 'Y'))
			return true;
		else if ((ans[0] == 'n') || (ans[0] == 'N'))
			return false;
		cout << "please answer yes or no.\n";
	}
}

void learnNewAnimal(node<string>* current)
{	// learn about a new animal type
	string currentAnimal = current->value;
	cout << "what is your animal?\n";
	string newAnimal;
	getline(cin, newAnimal);
	cout << "What is a yes/no question that I can use to tell a "
		<< current->value << " from a " << newAnimal << " ?\n";
	string newQuestion;
	node<string>* node1 = new node<string>(newAnimal, current);
	node<string>* node2 = new node<string>(currentAnimal, current);
	// make sure allocation worked
	assert((node1 != NULL) && (node2 != NULL));

	getline(cin, newQuestion);
	cout << "For a " << newAnimal << " is the answer yes or no?\n";
	if (answer()) {	// delete '!= NULL'
		current->leftChild = node1;
		current->rightChild = node2;
	}
	else {
		current->leftChild = node2;
		current->rightChild = node1;
	}
	current->value = newQuestion;
}

void animalGame() {
	// initialize the database with one animal
	node<string>* root = new node<string>((string)"cat");
	node<string>* current = root;
	// now start the game
	cout << "let's play guess the animal.\n";
	while (current != NULL) {
		// if current node has children, it represents a question
		if (current->leftChild != NULL) {
			cout << current->value << '\n';
			if (answer())
				current = current->leftChild;
			else
				current = current->rightChild;
		}
		// if current node has no children, it is an answer
		else {
			cout << "I know.  Is it a " << current->value << " ?\n";
			if (answer())
				cout << "I won.\n";
			else // We didn't get it. Time to learn something
				learnNewAnimal(current);
			cout << "Try again?\n";
			if (answer())
				current = root;
			else
				return;
		}
	}
}

template<typename T>
void inorder(node<T>* root) {	// also called "infix order" (LDR)
	if (root->leftChild != NULL)
		inorder(root->leftChild);	// recursivly process left subtree
	cout << " " << root->value << endl;	// process data field
	if (root->rightChild != NULL)	// recursivly process right subtree
		inorder(root->rightChild);
}

void main() {
//	animalGame();
	node<string>* root = new node<string>((string) "MSOE");
	node<string>* marquette = new node<string>((string) "MARQUETTE");
	root->insert(marquette);
	node<string>* uwm = new node<string>((string) "UWM");
	root->insert(uwm);
	node<string>* cschools = new node<string>((string) "CONCORDIA");
	cschools->insert(new node<string>((string) "CARTHAGE"));
	cschools->insert(new node<string>((string) "CARROLL"));
	inorder(root);
	cout << "Tree size is " << root->size() << " nodes." << endl;
	inorder(cschools);
	cout << "Tree size is " << cschools->size() << " nodes." << endl;
	root->merge(root, cschools);
	cout << "The root tree is: ";
	inorder(root);
	cout << "The right tree is: ";
	inorder(cschools);
	system("pause");
}

/* Add the following features to this program:
	1) Create an expression tree (interior nodes are operators, leaf
		nodes are operands) and traverse the tree in preorder (DLR), inorder (LDR)
		and postorder (LRD) fashion.  To do this, add a new insert method
		that just puts the next node at the bottom of the tree.  Also
		add a preorder and postorder traversal to our work above.
	2) Adding a new insert method gives us the basis to turn our binary
		trees into heaps.  Add two heap methods called percolateUp() and
		siftDown() that keep the heap in priority order.  Then populate
		the heap with random integer values and remove them in sorted order.
*/
 

4-Stacks

The following code example shows how to use stacks from the C++ Standard Template Library (STL):

#include <iostream>
//#include <vector>		// an STL container
#include <stack>		// an STL adapter
#include <deque>		// an STL container
#include <list>			// an STL container
using namespace std;

void main()
{
	stack< int, list<int> > stk;	// select your container w/2nd arg.
	stack<double> dstk;		// this now works!  container is a deque.

	stk.push(3);
	stk.push(6);
	stk.push(9);
	cout << "Top of stk is " << stk.top() << endl;

	dstk.push(3.14159); dstk.push(2.71828);
	cout << "Top of dstk is " << dstk.top() << endl;
	dstk.pop();
	cout << "Be careful, as underflow is possible!" << endl;
	cout << "After pop, top of dstk is " << dstk.top() << endl;
	stk.pop();
	cout << "stk is popped..." << endl;
	// The following stmts may cause a runtime error:
	cout << "top now returns: " << stk.top() << endl;
	stk.pop();
	cout << "pop is done! top is now: " << stk.top() << endl;
	cout << "Let's attempt to underflow stk" << endl;
	stk.pop();
	cout << "stk's top returns " << stk.top() << endl;

	system("pause");
}
 

Sea 28, GB 22 Simply the Worst Loss in GB Packer History

Need I say more?! But I will. A loss like this one is enough to make me question why I watch football with so much interest invested in the first place. It’s a horrible experience to watch your team fall apart in the final minutes, after commanding the action on the field the entire game, only to let the noisiest venue in football come crashing down on you. As a fan, we’re all helpless to stop it, aside from turning our attention away. How can you watch another Packer game and not think about how this one ended?!