Instructions

Write the function singleParent that returns the number of nodes in a binary tree that have only one child.

Add this function to the class binaryTreeType and create a program to test this function. (Note: First create a binary search tree.)

binarySearchTree.h

//HeaderFileBinarySearchTree

#ifndefH_binarySearchTree

#defineH_binarySearchTree

#include

#include"binaryTree.h"

usingnamespacestd;

template

classbSearchTreeType:publicbinaryTreeType

{

public:

boolsearch(constelemType&searchItem)const;

//FunctiontodetermineifsearchItemisinthebinary

//searchtree.

//Postcondition:ReturnstrueifsearchItemisfoundin

//thebinarysearchtree;otherwise,

//returnsfalse.

voidinsert(constelemType&insertItem);

//FunctiontoinsertinsertIteminthebinarysearchtree.

//Postcondition:Ifthereisnonodeinthebinarysearch

//treethathasthesameinfoas

//insertItem,anodewiththeinfo

//insertItemiscreatedandinsertedinthe

//binarysearchtree.

voiddeleteNode(constelemType&deleteItem);

//FunctiontodeletedeleteItemfromthebinarysearchtree

//Postcondition:IfanodewiththesameinfoasdeleteItem

//isfound,itisdeletedfromthebinary

//searchtree.

//IfthebinarytreeisemptyordeleteItem

//isnotinthebinarytree,anappropriate

//messageisprinted.

private:

voiddeleteFromTree(nodeType*&p);

//Functiontodeletethenodetowhichppointsis

//deletedfromthebinarysearchtree.

//Postcondition:Thenodetowhichppointsisdeleted

//fromthebinarysearchtree.

};

template

boolbSearchTreeType::search

(constelemType&searchItem)const

{

nodeType*current;

boolfound=false;

if(this->root==nullptr)

cout<<"Cannotsearchanemptytree."<

else

{

current=this->root;

while(current!=nullptr&&!found)

{

if(current->info==searchItem)

found=true;

elseif(current->info>searchItem)

current=current->lLink;

else

current=current->rLink;

}//endwhile

}//endelse

returnfound;

}//endsearch

template

voidbSearchTreeType::insert

(constelemType&insertItem)

{

nodeType*current;//pointertotraversethetree

nodeType*trailCurrent=nullptr;//pointer

//behindcurrent

nodeType*newNode; //pointertocreatethenode

newNode=newnodeType;

newNode->info=insertItem;

newNode->lLink=nullptr;

newNode->rLink=nullptr;

if(this->root==nullptr)

this->root=newNode;

else

{

current=this->root;

while(current!=nullptr)

{

trailCurrent=current;

if(current->info==insertItem)

{

cout<<"Theitemtobeinsertedisalready";

cout<<"inthetree--duplicatesarenot"

<<"allowed."<

return;

}

elseif(current->info>insertItem)

current=current->lLink;

else

current=current->rLink;

}//endwhile

if(trailCurrent->info>insertItem)

trailCurrent->lLink=newNode;

else

trailCurrent->rLink=newNode;

}

}//endinsert

template

voidbSearchTreeType::deleteNode

(constelemType&deleteItem)

{

nodeType*current;//pointertotraversethetree

nodeType*trailCurrent;//pointerbehindcurrent

boolfound=false;

if(this->root==nullptr)

cout<<"Cannotdeletefromanemptytree."

<

else

{

current=this->root;

trailCurrent=this->root;

while(current!=nullptr&&!found)

{

if(current->info==deleteItem)

found=true;

else

{

trailCurrent=current;

if(current->info>deleteItem)

current=current->lLink;

else

current=current->rLink;

}

}//endwhile

if(current==nullptr)

cout<<"Theitemtobedeletedisnotinthetree."

<

elseif(found)

{

if(current==this->root)

deleteFromTree(this->root);

elseif(trailCurrent->info>deleteItem)

deleteFromTree(trailCurrent->lLink);

else

deleteFromTree(trailCurrent->rLink);

}

else

cout<<"Theitemtobedeletedisnotinthetree."

<

}

}//enddeleteNode

template

voidbSearchTreeType::deleteFromTree

(nodeType*&p)

