C++ please

1 Overview

Implement a simple version of Binary Search Tree (BST)

2 Requirement

This assignment considers the BST with recursive implementationin chapter 8.

2.1 (Class) Implement a simple version of a BST ADT name TreeType class based on the code in chapter 8.

The TreeType class uses the TreeNode struct (see below) to represent the nodes in the tree.

The items in the tree belong to ItemType as a type of characters: typedef char ItemType;

The TreeType class must have the following functions:

• Three original functions (other functions are not required):
  • bool IsEmpty() const; // see textbook
  • void PutItem(ItemType item); // see textbook
  • int GetLength() const; // see textbook
• Two additional functions:
  • int LeafCount() const; //Post condition: Return the number of leaf nodes in the tree. This function need to call a helper function named Count(TreeNode* tree).
  • int OneChildNodeCount() const; // Post condition: Return the number of node with only one child. This function needs to call a helper function SingleCount(TreeNode* tree).

*Notice: The constructor of the TreeType class must be implemented to create an empty tree.

2.2 (Helper) In the TreeType class, Implement two helper functions mentioned above.

• int Count(TreeNode* tree): This is a recursive function to count and return the number of leaf nodes in the tree.
• int SingleCount(TreeNode* tree): This is a recursive function to count and return the number of nodes with only one child.

**You may use this sample header file:

//Student name:

#include #include

typedef char ItemType; // define the ItemType of character struct TreeNode; class TreeType {

...

}

The struct TreeNode is):

struct TreeNode

{

ItemType info;

TreeNode* left;

TreeNode* right

}

2.3 (TestDriver) Implement the test program (TestDrive.cpp) for testing the TreeType class.

This test program must:

• Create an object of the TreeType class
• Read an input file
• Test all functions of the TreeType class based on the input file
• Write output results to an output file.

The input file must cover the following cases:

IsEmpty PutItem M PutItem D PutItem P PutItem H PutItem C PutItem F PutItem B IsEmpty GetLength LeafCount SingleParentCount Error Quit