#include "BSTree.h$"$

template

BSTree::BSTreeNode::BSTreeNode $($ const DataType &nodeDataItem, BSTreeNode $*$leftPtr$,$ BSTreeNode $*$rightPtr $)$

: dataItem$($nodeDataItem$),$ left$($leftPtr$),$ right$($rightPtr$)$

$\{$

$//$ nothing needs to be changed

$\}$

template $<$ typename DataType, class KeyType $>$

BSTree::BSTree $()$

$\{$

$//$ nothing needs to be changed

root $=0$;

$//$ or

$//$ root $=$ nullptr;

$\}$

template $<$ typename DataType, class KeyType $>$

BSTree::~BSTree$()$

$\{$

$//$ nothing needs to be changed

clear$()$;

$\}$

template $<$ typename DataType, class KeyType $>$

BSTree::BSTree $($ const BSTree& other $)$

$\{$

root $=$ NULL;

$*$this $=$ other;

$\}$

template $<$ typename DataType, class KeyType $>$

BSTree& BSTree:: operator$=($ const BSTree& other $)$

$\{$

if$($ this $!=$ &other $)\{$

clear$()$;

if$(!$other.isEmpty$())\{$

clone$\_$sub$($ root, other.root $)$;

$\}$

$\}$

return $*$this;

$\}$

template $<$ typename DataType, class KeyType $>$

void BSTree::insert $($ const DataType& newDataItem $)$

$\{$

KeyType key $=$ newDataItem.getKey$()$;

insert$\_$sub$($ root, newDataItem, key $)$;

$\}$

template $<$ typename DataType, class KeyType $>$

void BSTree::clear$()$

$\{$

if$($ root $!=$ NULL $)$

$\{$

clear$\_$sub$($ root $)$;

$\}$

$\}$

template $<$ typename DataType, class KeyType $>$

bool BSTree::isEmpty$()$ const

$\{$

if $($ root $==$ NULL $)$

$\{$

cout $<<$ "Empty tree" $<<$ endl;

return true;

$\}$

else

$\{$

cout $<<$ endl;

showHelper$($root$,1)$;

cout $<<$ endl;

return false;

$\}$

$\}$

template

void BSTree::insert$\_$sub$($ BSTreeNode$*$& currentNode, const DataType& newDataItem, const KeyType& key $)$

$\{$

KeyType currentKey;

if$($ currentNode $==$ NULL $)\{$

currentNode $=$ new BSTreeNode$($ newDataItem, NULL, NULL $)$;

$\}$

else $\{$

currentKey $=$ currentNode$->$dataItem.getKey$()$;

if$($ key $==$ currentKey $)\{$

currentNode$->$dataItem $=$ newDataItem;

$\}$

else if$($ key $<$ currentKey $)\{$

insert$\_$sub$($ currentNode$->$left, newDataItem, key $)$;

$\}$

else $\{$

insert$\_$sub$($ currentNode$->$right, newDataItem, key $)$;

$\}$

$\}$

$\}$

template

void BSTree::clone$\_$sub$($ BSTreeNode$*$& currentNode,

const BSTreeNode$*$ otherNode $)$

$\{$

currentNode $=$ new BSTreeNode$($ otherNode$->$dataItem, NULL, NULL $)$;

if$($ otherNode$->$left $!=$ NULL $)\{$

clone$\_$sub$($ currentNode$->$left, otherNode$->$left $)$;

$\}$

if$($ otherNode$->$right $!=$ NULL $)\{$

clone$\_$sub$($ currentNode$->$right, otherNode$->$right $)$;

$\}$

$\}$

template

void BSTree::clear$\_$sub$($ BSTreeNode$*$& currentNode $)$

$\{$

if$($ currentNode$->$left $!=$ NULL $)$

$\{$

clear$\_$sub$($ currentNode$->$left $)$;

$\}$

if$($ currentNode$->$right $!=$ NULL $)$

$\{$

clear$\_$sub$($ currentNode$->$right $)$;

$\}$

delete currentNode;

currentNode $=$ NULL;

$\}$

$//===================================================================$ end of in$-$class part

template $<$ typename DataType, class KeyType $>$

bool BSTree::retrieve $($ const KeyType& searchKey, DataType& searchDataItem $)$ const

$\{$

return false;

$\}$

template $<$ typename DataType, class KeyType $>$

bool BSTree::remove $($ const KeyType& deleteKey $)$

$\{$

return false;

$\}$

template $<$ typename DataType, class KeyType $>$

void BSTree::writeKeys $()$ const

$\{$

$\}$

template $<$ typename DataType, class KeyType $>$

int BSTree::getHeight $()$ const

$\{$

return $-1$;

$\}$

template $<$ typename DataType, class KeyType $>$

int BSTree::getCount $()$ const

$\{$

return $-1$;

$\}$

template $<$ typename DataType, class KeyType $>$

void BSTree::writeLessThan $($ const KeyType& searchKey $)$ const

$\{$

$\}$

#include "show$9.$cpp$"$