{

nodeType*current;//pointertotraversethetree

nodeType*trailCurrent; //pointerbehindcurrent

nodeType*temp; //pointertodeletethenode

if(p==nullptr)

cout<<"Error:Thenodetobedeleteddoesnotexist."

<

elseif(p->lLink==nullptr&&p->rLink==nullptr)

{

temp=p;

p=nullptr;

deletetemp;

}

elseif(p->lLink==nullptr)

{

temp=p;

p=temp->rLink;

deletetemp;

}

elseif(p->rLink==nullptr)

{

temp=p;

p=temp->lLink;

deletetemp;

}

else

{

current=p->lLink;

trailCurrent=nullptr;

while(current->rLink!=nullptr)

{

trailCurrent=current;

current=current->rLink;

}//endwhile

p->info=current->info;

if(trailCurrent==nullptr)//currentdidnotmove;

//current==p->lLink;adjustp

p->lLink=current->lLink;

else

trailCurrent->rLink=current->lLink;

deletecurrent;

}//endelse

}//enddeleteFromTree

#endif

binaryTree.h

//HeaderFileBinaryTree

#ifndefH_binaryTree

#defineH_binaryTree

#include

usingnamespacestd;

//Definitionofthenode

template

structnodeType

{

elemTypeinfo;

nodeType*lLink;

nodeType*rLink;

};

//Definitionoftheclass

template

classbinaryTreeType

{

public:

constbinaryTreeType&operator=

(constbinaryTreeType&);

//Overloadtheassignmentoperator.

boolisEmpty()const;

//Functiontodeterminewhetherthebinarytreeisempty.

//Postcondition:Returnstrueifthebinarytreeisempty;

//otherwise,returnsfalse.

voidinorderTraversal()const;

//Functiontodoaninordertraversalofthebinarytree.

//Postcondition:Nodesareprintedininordersequence.

voidpreorderTraversal()const;

//Functiontodoapreordertraversalofthebinarytree.

//Postcondition:Nodesareprintedinpreordersequence.

voidpostorderTraversal()const;

//Functiontodoapostordertraversalofthebinarytree.

//Postcondition:Nodesareprintedinpostordersequence.

inttreeHeight()const;

//Functiontodeterminetheheightofabinarytree.

//Postcondition:Returnstheheightofthebinarytree.

inttreeNodeCount()const;

//Functiontodeterminethenumberofnodesina

//binarytree.

//Postcondition:Returnsthenumberofnodesinthe

//binarytree.

inttreeLeavesCount()const;

//Functiontodeterminethenumberofleavesina

//binarytree.

//Postcondition:Returnsthenumberofleavesinthe

//binarytree.

voiddestroyTree();

//Functiontodestroythebinarytree.

//Postcondition:Memoryspaceoccupiedbyeachnode

//isdeallocated.

//root=nullptr;

virtualboolsearch(constelemType&searchItem)const=0;

//FunctiontodetermineifsearchItemisinthebinary

//tree.

//Postcondition:ReturnstrueifsearchItemisfoundin

//thebinarytree;otherwise,returns

//false.

virtualvoidinsert(constelemType&insertItem)=0;

//FunctiontoinsertinsertIteminthebinarytree.

//Postcondition:Ifthereisnonodeinthebinarytree

//thathasthesameinfoasinsertItem,a

//nodewiththeinfoinsertItemiscreated

//andinsertedinthebinarysearchtree.

virtualvoiddeleteNode(constelemType&deleteItem)=0;

//FunctiontodeletedeleteItemfromthebinarytree

//Postcondition:Ifanodewiththesameinfoas

//deleteItemisfound,itisdeletedfrom

//thebinarytree.

//Ifthebinarytreeisemptyor

//deleteItemisnotinthebinarytree,

//anappropriatemessageisprinted.

binaryTreeType(constbinaryTreeType&otherTree);

//Copyconstructor

binaryTreeType();

//Defaultconstructor

~binaryTreeType();

//Destructor

protected:

nodeType*root;

private:

voidcopyTree(nodeType*&copiedTreeRoot,

nodeType*otherTreeRoot);

//Makesacopyofthebinarytreetowhich

//otherTreeRootpoints.

//Postcondition:ThepointercopiedTreeRootpointsto

//therootofthecopiedbinarytree.

voiddestroy(nodeType*&p);

//Functiontodestroythebinarytreetowhichppoints.

//Postcondition:Memoryspaceoccupiedbyeachnode,in

//thebinarytreetowhichppoints,is

//deallocated.

//p=nullptr;

voidinorder(nodeType*p)const;

//Functiontodoaninordertraversalofthebinary

//treetowhichppoints.

//Postcondition:Nodesofthebinarytree,towhichp

//points,areprintedininordersequence.

voidpreorder(nodeType*p)const;

//Functiontodoapreordertraversalofthebinary

//treetowhichppoints.

//Postcondition:Nodesofthebinarytree,towhichp

//points,areprintedinpreorder

//sequence.

voidpostorder(nodeType*p)const;

//Functiontodoapostordertraversalofthebinary

//treetowhichppoints.

//Postcondition:Nodesofthebinarytree,towhichp

//points,areprintedinpostorder

//sequence.

intheight(nodeType*p)const;

//Functiontodeterminetheheightofthebinarytree

//towhichppoints.

//Postcondition:Heightofthebinarytreetowhich

//ppointsisreturned.

intmax(intx,inty)const;

//Functiontodeterminethelargerofxandy.

//Postcondition:Returnsthelargerofxandy.

intnodeCount(nodeType*p)const;

//Functiontodeterminethenumberofnodesin

//thebinarytreetowhichppoints.

//Postcondition:Thenumberofnodesinthebinary

//treetowhichppointsisreturned.

intleavesCount(nodeType*p)const;

//Functiontodeterminethenumberofleavesin

//thebinarytreetowhichppoints

//Postcondition:Thenumberofleavesinthebinary

//treetowhichppointsisreturned.

};

