Tree Program Assignment

Write a C++ program that will manipulate a binary tree. Your menu driven program should allow the following functions:

Create a binary tree with N nodes where the integer data is stored in the text file tree.dat.
Display the binary tree in Preorder.
Display the binary tree in Inorder.
Display the binary tree in Postorder.
Count the number of nodes in the tree.
Count the number of leaves in the tree.
Sum the node values in the tree.
Compute the height of the tree.
Compute the width of the tree.
Search for a value in the tree.
Delete a node from the binary tree.
Destroy the tree.
Draw the tree with the root at the top and the leaves on the bottom.

Use the following data structure in your program:

	struct TreeNode;
	typedef TreeNode* TreePtr;
	struct TreeNode 
	{
		int data;
		TreePtr left;
		TreePtr right;
	};

When deleting a node from a binary tree, replace the deleted node with the greatest value off the left subtree of the node being deleted. Read these notes for a complete description.

To compute the Height and Width of a tree you will also need to write a Max(x,y) function. The function Max will return the greater value of x and y.

The Height of a binary tree is defined to be the number of nodes in the longest path from the root to a leaf of the binary tree.

The Width of a binary tree is defined to be the number of nodes in the longest path in the binary tree (which does not have to go through the root). The Width of an empty tree is 0. The Width of a non-empty tree is the maximum of the following three quantities.

the width of the left subtree
the width of the right subtree
the length of the longest path that includes the root (which can be calculated from the heights of the left and right subtrees).

Turn in your program with the following test data:

Load the first 20 integer values from tree.dat
Draw the tree.
Show the results for preorder, inorder, postorder traversals, as well the number of nodes, number of leaves, sum of all the noes in the tree, height and width of the tree.
Search for the values: 555, 116 and 28.
Delete values 555, 116, 497, 961, 633, and 644 in that order, then do a preorder, inorder, and postorder traversal.
Draw the tree.
Destroy the tree, and do a preorder traversal.