/* * * @ Javier Felipe Toribio 2019-08-25 * * challenge by John Wells * * Binary Tree Details * * Input a list of integers into a sorted * binary tree. Each integer must be unique * (duplicates can be ignored) and, as it is * seen, it gets placed. The first number is * the root. The second number is either the * left or right leaf with lower numbers * going left and higher going right. Each * additional number continues to be inserted * as a leaf after traversing the tree to * it's insertion point. * * Once the tree is complete, output three * details of the tree: total nodes, maximum * height, and balanced vs. unbalanced. The * nodes is the number of integers read and * inserted. If your input was the numbers * one, two, three, and four, the root is one * and it's right node is two. Two's right * node is three and three's right node is * four. This gives a height of four for that * tree. A balanced tree has a difference of * height of each node's subtrees of zero or * one so node three in the previous tree was * balanced as it's left side was zero and * it's left side was zero and it's right was * one. Node two is unbalanced as it's left * is zero and it's right is two. Any * unbalanced subtree makes it's parent * unbalanced. * * Examples * * Input: * 1 2 3 4 * * Output: * 4 nodes, height of 4, unbalanced * * Input: * 10 5 15 3 7 12 18 * * Output: * 7 nodes, height of 3, balanced * * Input: * 10 5 15 3 18 * * Output: * 5 nodes, height of 3, balanced * * Input: * 10 12 5 15 3 18 * * Output: * 6 nodes, height of 4, unbalanced * * Input: * 10 13 5 15 3 18 8 11 4 14 17 1 2 12 9 * * Output: * 15 nodes, height of 5, balanced * * * * INPUT: Insert integer values. * If input is empty, default * values will be used * */ #include #include #include #include #include #include #include #include using namespace std; /* * Class node */ class Node { public: int *value; Node *left; Node *right; /* * Constructor */ Node() : value(nullptr), left(nullptr), right(nullptr) {} /* destructor */ ~Node() { delete(value); delete(left); delete(right); } }; /* * Class Tree */ class Tree { private: Node * root; int height; int numNodes; /* * Revise heights to check if tree is * balanced * If difference between left and right * heights is greater than 1 return -1; * Otherwise, return node height. */ int reviseHeights(Node **node) { int leftHeight, rightHeight; if(*node == nullptr) return 0; if((leftHeight = reviseHeights(&(*node)->left)) == -1) return -1; if((rightHeight = reviseHeights(&(*node)->right)) == -1) return -1; if(abs(leftHeight - rightHeight) > 1) return -1; return max(leftHeight, rightHeight) + 1; } /* * Insert value and calculate height */ void insert(const int value, Node ** tree, int height) { if(*tree == nullptr) { *tree = new Node(); (*tree)->value = new int(value); (*tree)->left = nullptr; (*tree)->right = nullptr; numNodes++; if(height > this->height) this->height = height; } else if(value < * (*tree)->value) { insert(value, &(*tree)->left,height+1); } else if(value > * (*tree)->value) { insert(value, &(*tree)->right,height+1); } else { /* Ignore duplicated values */ } } public: /* * Constructor */ Tree() : root(nullptr), height(0), numNodes(0) {} /* * Insert value in tree */ void insert(const int value) { insert(value,&root,0); } /* * Check if the tree is balanced */ bool isBalanced() { return reviseHeights(&root) != -1; } /* * Get number of nodes */ inline int getNumberOfNodes() { return numNodes; } /* * Get height */ inline int getHeight() { return height + 1; } /* * Report tree values */ void report() { string balStr = isBalanced() ?"Balanced" : "Unbalanced"; cout << "Tree report" << endl << "===========" << endl << "Number of nodes : " << numNodes << endl << "Height : " << height+1 << endl << "Balanced ? : " << balStr << endl; } }; // Tree class /* * Convert input data string to vector of * integers */ void stringToVector(string s, vector & values) { istringstream is(s); vector v((istream_iterator(is)), istream_iterator()); for(string val : v) values.push_back(stoi(val)); } /* * Obtain numeric values from input. * If input is empty, use default values */ void getInput(vector & values) { cout << "Insert integer values" << endl; string s; getline(cin, s); if(s.size()>0) { stringToVector(s,values); } else { cout << "Empty input." << " Using default values" << endl << endl; stringToVector(string("7 9 5 3 1"),values); } cout << "Values: " << endl << endl; for(int i : values) cout << " " << i; cout << endl << endl; } /* * Insert values in tree and show report */ void createTree(Tree **tree,vector values){ *tree = new Tree(); for(int value : values) (*tree)->insert(value); (*tree)->report(); } /* test code */ void testCases(); /* * MAIN PROGRAM */ int main(int argc, char *argv[]) { Tree * tree = nullptr; vector values = vector(); /* Create tree with user input */ getInput(values); createTree(&tree,values); delete(tree); /* Check test cases */ testCases(); return 0; } /* * Test SW with cases */ void testCases() { struct Case { string input; int numNodes; int height; bool isBalanced; }; const struct Case tests[] = { {string("1 2 3 4"),4,4,false}, {string("10 5 15 3 7 12 18"),7,3,true}, {string("10 5 15 3 18"),5,3,true}, {string("10 12 5 15 3 18"),6,4,false}, {string("10 13 5 15 3 18 8 11 4 14 17 1 2 12 9"),15,5,true}}; string separator1 = string(42,'='); string separator2 = string(42,'-'); cout << endl << endl << endl; cout << separator1 << endl; cout << "Test cases" << endl; cout << separator1 << endl; for(Case test : tests) { Tree * tree = nullptr; vector values = vector(); stringToVector(test.input,values); cout << endl << test.input << endl << endl; createTree(&tree,values); assert(tree->getNumberOfNodes() == test.numNodes); assert(tree->getHeight() == test.height); assert(tree->isBalanced() == test.isBalanced); delete(tree); cout << endl << separator2 << endl; } }

[challenge] binary tree details