EECE 330 Lab Report, Spring 2008

Lab 5 _Soln 1) (As a template function in main) template <class Compare, class Key, class Elem > bool search (BinNode<Elem>* subroot, Key K ) { if (subroot == NULL) return false; //if (subroot->val() == K) return true; if (Compare::eq(subroot->val() , K)) return true; if (search <Compare>(subroot->right(), K)) return true; return search<Compare>(subroot->left(),K); } 2) For a binary tree (As a template function in main): template <class KECompare,class Key, class Elem > int smallCount(BinNode<Elem>* subroot, Key K) { if (subroot == NULL) return 0; // Empty subtree if (KECompare::gt(subroot->val(), K)) return smallCount<KECompare>(subroot->left(), K)+ smallCount<KECompare>(subroot->right(), K); else return smallCount<KECompare>(subroot->left(), K) + smallCount<KECompare>(subroot->right(), K) + 1; } For a BST (As a member function in BST, it can also be as a member fn in BST with helper) : template <class Key, class Elem, class KEComp, class EEComp> int BST<Key, Elem, KEComp, EEComp>:: smallcount(BinNode<Elem> * subroot , Key K) { if (subroot == NULL) { cout<<"Null"<<endl; return 0;} if (KEComp::gt( K, subroot->val())) {cout<<"If"<<endl; return smallcount(subroot->left(), K) + smallcount(subroot->right(), K) + 1;} else {cout<<"else"<<endl; return smallcount(subroot->left(), K) ;} 3)As a template function in main template <class KEComp, class Key, class Elem > void printRange(BinNode<Elem>* root, Key low, Key high) { if (root == NULL) return; if (KEComp::lt(high, root->val())) // all to left printRange <KEComp>(root->left(), low, high); else if (KEComp::gt(low, root->val())) // all to right printRange< KEComp>(root->right(), low, high); 1 else { // Must process both children printRange< KEComp>(root->left(), low, high); cout<<root->val()<<" "; printRange< KEComp>(root->right(), low, high); } } 4) // Min-heap class template <class Elem, class Comp> class minheap { private: Elem* Heap; // Pointer to the heap array int size; // Maximum size of the heap int n; // Number of elements now in the heap void siftdown(int); // Put element in its correct place public: minheap(Elem* h, int num, int max) // Constructor { Heap = h; n = num; size = max; buildHeap(); } int heapsize() const // Return current heap size { return n; } bool isLeaf(int pos) const // TRUE if pos a leaf { return (pos >= n/2) && (pos < n); } int leftchild(int pos) const { return 2*pos + 1; } // Return leftchild position int rightchild(int pos) const { return 2*pos + 2; } // Return rightchild position int parent(int pos) const // Return parent position { return (pos-1)/2; } bool insert(const Elem&); // Insert value into heap bool removemin(Elem&); // Remove manimum value bool remove(int, Elem&); // Remove from given position void buildHeap() // Heapify contents of Heap { for (int i=n/2-1; i>=0; i--) siftdown(i); } }; template <class Elem, class Comp> void minheap<Elem, Comp>::siftdown(int pos) { while (!isLeaf(pos)) { // Stop if pos is a leaf int j = leftchild(pos); int rc = rightchild(pos); if ((rc < n) && Comp::gt(Heap[j], Heap[rc])) j = rc; // Set j to lesser child's value if (!Comp::gt(Heap[pos], Heap[j])) return; // Done swap(Heap, pos, j); pos = j; // Move down } } template <class Elem, class Comp> bool minheap<Elem, Comp>::insert(const Elem& val) { 2 if (n >= size) return false; // Heap is full int curr = n++; Heap[curr] = val; // Start at end of heap // Now sift up until curr's parent < curr while ((curr!=0) && (Comp::lt(Heap[curr], Heap[parent(curr)]))) { swap(Heap, curr, parent(curr)); curr = parent(curr); } return true; } template <class Elem, class Comp> bool minheap<Elem, Comp>::removemin(Elem& it) { if (n == 0) return false; // Heap is empty swap(Heap, 0, --n); // Swap max with last value if (n != 0) siftdown(0); // Siftdown new root val it = Heap[n]; // Return deleted value return true; } // Remove value at specified position template <class Elem, class Comp> bool minheap<Elem, Comp>::remove(int pos, Elem& it) { if ((pos < 0) || (pos >= n)) return false; // Bad pos swap(Heap, pos, --n); // Swap with last value while ((pos != 0) && (Comp::lt(Heap[pos], Heap[parent(pos)]))) swap(Heap, pos, parent(pos)); // Push up if large key siftdown(pos); // Push down if small key it = Heap[n]; return true; } 3 Lab 6 Soln 1) template <class Elem> BinNode<Elem>* convert(GTNode<Elem>* genroot) { BinNode<Elem>* btemp; if (genroot == NULL) return NULL; GTNode<Elem>* gtemp = genroot->leftmost_child(); btemp = new BinNodePtr<Elem>(genroot->value(), (BinNodePtr<Elem>*) (convert(gtemp)),(BinNodePtr<Elem>*)convert(genroot->right_sibling())); } 2) In the main program: GenTree<int> tree, tree2; tree2.newroot(10,tree.root(), tree2.root()); BN= (BinNodePtr<int>*)(convert<int>(tree2.root())); cout<<"Printing the new Binary Tree:"<<endl; preorder(BN);