CIS 22 Spring 2005 - Assignment #5

CIS 22 - Data Structures

Spring 2005
Assignment #5
Practice with Binary Trees

Due: May 1, 2005

Overview

This assignment will give you practice with tree nodes and binary trees. You are asked to write the treenode class and the binary tree class including many methods to practice on.

The TNode Class

Implement the TNode class using father pointers. The TNode class design should look like this:

class TNode {

	public:
		TNode();
		// add in other constructors
		Type getinfo();
		TNode *getleft();
		TNode *getright();
		TNode *getfather();
		TNode *getbrother();	// return pointer to brother node
		void setinfo(Type x);
		void setleft(TNode *p);
		void setright(TNode *p);
		void setfather(TNode *p);
		bool isleaf();		// return true is this node is a leaf
		bool isleftson(); 	// return true if this node is the left
					// son of its father
	private:
		Type info;
		TNode *left;
		TNode *right;
		TNode *father;
}

The Binary Tree Class

Implement the binary tree class as we described it in class. Be careful to make sure that you update the father pointers (the implementation we did in class did not use father pointers) Make the data area protected, because eventually you may be making other classes out of this class.

In addition to the standard methods that we talked about in class, implement the following methods for the Binary Tree class: (These methods should all be written as wrapper functions that call recursive functions to carry out the work.)

count - returns a count of how many items are in the tree
count_leaves - returns a count of how leaves are in the tree
sumdata - return the sum of all the data stored in the tree
findmax - returns the maximum value stored in the tree
depth - length of the longest path from the root to a leaf.
(A tree with a root that has no children has a depth of 0. Otherwise the depth is equal to one plus the maximum of the depth of the two subtrees.)

For the purpose of this assignment, you may assume that the data is numeric, but still use Type in the class definitions.

Testing