$//$Header File Binary Search Tree

#ifndef H$\_$binaryTree

#define H$\_$binaryTree

#include

# IMPORTANT NOTICE

# This is the header file binaryTreeType class, which is handled in your lab session.

# For the Q$3$ of lab$-$exam, just scroll down all the way to the bottom

# and fill in the given function blocks.

# $!!!!!!!!!!!!!!!!$

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&$)$;

bool isEmpty$()$ const;

void inorderTraversal$()$ const;

void preorderTraversal$()$ const;

void postorderTraversal$()$ const;

int treeHeight$()$ const;

int treeNodeCount$()$ const;

$//$For Questions:

int treeLeavesCount$()$ const;

void treeSwapSubtrees$()$;

void treeSwapSubtreesOfNode$()$;

int treeSingleParent$()$ const;

int treeSingleP$()$ const;

int treeLargest$()$ const;

int compareSubtreesSum$()$ const;

$//$end

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

binaryTreeType$($const binaryTreeType& otherTree$)$;

binaryTreeType$()$;

protected:

nodeType $*$root;

private:

void copyTree$($nodeType$*$ &copiedTreeRoot, nodeType$*$ otherTreeRoot$)$;

void inorder$($nodeType $*$p$)$ const;

void preorder$($nodeType $*$p$)$ const;

void postorder$($nodeType $*$p$)$ const;

int height$($nodeType $*$p$)$ const;

int max$($int x$,$ int y$)$ const;

int nodeCount$($nodeType $*$p$)$ const;

$//$For Questions:

int leavesCount$($nodeType $*$p$)$ const;

void swapSubtrees$()$;

void swapSubtreesOfNode$($nodeType$*$ p$)$;

int singleParent$()$ const;

int singleP$($nodeType$*$ p$)$ const;

int sum$($nodeType $*$p$)$ const;

$//$end

$\}$;

$//$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$)$;

$\}$

$//$For Questions:

template

int binaryTreeType::treeLeavesCount$()$ const

$\{$

return leavesCount$($root$)$;

$\}$

template

void binaryTreeType::treeSwapSubtrees$()$

$\{$

return swapSubtrees$($root$)$;

$\}$

template

void binaryTreeType::treeSwapSubtreesOfNode$()$

$\{$

return swapSubtreesOfNode$($root$)$;

$\}$

template

int binaryTreeType::treeSingleParent$()$ const

$\{$

return singleParent$($root$)$;

$\}$

template

int binaryTreeType::treeSingleP$()$ const

$\{$

return singleP$($root$)$;

$\}$

$//$end

template

void binaryTreeType::copyTree

$($nodeType$*$ &copiedTreeRoot,

nodeType$*$ otherTreeRoot$)$

$\{$

if $($otherTreeRoot $==$ NULL$)$

copiedTreeRoot $=$ NULL;

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 $!=$ NULL$)$

$\{$

inorder$($p$->$lLink$)$;

cout $$ p$->$info ;

inorder$($p$->$rLink$)$;

$\}$

$\}$

template

void binaryTreeType::preorder

$($nodeType $*$p$)$ const

$\{$

if $($p $!=$ NULL$)$

$\{$

cout $$ p$->$info ;

preorder$($p$->$lLink$)$;

preorder$($p$->$rLink$)$;

$\}$

$\}$

template

void binaryTreeType::postorder

$($nodeType $*$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 $!=$ &othe