template

boolbinaryTreeType::isEmpty()const

{

return(root==nullptr);

}

template

binaryTreeType::binaryTreeType()

{

root=nullptr;

}

template

voidbinaryTreeType::inorderTraversal()const

{

inorder(root);

}

template

voidbinaryTreeType::preorderTraversal()const

{

preorder(root);

}

template

voidbinaryTreeType::postorderTraversal()const

{

postorder(root);

}

template

intbinaryTreeType::treeHeight()const

{

returnheight(root);

}

template

intbinaryTreeType::treeNodeCount()const

{

returnnodeCount(root);

}

template

intbinaryTreeType::treeLeavesCount()const

{

returnleavesCount(root);

}

template

voidbinaryTreeType::inorder

(nodeType*p)const

{

if(p!=nullptr)

{

inorder(p->lLink);

cout<info<<"";

inorder(p->rLink);

}

}

template

voidbinaryTreeType::preorder

(nodeType*p)const

{

if(p!=nullptr)

{

cout<info<<"";

preorder(p->lLink);

preorder(p->rLink);

}

}

template

voidbinaryTreeType::postorder

(nodeType*p)const

{

if(p!=nullptr)

{

postorder(p->lLink);

postorder(p->rLink);

cout<info<<"";

}

}

template

intbinaryTreeType::height

(nodeType*p)const

{

if(p==nullptr)

return0;

else

return1+max(height(p->lLink),height(p->rLink));

}

template

intbinaryTreeType::max(intx,inty)const

{

if(x>=y)

returnx;

else

returny;

}

template

voidbinaryTreeType::copyTree

(nodeType*&copiedTreeRoot,

nodeType*otherTreeRoot)

{

if(otherTreeRoot==nullptr)

copiedTreeRoot=nullptr;

else

{

copiedTreeRoot=newnodeType;

copiedTreeRoot->info=otherTreeRoot->info;

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

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

}

}//endcopyTree

template

voidbinaryTreeType::destroy(nodeType*&p)

{

if(p!=nullptr)

{

destroy(p->lLink);

destroy(p->rLink);

deletep;

p=nullptr;

}

}

template

voidbinaryTreeType::destroyTree()

{

destroy(root);

}

//copyconstructor

template

binaryTreeType::binaryTreeType

(constbinaryTreeType&otherTree)

{

if(otherTree.root==nullptr)//otherTreeisempty

root=nullptr;

else

copyTree(root,otherTree.root);

}

//Destructor

template

binaryTreeType::~binaryTreeType()

{

destroy(root);

}

//Overloadtheassignmentoperator

template

constbinaryTreeType&binaryTreeType::

operator=(constbinaryTreeType&otherTree)

{

if(this!=&otherTree)//avoidself-copy

{

if(root!=nullptr) //ifthebinarytreeisnotempty,

//destroythebinarytree

destroy(root);

if(otherTree.root==nullptr)//otherTreeisempty

root=nullptr;

else

copyTree(root,otherTree.root);

}//endelse

return*this;

}

#endif

I need main.cpp