Data structure and alogorithm

/** @file assg11-tests.cpp * @brief Unit tests for Assignment 11 binary trees * * @author Jane Programmer * @note cwid : 123 45 678 * @note class: COSC 2336, Summer 2020 * @note ide : Atom Text Editor 1.46.0 / build package / GNU gcc tools * @note assg : Assignment 11 * @date June 1, 2020 * * Assignment 11 BinaryTrees. Implement some missing member functions for a * BinaryTree ADT data structure. This file has catch2 unit tests you need to * test and implement the functions for your assignment. */ #define CATCH_CONFIG_MAIN #include "catch.hpp" #include "BinaryTree.hpp" using namespace std; /** test basic BinaryTree functions() functions. Just some general tests * of the BinaryTree implementation given to you, to make sure nothing * breaks while trying to add/implement new functionality to the BinaryTree. * Without insertion we can't really test much yet as we can create non-empty * trees initially. */ TEST_CASE("<basic BinaryTree> test basic BinaryTree functionality", "[class]") { // A new tree should be empty and have a size of 0 BinaryTree t; CHECK( t.size() == 0 ); CHECK( t.tostring() == "size: 0 items: [ ]\n" ); } /** test insert() member function */ /* uncomment the test cases 1 at a time. This test case tests implementation * of the insert() member function. TEST_CASE("<insert()> test insert() member function", "[member]") { BinaryTree t; // test insert into initially empty tree t.insert(10); CHECK( t.size() == 1 ); CHECK( t.tostring() == "size: 1 items: [ 10 ]\n" ); // insert left child on root node t.insert(5); CHECK( t.size() == 2 ); CHECK( t.tostring() == "size: 2 items: [ 5 10 ]\n" ); // insert right child on root node t.insert(15); CHECK( t.size() == 3 ); CHECK( t.tostring() == "size: 3 items: [ 5 10 15 ]\n" ); // insert a left and right on the children of root t.insert(3); t.insert(12); CHECK( t.size() == 5 ); CHECK( t.tostring() == "size: 5 items: [ 3 5 10 12 15 ]\n" ); // insert some more to grow height at least 5 t.insert(2); t.insert(1); t.insert(20); t.insert(30); t.insert(40); t.insert(13); CHECK( t.size() == 11 ); CHECK( t.tostring() == "size: 11 items: [ 1 2 3 5 10 12 13 15 20 30 40 ]\n" ); } */ /** test height() member function */ /* uncomment the test cases 1 at a time. This test case tests implementation * of the height() member function. TEST_CASE("<height()> test height() member function", "[member]") { BinaryTree t; // empty tre should have height 0 CHECK(t.height() == 0 ); // add root node and check heght t.insert(10); CHECK(t.height() == 1 ); // add child node, height becomes 2 t.insert(5); CHECK(t.height() == 2 ); // height should not change if add a right child t.insert(15); CHECK(t.height() == 2 ); // make tree unbalanced, add some big nodes down rith path t.insert(20); CHECK(t.height() == 3 ); t.insert(30); CHECK(t.height() == 4 ); t.insert(40); CHECK(t.height() == 5 ); t.insert(50); CHECK(t.height() == 6 ); // now adding nodes on left will not increase height unitll a subtree exceeds // height of 6 t.insert(4); CHECK(t.height() == 6 ); t.insert(3); CHECK(t.height() == 6 ); t.insert(2); CHECK(t.height() == 6 ); t.insert(1); CHECK(t.height() == 6 ); // one more on left path increase its height to 7 t.insert(0); CHECK(t.height() == 7 ); } */ /** test clear() member function */ /* uncomment the test cases 1 at a time. This test case tests implementation * of the clear() member function. TEST_CASE("<clear()> test height() member function", "[member]") { // create a tree to clear it. BinaryTree t; t.insert(10); t.insert(5); t.insert(15); t.insert(20); t.insert(30); t.insert(40); t.insert(50); t.insert(4); t.insert(3); t.insert(2); t.insert(1); t.insert(0); CHECK( t.size() == 12 ); CHECK(t.height() == 7 ); CHECK( t.tostring() == "size: 12 items: [ 0 1 2 3 4 5 10 15 20 30 40 50 ]\n" ); // now clear it t.clear(); CHECK( t.size() == 0 ); CHECK( t.height() == 0 ); CHECK( t.tostring() == "size: 0 items: [ ]\n" ); // test clear doesn't mess up for an already empty tree BinaryTree t2; t2.clear(); CHECK( t.size() == 0 ); CHECK( t.height() == 0 ); CHECK( t.tostring() == "size: 0 items: [ ]\n" ); // test clear works for tree cleared and only has a root node t.insert(42); CHECK( t.size() == 1 ); CHECK( t.height() == 1 ); CHECK( t.tostring() == "size: 1 items: [ 42 ]\n" ); t.clear(); CHECK( t.size() == 0 ); CHECK( t.height() == 0 ); CHECK( t.tostring() == "size: 0 items: [ ]\n" ); } */