C++ only

HearderFile

//Header File Binary Search Tree

#ifndef H_binaryTree

#define H_binaryTree

#include

using namespace std;

//Definition of the Node

template

struct nodeType

{

elemType info;

nodeType *lLink;

nodeType *rLink;

};

//Definition of the class

template

class binaryTreeType

{

public:

const binaryTreeType& operator=

(const binaryTreeType&);

//Overload the assignment operator.

bool isEmpty() const;

//Function to determine whether the binary tree is empty.

//Postcondition: Returns true if the binary tree is empty;

// otherwise, returns false.

void inorderTraversal() const;

//Function to do an inorder traversal of the binary tree.

//Postcondition: Nodes are printed in inorder sequence.

void preorderTraversal() const;

//Function to do a preorder traversal of the binary tree.

//Postcondition: Nodes are printed in preorder sequence.

void postorderTraversal() const;

//Function to do a postorder traversal of the binary tree.

//Postcondition: Nodes are printed in postorder sequence.

int treeHeight() const;

//Function to determine the height of a binary tree.

//Postcondition: Returns the height of the binary tree.

int treeNodeCount() const;

//Function to determine the number of nodes in a

//binary tree.

//Postcondition: Returns the number of nodes in the

// binary tree.

int treeLeavesCount() const;

//Function to determine the number of leaves in a

//binary tree.

//Postcondition: Returns the number of leaves in the

// binary tree.

void destroyTree();

//Function to destroy the binary tree.

//Postcondition: Memory space occupied by each node

// is deallocated.

// root = nullptr;

virtual bool search(const elemType& searchItem) const = 0;

//Function to determine if searchItem is in the binary

//tree.

//Postcondition: Returns true if searchItem is found in

// the binary tree; otherwise, returns

// false.

virtual void insert(const elemType& insertItem) = 0;

//Function to insert insertItem in the binary tree.

//Postcondition: If there is no node in the binary tree

// that has the same info as insertItem, a

// node with the info insertItem is created

// and inserted in the binary search tree.

virtual void deleteNode(const elemType& deleteItem) = 0;

//Function to delete deleteItem from the binary tree

//Postcondition: If a node with the same info as

// deleteItem is found, it is deleted from

// the binary tree.

// If the binary tree is empty or

// deleteItem is not in the binary tree,

// an appropriate message is printed.

binaryTreeType(const binaryTreeType& otherTree);

//Copy constructor

binaryTreeType();

//Default constructor

~binaryTreeType();

//Destructor

protected:

nodeType *root;

private:

void copyTree(nodeType* &copiedTreeRoot,

nodeType* otherTreeRoot);

//Makes a copy of the binary tree to which

//otherTreeRoot points.

//Postcondition: The pointer copiedTreeRoot points to

// the root of the copied binary tree.

void destroy(nodeType* &p);

//Function to destroy the binary tree to which p points.

//Postcondition: Memory space occupied by each node, in

// the binary tree to which p points, is

// deallocated.

// p = nullptr;

void inorder(nodeType *p) const;

//Function to do an inorder traversal of the binary

//tree to which p points.

//Postcondition: Nodes of the binary tree, to which p

// points, are printed in inorder sequence.

void preorder(nodeType *p) const;

//Function to do a preorder traversal of the binary

//tree to which p points.

//Postcondition: Nodes of the binary tree, to which p

// points, are printed in preorder

// sequence.

void postorder(nodeType *p) const;

//Function to do a postorder traversal of the binary

//tree to which p points.

//Postcondition: Nodes of the binary tree, to which p

// points, are printed in postorder

// sequence.

int height(nodeType *p) const;

//Function to determine the height of the binary tree

//to which p points.

//Postcondition: Height of the binary tree to which

// p points is returned.

int max(int x, int y) const;

//Function to determine the larger of x and y.

//Postcondition: Returns the larger of x and y.

int nodeCount(nodeType *p) const;

//Function to determine the number of nodes in

//the binary tree to which p points.

//Postcondition: The number of nodes in the binary

// tree to which p points is returned.

int leavesCount(nodeType *p) const;

//Function to determine the number of leaves in

//the binary tree to which p points

//Postcondition: The number of leaves in the binary

// tree to which p points is returned.

};

//Definition of member functions

template

binaryTreeType::binaryTreeType()

{

root = nullptr;

}

template

bool binaryTreeType::isEmpty() const

{

return (root == nullptr);

}

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

(nodeType* &copiedTreeRoot,

nodeType* otherTreeRoot)

{

if (otherTreeRoot == nullptr)

copiedTreeRoot = nullptr;

else

{

copiedTreeRoot = new nodeType;

copiedTreeRoot->info = otherTreeRoot->info;

copyTree(copiedTreeRoot->lLink, otherTreeRoot->lLink);

copyTree(copiedTreeRoot->rLink, otherTreeRoot->rLink);

}

} //end copyTree

template

void binaryTreeType::inorder

(nodeType *p) const

{

if (p != nullptr)

{

inorder(p->lLink);

cout info

inorder(p->rLink);

}

}

template

void binaryTreeType::preorder

(nodeType *p) const

{

if (p != nullptr)

{

cout info

preorder(p->lLink);

preorder(p->rLink);

}

}

template

void binaryTreeType::postorder

(nodeType *p) const

{

if (p != nullptr)

{

postorder(p->lLink);

postorder(p->rLink);

cout info

}

}

//Overload the assignment operator

template

const binaryTreeType& binaryTreeType::

operator=(const binaryTreeType& otherTree)

{

if (this != &otherTree) //avoid self-copy

{

if (root != nullptr) //if the binary tree is not empty,

//destroy the binary tree

destroy(root);

if (otherTree.root == nullptr) //otherTree is empty

root = nullptr;

else

copyTree(root, otherTree.root);

}//end else

return *this;

}

template

void binaryTreeType::destroy(nodeType* &p)

{

if (p != nullptr)

{

destroy(p->lLink);

destroy(p->rLink);

delete p;

p = nullptr;

}

}

template

void binaryTreeType::destroyTree()

{

destroy(root);

}

//copy constructor

template

binaryTreeType::binaryTreeType

(const binaryTreeType& otherTree)

{

if (otherTree.root == nullptr) //otherTree is empty

root = nullptr;

else

copyTree(root, otherTree.root);

}

//Destructor

template

binaryTreeType::~binaryTreeType()

{

destroy(root);

}

template

int binaryTreeType::height

(nodeType *p) const

{

if (p == nullptr)

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(nodeType *p) const

{

cout

return 0;

}

template

int binaryTreeType::leavesCount(nodeType *p) const

{

cout

return 0;

}

#endif

Use the binaryTree header file, from your textbook companion site, to implement the Binary Search program. This file gives you a good idea for implementing a tree application. It implements postOrder, preOrder, inOrder and many other functions. Many of these functions are not used in this application, so please remove those. Also, please note that most of these functions are already implemented, so use what you already have. You should have a menu driven program to test for all the functions: 1- Insert an item, 2- Delete a given item, 3- Search for an Item, 4- Print postOrder traversal 5- Print preOrder traversal, 6- Print inOrder traversal 7- Quit