C++ Assignment Using Visual Studio.
GraceMaze
Lab4BSTSkeletonMSVCVersion.zipLab 4 BST Skeleton MSVC Version/Lab 4 BST Skeleton MSVC Version.sdf
Lab 4 BST Skeleton MSVC Version/Lab 4 BST Skeleton MSVC Version.sln
Microsoft Visual Studio Solution File, Format Version 12.00 # Visual Studio 2013 VisualStudioVersion = 12.0.21005.1 MinimumVisualStudioVersion = 10.0.40219.1 Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "Lab 4 BST Skeleton MSVC Version", "Lab 4 BST Skeleton MSVC Version\Lab 4 BST Skeleton MSVC Version.vcxproj", "{AB1219E2-F9D0-4520-B8C2-0614EDC399BA}" EndProject Global GlobalSection(SolutionConfigurationPlatforms) = preSolution Debug|Win32 = Debug|Win32 Release|Win32 = Release|Win32 EndGlobalSection GlobalSection(ProjectConfigurationPlatforms) = postSolution {AB1219E2-F9D0-4520-B8C2-0614EDC399BA}.Debug|Win32.ActiveCfg = Debug|Win32 {AB1219E2-F9D0-4520-B8C2-0614EDC399BA}.Debug|Win32.Build.0 = Debug|Win32 {AB1219E2-F9D0-4520-B8C2-0614EDC399BA}.Release|Win32.ActiveCfg = Release|Win32 {AB1219E2-F9D0-4520-B8C2-0614EDC399BA}.Release|Win32.Build.0 = Release|Win32 EndGlobalSection GlobalSection(SolutionProperties) = preSolution HideSolutionNode = FALSE EndGlobalSection EndGlobal
Lab 4 BST Skeleton MSVC Version/Lab 4 BST Skeleton MSVC Version.v12.suo
Lab 4 BST Skeleton MSVC Version/Lab 4 BST Skeleton MSVC Version/BST.h
#pragma once #include <iostream> using namespace std; template <class T> class BinarySearchTree; template <class T> class TreeNode { private: T _item; TreeNode<T>* _left; TreeNode<T>* _right; int _height; public: TreeNode(T x) { _left = _right = NULL; _item = x; _height = 0; }; friend BinarySearchTree<T>; }; template <class T> class BinarySearchTree { private: int _size; TreeNode<T>* _root; void _printTree(int indent, TreeNode<T>*, bool withHeight); void _preOrderPrint(TreeNode<T>*); TreeNode<T>* _insert(TreeNode<T>* current, T x); TreeNode<T>* _rightRotation(TreeNode<T>*); TreeNode<T>* _leftRotation(TreeNode<T>*); void _destroySubTree(TreeNode<T>*); public: BinarySearchTree() { _root = NULL; _size = 0; } ~BinarySearchTree(); int size() { return _size; }; void insert(T); void printTree(bool withHeight = 1); void inOrderPrint(); void postOrderPrint(); void preOrderPrint(); T searchMax() ; T searchMin(); bool exist(T x); T successor(T); }; #include "BST.hpp"
Lab 4 BST Skeleton MSVC Version/Lab 4 BST Skeleton MSVC Version/BST.hpp
#pragma once #ifndef BSTHPP #define BSTHPP #include "BST.h" template <class T> TreeNode<T>* BinarySearchTree<T>::_insert(TreeNode<T>* current, T x) { if (current->_item > x) { if (current->_left) current->_left = _insert(current->_left, x); else { current->_left = new TreeNode<T>(x); } } else if (x > current->_item) { if (current->_right) current->_right = _insert(current->_right, x); else { current->_right = new TreeNode<T>(x); } } else return current; return current; } template <class T> void BinarySearchTree<T>::insert(T x) { if (_root == NULL) _root = new TreeNode<T>(x); else _root = _insert(_root, x); } template <class T> bool BinarySearchTree<T>::exist(T x) { return false; } template <class T> T BinarySearchTree<T>::searchMax() { return T(); } template <class T> T BinarySearchTree<T>::searchMin() { return T(); } template <class T> T BinarySearchTree<T>::successor(T x) { return T(); } template <class T> TreeNode<T>* BinarySearchTree<T>::_leftRotation(TreeNode<T>* node) { return NULL; } template <class T> TreeNode<T>* BinarySearchTree<T>::_rightRotation(TreeNode<T>* node) { return NULL; } template <class T> void BinarySearchTree<T>::printTree(bool withHeight) { _printTree(0, _root, withHeight); } template <class T> void BinarySearchTree<T>::preOrderPrint() { _preOrderPrint(_root); cout << endl; } template <class T> void BinarySearchTree<T>::_preOrderPrint(TreeNode<T>* node) { if (!node) return; cout << node->_item << " "; _preOrderPrint(node->_left); _preOrderPrint(node->_right); } template <class T> void BinarySearchTree<T>::inOrderPrint() { } template <class T> void BinarySearchTree<T>::postOrderPrint() { } template <class T> void BinarySearchTree<T>::_printTree(int indent, TreeNode<T>* node, bool withHeight) { if (!node) return; if (node->_right) _printTree(indent + 2, node->_right, withHeight); for (int i = 0; i < indent; i++) cout << " "; cout << node->_item; if (withHeight) cout << "(h=" << node->_height << ")"; cout << endl; if (node->_left) _printTree(indent + 2, node->_left, withHeight); }; template <class T> void BinarySearchTree<T> ::_destroySubTree(TreeNode<T>* node) { if (node->_left) _destroySubTree(node->_left); if (node->_right) _destroySubTree(node->_right); delete node; } template <class T> BinarySearchTree<T> :: ~BinarySearchTree() { if (_root) _destroySubTree(_root); } #endif
Lab 4 BST Skeleton MSVC Version/Lab 4 BST Skeleton MSVC Version/Debug/Lab 4 BST Skeleton MSVC Version.log
Build started 9/6/2018 9:04:03 AM. Build succeeded. Time Elapsed 00:00:00.01
Lab 4 BST Skeleton MSVC Version/Lab 4 BST Skeleton MSVC Version/Lab 4 BST Skeleton MSVC Version.vcxproj
Debug Win32 Release Win32 {AB1219E2-F9D0-4520-B8C2-0614EDC399BA} Lab4BSTSkeletonMSVCVersion Application true v120 MultiByte Application false v120 true MultiByte Level3 Disabled true true Console Level3 MaxSpeed true true true true true true
Lab 4 BST Skeleton MSVC Version/Lab 4 BST Skeleton MSVC Version/Lab 4 BST Skeleton MSVC Version.vcxproj.filters
{4FC737F1-C7A5-4376-A066-2A32D752A2FF} cpp;c;cc;cxx;def;odl;idl;hpj;bat;asm;asmx {93995380-89BD-4b04-88EB-625FBE52EBFB} h;hh;hpp;hxx;hm;inl;inc;xsd {67DA6AB6-F800-4c08-8B7A-83BB121AAD01} rc;ico;cur;bmp;dlg;rc2;rct;bin;rgs;gif;jpg;jpeg;jpe;resx;tiff;tif;png;wav;mfcribbon-ms Header Files Header Files Source Files
Lab 4 BST Skeleton MSVC Version/Lab 4 BST Skeleton MSVC Version/main.cpp
#include "BST.h" void testInsertion1(bool printWithHeight = true); void testInsertion2(bool printWithHeight = true); void testSuccessor(); void testSearchMinMax(); void testExist(); int main() { // uncomment the following code for your testing testInsertion1(true); //testSearchMinMax(); //testExist(); //testSuccessor(); //testInsertion2(true); } void testInsertion1(bool printWithHeight) { cout << "Insertion Test 1" << endl; int array[] = { 7, 3, 1, 0, 2, 5, 4, 6, 11, 9, 8, 10, 13, 12, 14 }; BinarySearchTree<int> bsti; for (int i = 0; i < 15; i++) bsti.insert(array[i]); bsti.printTree(false); cout << endl << endl; bsti.printTree(printWithHeight); cout << endl << endl; cout << "The size of the tree is " << bsti.size() << endl; cout << "Pre-order Traversal:" << endl; bsti.preOrderPrint(); cout << "In-order Traversal:" << endl; bsti.inOrderPrint(); cout << "Post-order Traversal:" << endl; bsti.postOrderPrint(); cout << endl << endl; } void testExist() { cout << "Exist Test" << endl; BinarySearchTree<int> bsti; cout << "Numbers inserted in the tree: "; for (int i = 0; i < 11; i++) { cout << i * 6 << " "; bsti.insert(i * 6); } // bsti.printTree(false); cout << endl << endl; for (int i = 0; i < 70; i += 8) cout << "The number " << i << (bsti.exist(i) ? " exists " : " does not exist ") << "in the tree" << endl; cout << endl << endl; } void testInsertion2(bool printWithHeight) { cout << "Insertion Test 2" << endl; cout << "The tree shape should be the same as Test 1" << endl; cout << "if you have done the balancing correctly." << endl; BinarySearchTree<int> bsti; for (int i = 0; i < 15; i++) bsti.insert(i); bsti.printTree(printWithHeight); cout << endl << endl; cout << "The size of the tree is " << bsti.size() << endl; cout << "Pre-order Traversal:" << endl; bsti.preOrderPrint(); cout << "In-order Traversal:" << endl; bsti.inOrderPrint(); cout << "Post-order Traversal:" << endl; bsti.postOrderPrint(); cout << endl << endl; } void testSearchMinMax() { cout << "Search Min/Max Test" << endl; int array[] = { 7, 3, 1, 0, 2, 5, 4, 6, 11, 9, 8, 10, 13, 12, 14 }; BinarySearchTree<int> bsti; for (int i = 0; i < 15; i++) bsti.insert(array[i]); cout << "The minimum number in the tree is " << bsti.searchMin() << endl; cout << "The maximum number in the tree is " << bsti.searchMax() << endl; cout << endl; } void testSuccessor() { cout << "Successor Test" << endl; BinarySearchTree<int> bsti; cout << "Numbers inserted in the tree: "; for (int i = 0; i < 11; i++) { cout << i * 7 << " "; bsti.insert(i * 7); } // bsti.printTree(false); cout << endl << endl; for (int i = 0; i < 70; i += 10) cout << "The successor of " << i << " in the BST is " << bsti.successor(i) << endl; cout << endl << endl; }
