Programming Exercise 19-1: Analysis of Algorithms

Write the definition of the function nodeCount that returns the number of nodes in the binary tree. Add this function to the class binaryTreeType and create a program to test this function.

task:

nodeCount implemented

1

0 out of 1 checks passed. Review the results below for more details.

Checks

Unit TestIncomplete

Method nodeCount implemented

Build Status

Build Failed

Build Output

In file included from /root/sandbox63dec8a9/binarySearchTree.h:5:0, from /root/sandbox63dec8a9t-test-51979c88.cpp:2: /root/sandbox63dec8a9/binaryTree.h:19:1: error: expected unqualified-id before '...' token ... ^~~ In file included from /usr/include/gtest/gtest.h:1929:0, from /root/sandbox63dec8a9t-test-51979c88.cpp:1: /root/sandbox63dec8a9t-test-51979c88.cpp: In member function 'virtual void Tree_1_Test::TestBody()': /root/sandbox63dec8a9t-test-51979c88.cpp:6:22: error: 'class bSearchTreeType' has no member named 'treeNodeCount'; did you mean 'nodeCount'? ASSERT_EQ(treeRoot.treeNodeCount(), 0); ^ /root/sandbox63dec8a9t-test-51979c88.cpp:6:3: error: template argument 1 is invalid ASSERT_EQ(treeRoot.treeNodeCount(), 0); ^ /root/sandbox63dec8a9t-test-51979c88.cpp:6:22: error: 'class bSearchTreeType' has no member named 'treeNodeCount'; did you mean 'nodeCount'? ASSERT_EQ(treeRoot.treeNodeCount(), 0); ^ /root/sandbox63dec8a9t-test-51979c88.cpp:10:22: error: 'class bSearchTreeType' has no member named 'treeNodeCount'; did you mean 'nodeCount'? ASSERT_EQ(treeRoot.treeNodeCount(), 3); ^ /root/sandbox63dec8a9t-test-51979c88.cpp:10:3: error: template argument 1 is invalid ASSERT_EQ(treeRoot.treeNodeCount(), 3); ^ /root/sandbox63dec8a9t-test-51979c88.cpp:10:22: error: 'class bSearchTreeType' has no member named 'treeNodeCount'; did you mean 'nodeCount'? ASSERT_EQ(treeRoot.treeNodeCount(), 3); ^ /root/sandbox63dec8a9t-test-51979c88.cpp:15:22: error: 'class bSearchTreeType' has no member named 'treeNodeCount'; did you mean 'nodeCount'? ASSERT_EQ(treeRoot.treeNodeCount(), 6); ^ /root/sandbox63dec8a9t-test-51979c88.cpp:15:3: error: template argument 1 is invalid ASSERT_EQ(treeRoot.treeNodeCount(), 6); ^ /root/sandbox63dec8a9t-test-51979c88.cpp:15:22: error: 'class bSearchTreeType' has no member named 'treeNodeCount'; did you mean 'nodeCount'? ASSERT_EQ(treeRoot.treeNodeCount(), 6); ^ /root/sandbox63dec8a9t-test-51979c88.cpp:19:21: error: 'class bSearchTreeType' has no member named 'treeNodeCount'; did you mean 'nodeCount'? ASSERT_EQ(treeRoot.treeNodeCount(), 7); ^ /root/sandbox63dec8a9t-test-51979c88.cpp:19:2: error: template argument 1 is invalid ASSERT_EQ(treeRoot.treeNodeCount(), 7); ^ /root/sandbox63dec8a9t-test-51979c88.cpp:19:21: error: 'class bSearchTreeType' has no member named 'treeNodeCount'; did you mean 'nodeCount'? ASSERT_EQ(treeRoot.treeNodeCount(), 7); ^ In file included from /root/sandbox63dec8a9t-test-51979c88.cpp:2:0: /root/sandbox63dec8a9/binarySearchTree.h: In instantiation of 'void bSearchTreeType::insert(const elemType&) [with elemType = int]': /root/sandbox63dec8a9t-test-51979c88.cpp:7:20: required from here /root/sandbox63dec8a9/binarySearchTree.h:87:15: error: 'class bSearchTreeType' has no member named 'root' if (this->root == nullptr) ~~~~~~^~~~ /root/sandbox63dec8a9/binarySearchTree.h:88:15: error: 'class bSearchTreeType' has no member named 'root' this->root = newNode; ~~~~~~^~~~ /root/sandbox63dec8a9/binarySearchTree.h:91:25: error: 'class bSearchTreeType' has no member named 'root' current = this->root; ~~~~~~^~~~ make[2]: *** [CMakeFiles/runTests.dirt-test-51979c88.cpp.o] Error 1 make[1]: *** [CMakeFiles/runTests.dir/all] Error 2 make: *** [all] Error 2

Test Contents

bSearchTreeType treeRoot; TEST(Tree,1) { ASSERT_EQ(treeRoot.treeNodeCount(), 0); treeRoot.insert(1); treeRoot.insert(434); treeRoot.insert(245); ASSERT_EQ(treeRoot.treeNodeCount(), 3); treeRoot.insert(543); treeRoot.insert(5563); treeRoot.insert(324532); ASSERT_EQ(treeRoot.treeNodeCount(), 6); treeRoot.insert(3245332); ASSERT_EQ(treeRoot.treeNodeCount(), 7); } 

Run checks

binaryTree.h:

#include

using namespace std;

template

struct nodeType

{

elemType info;

nodeType *lLink;

nodeType *rLink;

};

template

class binaryTreeType

{

public:

int nodeCount(nodeType *p) const;

// Returns the number of nodes in the binary tree.

// Postcondition: Returns the number of nodes.

...

};

template

int binaryTreeType::nodeCount(nodeType *p) const

{

if (p == NULL)

return 0;

else

return 1 + nodeCount(p->lLink) + nodeCount(p->rLink);

}

main.cpp:

#include

#include "binaryTreeType.h"

#include "gtest/gtest.h"

TEST(Tree, NodeCount)

{

binaryTreeType tree;

ASSERT_EQ(tree.nodeCount(tree.root), 0);

tree.insert(1);

tree.insert(2);

tree.insert(3);

ASSERT_EQ(tree.nodeCount(tree.root), 3);

tree.insert(4);

tree.insert(5);

ASSERT_EQ(tree.nodeCount(tree.root), 5);

}

int main(int argc, char **argv)

{

::testing::InitGoogleTest(&argc, argv);

return RUN_ALL_TESTS();

}

\}; class binaryTreeType \{ public: int nodeCount (nodeType*p) const; // Returns the number of nodes in the binary // Postcondition: Returns the number of nodes \} ; int binaryTreeType: :nodeCount (nodeType(p==NULL) return ; else return 1+ nodeCount (p>1 Link )+ nodeCount (p Programming Exercise 19-1