You will be converting the binary search function into a template version . And

Question

You will be converting the binary search function into a template version. And this template version of binary search function should be able to work with different data types. IWe are going to use both std::list and std::vector.

Note: Since now the template binary search function is generic for both list and vector, when you traverse the elements inside a list or a vector using iterators, you should probably use std::advance and std::distance instead of the +/- and +=/-= operators, because the latter only work with random access iterators (although std::advance(iterator, 1) and ++iterator do the same thing).

Note:  Don't forget to #include <list> and #include <algorithm> if you are going to use std::list, std::advance and std::distance.

Here is the example output:

For vector v = {1, 2, 5, 7, 9, 13, 15, 18} and list l = {1, 2, 3, 4, 5, 6, 7, 8}:

./Lab8

7 is in the 4th position in the vector.

7 is in the 7th position in the list.

Explanation / Answer

#include using namespace std; // Code Fragment: LinkedBinaryTree1 template class LinkedBinaryTree { protected: // ... (insert Node definition here) //Code Fragment: Node struct Node { // a node in the tree Object element; // the element Node* parent; // parent Node* left; // left child Node* right; // right child Node() : element(Object()) // default constructor { parent = left = right = NULL; } Node* sibling() const { // get our sibling return (this == parent->left ? parent->right : parent->left); } }; typedef Node* NodePtr; // a node pointer public: // ... (insert Position definition here) //Code Fragment: Position class Position { // position in the tree private: NodePtr node; // pointer to the node public: Position(NodePtr n = NULL) // constructor { node = n; } Object& element() const // get element { return node->element; } bool isNull() const // null position? { return node == NULL; } friend class LinkedBinaryTree; // allow access }; private: // member data NodePtr theRoot; // pointer to the root int sz; // number of nodes protected: // protected utilities // ... (insert LinkedBinaryTree utilities here) //Code Fragment: LinkedBinaryTree2 // ... (utilities for LinkedBinaryTree) NodePtr nodePtr(const Position& v) const // convert to NodePtr { return v.node; } bool isExternal(NodePtr n) const // is node external? { return (n->left == NULL && n->right == NULL); } bool isInternal(NodePtr n) const // is node internal? { return ! isExternal(n); } bool isRoot(NodePtr n) const // is node the root? { return (n == theRoot); } void setRoot(NodePtr r) // make r the root { theRoot = r; r->parent = NULL; } void replaceElement(NodePtr n, const Object& o) // replace element { n->element = o; } void swapElements(NodePtr n, NodePtr w) { // swap elements Object temp = w->element; w->element = n->element; n->element = temp; } void expandExternal(NodePtr n) { // expand external node n->left = new Node; n->left->parent = n; n->right = new Node; n->right->parent = n; sz += 2; } NodePtr removeAboveExternal(NodePtr n) { // remove n and parent NodePtr p = n->parent; NodePtr s = n->sibling(); if (isRoot(p)) setRoot(s); // p was root; now s is else { NodePtr g = p->parent; // the grandparent if (p == g->left) g->left = s; // replace parent by sibling else g->right = s; s->parent = g; } delete n; delete p; // delete removed nodes sz -= 2; // two fewer nodes return s; } public: LinkedBinaryTree() // constructor { theRoot = new Node; sz = 1; } int size() const // size of tree { return sz; } bool isEmpty() const // is tree empty? { return (sz == 0); } Position root() const // returns root { return Position(theRoot); } Position leftChild(const Position& v) const // returns left child { return Position(nodePtr(v)->left); } Position rightChild(const Position& v) const // returns right child { return Position(nodePtr(v)->right); } // ... parent(), and sibling() are omitted but similar) bool isRoot(const Position& v) const // is v the root? { return isRoot(nodePtr(v)); } bool isInternal(const Position& v) const // is v internal? { return isInternal(nodePtr(v)); } bool isExternal(const Position& v) const // is v external? { return isExternal(nodePtr(v)); } void replaceElement(const Position& v, const Object& o) { replaceElement(nodePtr(v), o); } // replace element void swapElements(const Position& v, const Position& w) { swapElements(nodePtr(v), nodePtr(w)); } // swap elements void expandExternal(const Position& v) { expandExternal(nodePtr(v)); } // expand external node Position removeAboveExternal(const Position& v) // remove v and parent { return Position(removeAboveExternal(nodePtr(v))); } // ... (housekeeping and iterator functions omitted) }; class Int { public: Int() { counter++; num = counter; } private: static int counter; int num; friend ostream& operator

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

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