Data Structures C++

A node's level is the number of parent's nodes from the root to node. The root is always at level 0. The root's children are a level 1 and so on. A level's width is the number of nodes at the level. A tree's width the greatest width of all of a tree's levels' width. Add iterative functions to the binaryTree class to compute a tree's width.

BINARYSEARCHTREE.H

//Header File Binary Search Tree

#ifndef H_binarySearchTree #define H_binarySearchTree #include #include #include "binaryTree.h"

//************************************************************* // Author: D.S. Malik // // This class specifies the basic operations to implement a // binary search tree. //*************************************************************

using namespace std;

template class bSearchTreeType: public binaryTreeType { public: bool search(const elemType& searchItem) const; //Function to determine if searchItem is in the binary //search tree. //Postcondition: Returns true if searchItem is found in the // binary search tree; otherwise, returns false.

void insert(const elemType& insertItem); //Function to insert insertItem in the binary search tree. //Postcondition: If no node in the binary search tree has the // same info as insertItem, a node with the info insertItem // is created and inserted in the binary search tree.

void deleteNode(const elemType& deleteItem); //Function to delete deleteItem from the binary search tree //Postcondition: If a node with the same info as deleteItem // is found, it is deleted from the binary search tree

private: void deleteFromTree(binaryTreeNode* &p); //Function to delete the node to which p points is deleted //from the binary search tree. //Postcondition: The node to which p points is deleted from // the binary search tree. };

template bool bSearchTreeType:: search(const elemType& searchItem) const { binaryTreeNode *current; bool found = false;

if (root == NULL) cerr << "Cannot search the empty tree." << endl; else { current = root;

while (current != NULL && !found) { if (current->info == searchItem) found = true; else if (current->info > searchItem) current = current->llink; else current = current->rlink; }//end while }//end else

return found; }//end search

template void bSearchTreeType::insert(const elemType& insertItem) { binaryTreeNode *current; //pointer to traverse the tree binaryTreeNode *trailCurrent; //pointer behind current binaryTreeNode *newNode; //pointer to create the node

newNode = new binaryTreeNode; assert(newNode != NULL); newNode->info = insertItem; newNode->llink = NULL; newNode->rlink = NULL;

if (root == NULL) root = newNode; else { current = root; while (current != NULL) { trailCurrent = current;

if (current->info == insertItem) { cerr << "The insert item is already in the list-"; cerr << "duplicates are not allowed." << insertItem << endl; return; } else if (current->info > insertItem) current = current->llink; else current = current->rlink; }//end while

if (trailCurrent->info > insertItem) trailCurrent->llink = newNode; else trailCurrent->rlink = newNode; } }//end insert

template void bSearchTreeType::deleteNode(const elemType& deleteItem) { binaryTreeNode *current; //pointer to traverse the tree binaryTreeNode *trailCurrent; //pointer behind current bool found = false;

if (root == NULL) cout << "Cannot delete from the empty tree." << endl; else { current = root; trailCurrent = root;

while (current != NULL && !found) { if (current->info == deleteItem) found = true; else { trailCurrent = current;

if (current->info > deleteItem) current = current->llink; else current = current->rlink; } }//end while

if (current == NULL) cout << "The delete item is not in the tree." << endl; else if (found) { if (current == root) deleteFromTree(root); else if (trailCurrent->info > deleteItem) deleteFromTree(trailCurrent->llink); else deleteFromTree(trailCurrent->rlink); }//end if } }//end deleteNode

template void bSearchTreeType::deleteFromTree (binaryTreeNode* &p) { binaryTreeNode *current; //pointer to traverse the tree binaryTreeNode *trailCurrent; //pointer behind current binaryTreeNode *temp; //pointer to delete the node

if (p == NULL) cerr << "Error: The node to be deleted is NULL." << endl; else if(p->llink == NULL && p->rlink == NULL) { temp = p; p = NULL; delete temp; } else if(p->llink == NULL) { temp = p; p = temp->rlink; delete temp; } else if(p->rlink == NULL) { temp = p; p = temp->llink; delete temp; } else { current = p->llink; trailCurrent = NULL;

while (current->rlink != NULL) { trailCurrent = current; current = current->rlink; }//end while

p->info = current->info;

if (trailCurrent == NULL) //current did not move; //current == p->llink; adjust p p->llink = current->llink; else trailCurrent->rlink = current->llink; delete current; }//end else }//end deleteFromTree

#endif

BINARYTREE.H

//Header File Binary Search Tree #ifndef H_binaryTree #define H_binaryTree

//************************************************************* // Author: D.S. Malik // // class binaryTreeType // This class specifies the basic operations to implement a // binary tree. //*************************************************************

#include

using namespace std;

//Definition of the node template struct binaryTreeNode { elemType info; binaryTreeNode *llink; binaryTreeNode *rlink; };

//Definition of the class template class binaryTreeType { public: const binaryTreeType& operator= (const binaryTreeType&); //Overload the assignment operator. bool isEmpty() const; //Returns true if the binary tree is empty; //otherwise, returns false. void inorderTraversal() const; //Function to do an inorder traversal of the binary tree. void preorderTraversal() const; //Function to do a preorder traversal of the binary tree. void postorderTraversal() const; //Function to do a postorder traversal of the binary tree.

int treeHeight() const; //Returns the height of the binary tree. int treeNodeCount() const; //Returns the number of nodes in the binary tree. int treeLeavesCount() const; //Returns the number of leaves in the binary tree. void destroyTree(); //Deallocates the memory space occupied by the binary tree. //Postcondition: root = NULL;

binaryTreeType(const binaryTreeType& otherTree); //copy constructor

binaryTreeType(); //default constructor

~binaryTreeType(); //destructor

//leavesCount();

protected: binaryTreeNode *root;

private: void copyTree(binaryTreeNode* &copiedTreeRoot, binaryTreeNode* otherTreeRoot); //Makes a copy of the binary tree to which //otherTreeRoot points. The pointer copiedTreeRoot //points to the root of the copied binary tree.

void destroy(binaryTreeNode* &p); //Function to destroy the binary tree to which p points. //Postcondition: p = NULL

void inorder(binaryTreeNode *p) const; //Function to do an inorder traversal of the binary //tree to which p points. void preorder(binaryTreeNode *p) const; //Function to do a preorder traversal of the binary //tree to which p points. void postorder(binaryTreeNode *p) const; //Function to do a postorder traversal of the binary //tree to which p points.

int height(binaryTreeNode *p) const; //Function to return the height of the binary tree //to which p points. int max(int x, int y) const; //Returns the larger of x and y. int nodeCount(binaryTreeNode *p) const; //Function to return the number of nodes in the binary //tree to which p points int leavesCount(binaryTreeNode *p) const; //Function to return the number of leaves in the binary //tree to which p points };

//Definition of member functions

template binaryTreeType::binaryTreeType() { root = NULL; }

template bool binaryTreeType::isEmpty() const { return (root == NULL); }

template void binaryTreeType::inorderTraversal() const { inorder(root); }

template void binaryTreeType::preorderTraversal() const { preorder(root); }

template void binaryTreeType::postorderTraversal() const { postorder(root); }

template int binaryTreeType::treeHeight() const { return height(root); }

template int binaryTreeType::treeNodeCount() const { return nodeCount(root); }

template int binaryTreeType::treeLeavesCount() const { return leavesCount(root); }

template void binaryTreeType::copyTree (binaryTreeNode* &copiedTreeRoot, binaryTreeNode* otherTreeRoot) { if (otherTreeRoot == NULL) copiedTreeRoot = NULL; else { copiedTreeRoot = new binaryTreeNode; copiedTreeRoot->info = otherTreeRoot->info; copyTree(copiedTreeRoot->llink, otherTreeRoot->llink); copyTree(copiedTreeRoot->rlink, otherTreeRoot->rlink); } } //end copyTree

template void binaryTreeType::inorder(binaryTreeNode *p) const { if (p != NULL) { inorder(p->llink); cout << p->info << " "; inorder(p->rlink); } }

template void binaryTreeType::preorder(binaryTreeNode *p) const { if (p != NULL) { cout<info<<" "; preorder(p->llink); preorder(p->rlink); } }

template void binaryTreeType::postorder(binaryTreeNode *p) const { if (p != NULL) { postorder(p->llink); postorder(p->rlink); cout << p->info << " "; } }

//Overload the assignment operator template const binaryTreeType& binaryTreeType:: operator=(const binaryTreeType& otherTree) { if (this != &otherTree) //avoid self-copy { if (root != NULL) //if the binary tree is not empty, //destroy the binary tree destroy(root);

if (otherTree.root == NULL) //otherTree is empty root = NULL; else copyTree(root, otherTree.root); }//end else

return *this; }

template void binaryTreeType::destroy(binaryTreeNode* &p) { if (p != NULL) { destroy(p->llink); destroy(p->rlink); delete p; p = NULL; } }

template void binaryTreeType::destroyTree() { destroy(root); }

//copy constructor template binaryTreeType::binaryTreeType (const binaryTreeType& otherTree) { if (otherTree.root == NULL) //otherTree is empty root = NULL; else copyTree(root, otherTree.root); }

template binaryTreeType::~binaryTreeType() { destroy(root); }

template int binaryTreeType::height(binaryTreeNode *p) const { if (p == NULL) return 0; else return 1 + max(height(p->llink), height(p->rlink)); }

template int binaryTreeType::max(int x, int y) const { if (x >= y) return x; else return y; }

template int binaryTreeType::nodeCount(binaryTreeNode *p) const { cout << "Write the definition of the function nodeCount" << endl;

return 0; }

template int binaryTreeType::leavesCount(binaryTreeNode *p) const { if (p == NULL) return 0; else if (p->llink == NULL && rlink == NULL) return 1; else return leavesCount(p->llink) + leavesCount(p->rlink); }

#endif

How exactly do I approach this problem?