BST.CPP

------------

#include #include #include #include #include #include #include "BST.h"

using namespace std;

//-------------------------------------------- // Function: insert(int) // Purpose: insert a node into a binary tree // Returns: void //--------------------------------------------

bool BST::insert(int el) { // Pointers to keep track of where we are in descending // through the tree to find an insertion point BSTNode *ptr = Root; BSTNode *prev = NULL;

// If tree is empty, then insert the first node

if (this->isEmpty()) { Root = new BSTNode(el); return true; }

// Descend the tree for a proper place to put the input value // The input value will become a new leaf on the tree // NOTE: This does NOT perform any tree balancing!

while (ptr != NULL) { // prev remembers where we were, so when ptr becomes // NULL, prev will point to the node where we will // attach the new value as a child

prev = ptr;

// Descend the tree until we hit a leaf - go left if value // is less than current node, go right if greater

if (el getEl()) { ptr = ptr->getLeftChild(); } else if (el > ptr->getEl()) { ptr = ptr->getRightChild(); } else { // If the value matches one already in the tree, we // DON'T add it to the tree and simply return cout

// Create the new node and attach it to the node that prev // is pointing to

if (el getEl()) prev->setLeftChild(new BSTNode(el)); else prev->setRightChild(new BSTNode(el));

return true; }

//-------------------------------------------- // Function: isEmpty() // Purpose: determine whether a BST has no nodes // Returns: a boolean - true if empty //--------------------------------------------

bool BST::isEmpty() { return (Root == NULL); }

//-------------------------------------------- // Function: search(int) // Purpose: search for a value in a binary tree // Returns: a boolean - true is found, false if not //--------------------------------------------

bool BST::search(int el) const{ if(Root->getEl() == NULL) return false; if(Root->getEl() == el) return true; if(Root->getEl() getLeftChild() == &el) return true; } else if(Root->getEl() > el){ if(Root->getRightChild() == &el) return true; } return false; }

//-------------------------------------------- // Function: is_leaf(int) // Purpose: search for a value in a leaf of a // binary tree // Returns: a boolean - true is found, false if not //--------------------------------------------

// CODE FOR is_leaf METHOD GOES HERE

//-------------------------------------------- // Function: delete_leaf(int) // Purpose: delete node from tree if it's a leaf // Returns: a boolean - true is deleted, false if not //--------------------------------------------

// CODE FOR delete_leaf METHOD GOES HERE

BST.H

----------

class BSTNode { public:

// Two constructors: // BSTNode() creates an "empty" node with no value for el // BSTNode() crates a node with the given el value and // two pointers to "children" BSTNodes (which can // also be used with the el value only) BSTNode() { leftChild = NULL; rightChild = NULL; } BSTNode(int e, BSTNode *l = NULL, BSTNode *r = NULL) { el = e; leftChild = l; rightChild = r; } // Desctructor ~BSTNode(); // Accessors int getEl() const { return el; } BSTNode *getLeftChild() const { return leftChild; } BSTNode *getRightChild() const { return rightChild; } // Mutators (changing the el value is not permitted :-) void setLeftChild(BSTNode *nodePtr) { leftChild = nodePtr; } void setRightChild(BSTNode *nodePtr) { rightChild = nodePtr; } protected: int el; BSTNode *leftChild; BSTNode *rightChild; };

class BST { public: // Constructor BST() { // Create an empty binary tree // The first insertion will place a Node at the root Root = NULL; } // Destructor ~BST();

// Accessors bool search(int el) const; // bool is_leaf(int el) const;

// Mutators bool insert(int el); // bool delete_leaf(int el); // Other methods bool isEmpty();

protected: BSTNode *Root; };

#endif /* BST_H */

Define and test a new method bool BST::search(int el) that will search the binary tree for the integer value el. Your method should return true if the value is found and false if the value is not found. This method should not write anything to the screen. Define and test a new method bool BST::is_leaf(int el) that will search the binary tree for the integer value el. Your method should return true if the value is found in a leaf node and false if the value is not found or is found in an interior node. As a side effect, if the node is an interior node or was not found, your method should write that information to the screen. Define and test a new method bool BST::delete_leaf(int el) that will search the binary tree for the integer value el. Your method should delete the BSTNode from the tree and free up the allocated memory of the BSTNode) ONLY if the node is a leaf node. Also, the parent's pointer to the node NEEDS to be set to NULL! Return true if leaf is deleted