template?<?typename? ?K?, ?typename? ?V? > struct? ?Node { Node() : parent_(0),

Question

template?<?typename? ?K?, ?typename? ?V? >

struct? ?Node

{

Node() : parent_(0), left_(0), right_(0) { }

bool? IsRoot() ?const? { ?return?(parent_ == NULL); }

bool? IsExternal() ?const? { ?return?((left_ == NULL) && (right_ == NULL)); }

   K?      key_;

Node?* left_;

Node?* parent_;

Node?* right_;

V?      value_;

};

template?<?typename? ?K?, ?typename? ?V? >

class? ?BinarySearchTree

{

public? :

bool?   Find(?const? ?K?& ?key?);

int?    size(); // NEW MEMBER FUNCTION TO BE IMPLEMENTED   

private? :

Node?<?K?, ?V?>*   Finder(?const? ?K?& ?key?, ?Node?<?K?, ?V?>* ?node?);

Node?<?K?, ?V?>*   root_;

// DECLARE ANY HELPER FUNCTIONS

};

template?<?typename? ?K?, ?typename? ?V? >

bool?   ?BinarySearchTree?<?K?, ?V?>::Find(?const? ?K?& ?key?) {

Node?<?K?, ?V?>* node = Finder(?key?, root_);

if? (!node->IsExternal()) ?// found           ?

return? ?true? ;

else? ?// not found          

?return? ?false? ;

}
   template?<?typename? ?K?, ?typename? ?V? >

Node?<?K?, ?V?>*   ?BinarySearchTree?<?K?, ?V?>::Finder(?const? ?K?& ?key?, ?Node?<?K?, ?V?>* ?node?) {

if? (?node?->IsExternal())         

?return?(?node?);

   if? (?key? == ?node?->key_)         

?return?(?node?);

else? ?if? (?key? < ?node?->key_)       

    ?return?(Finder(?key?, ?node?->left_));

else          

?return?(Finder(?key?, ?node?->right_));

}

//new function to be implemented

template?<?typename? ?K?, ?typename? ?V? >

int BinarySearchTree::size() { }

Space for any helper functions:

#3 - Binary Search Tree code The code below is a partial implementation of a Binary Search Tree (BST) class. (It does not show code for insert/delete as these are not required for this problem), Note that this code does not have a member variable storing the size of the tree. The size of a BST is the number of internal nodes. For example, the size of the BST in Question #1 is 7, Add a method to the code, along with any helper functions, to return the size of the BST. (Hint: think recursion!) Do not make changes to any of the existing functions. Do not change the contents of the search tree. Space to write your new function(s) is given in the end

Explanation / Answer

int BinarySearchTree::size() {

}

The above code shows a recursive funtion that calculates the size of the BST. It starts with the Root node and goes on traversing through the tree and returns it's size. The size() function calls itself recursively untill it has traversed each node and thus returns the size of the BST.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.