C++ Program Assignment Objectives: To create a C++ computer program that is a ga

Question

C++ Program

Assignment Objectives: To create a C++ computer program that is a game that bases itself upon binary trees. Your C++ program must satisfy all requirements of the game given below.

Binary Tree Terminal Node Game Requirements

Number of Players: 2

The premise of this game is two people taking turns populating a binary tree with numbers that are within a fixed range of 1-100. As each player inputs the number they wish to add to the tree each turn, the program will populate the binary tree. At the end of the game, the person with the most terminal nodes (the nodes at the bottom of the binary tree with no children) wins!

In order to ensure the tree is perfectly balanced at the end of the game, before the game begins, a pre-determined depth to the tree must be given by a user. So, if you wanted to play a game that used a tree of a node depth of 3 for example, you would tell the program before the game started to play until a node depth of 3 had been reached, which would be a total of 22+21+20 = 7 nodes.

Since there will always be an odd amount of nodes in a balanced binary tree, and the players will end up inserting an even amount of numbers, the game will automatically delete the root node (the node at the top and center of your tree) at the end of the game in order to balance the tree.

Because of the players going over the amount of nodes needed for a balanced tree by one node, the game must be allowed to run for (let’s use a node depth of 3 again as an example) 22+21+20+1 = 8 node insertions.

The same number cannot be entered twice. So if a player attempts to enter a number that has already been entered, they must be prompted to try another number within the 1-100 range.

You must display the numbers that each player has entered to the players at all times. How you precisely decide to display this is up to you.

The point of making this game is to demonstrate how to program a proper binary tree. The tasks of inserting (putting the nodes into the tree one at a time), navigating (navigating the tree once the game is over to flag the terminal nodes for each player), and deleting (deleting the root node and making sure the tree is in order after the deletion) are all demonstrated in the implementation of this game. Please, do not use any binary search tree function libraries for this project.  

Explanation / Answer

/* Binary Tree */ #include #include #include #include using namespace std; struct Tree { char data; Tree *left; Tree *right; Tree *parent; }; Tree* lookUp(struct Tree *node, char key) { if(node == NULL) return node; if(node->data == key) return node; else { if(node->data right, key) ; else return lookUp(node->left, key); } } Tree* leftMost(struct Tree *node) { if(node == NULL) return NULL; while(node->left != NULL) node = node->left; return node; } struct Tree *newTreeNode(int data) { Tree *node = new Tree; node->data = data; node->left = NULL; node->right = NULL; node->parent = NULL; return node; } struct Tree* insertTreeNode(struct Tree *node, int data) { static Tree *p; Tree *retNode; //if(node != NULL) p = node; if(node == NULL) { retNode = newTreeNode(data); retNode->parent = p; return retNode; } if(data data ) { p = node; node->left = insertTreeNode(node->left,data); } else { p = node; node->right = insertTreeNode(node->right,data); } return node; } void isBST(struct Tree *node) { static int lastData = INT_MIN; if(node == NULL) return; isBST(node->left); /* check if the given tree is BST */ if(lastData data) lastData = node->data; else { cout right); } int maxDepth(struct Tree *node) { if(node == NULL || (node->left == NULL && node->right == NULL)) return 0; int leftDepth = maxDepth(node->left); int rightDepth = maxDepth(node->right); return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1; } int minDepth(struct Tree *node) { if(node == NULL || (node->left == NULL && node->right == NULL)) return 0; int leftDepth = minDepth(node->left); int rightDepth = minDepth(node->right); return leftDepth left; return node; } /* Tree Maximum */ Tree* maxTree(struct Tree *node) { while(node->right) node = node -> right; return node; } /* In Order Successor - a node which has the next higher key */ Tree *succesorInOrder(struct Tree *node) { /* if the node has right child, seccessor is Tree-Minimum */ if(node->right != NULL) return minTree(node->right); Tree *y = node->parent; while(y != NULL && node == y->right) { node = y; y = y->parent; } return y; } /* In Order Predecessor - a node which has the next lower key */ Tree *predecessorInOrder(struct Tree *node) { /* if the node has left child, predecessor is Tree-Maximum */ if(node->left != NULL) return maxTree(node->left); Tree *y = node->parent; /* if it does not have a left child, predecessor is its first left ancestor */ while(y != NULL && node == y->left) { node = y; y = y->parent; } return y; } void reverseOrderPrint(struct Tree *node) { if(node == NULL) return; if(node->left == NULL && node->right == NULL) { cout left == q || node->right == p || node->right == q) return node; left = lowestCommonAncestor(node->left,p,q); right = lowestCommonAncestor(node->right, p,q); if(left && right) return node; else return (left) ? left : right; } void clear(struct Tree *node) { if(node != NULL) { clear(node->left); clear(node->right); delete node; } } /* print tree in order */ /* 1. Traverse the left subtree. 2. Visit the root. 3. Traverse the right subtree. */ void printTreeInOrder(struct Tree *node) { if(node == NULL) return; printTreeInOrder(node->left); cout left); printTreePostOrder(node->right); cout right == NULL) { cout right == NULL) { path[level] = node->data; for(int i = 0; i data != r2->data) return false; return (matchTree(r1->left, r2->left) && matchTree(r1->right, r2->right)); } bool subTree(Tree *r1, Tree *r2) { /*Big tree empty and subtree not found */ if(r1 == NULL) return false; if(r1->data == r2->data) if(matchTree(r1, r2)) return true; return (subTree(r1->left, r2) || subTree(r1->right, r2)); } bool isSubTree(Tree *r1, Tree *r2) { /* Empty tree is subtree */ if(r2 == NULL) return true; else return subTree(r1, r2); } /* change a tree so that the roles of the left and right hand pointers are swapped at every node */ void mirror(Tree *r) { if(r == NULL) return; Tree *tmp; mirror(r->left); mirror(r->right); /* swap pointers */ tmp = r->right; r->right = r->left; r->left = tmp; } /* create a new tree from a sorted array */ Tree *addToBST(char arr[], int start, int end) { if(end data = arr[mid]; r->left = addToBST(arr, start, mid-1); r->right = addToBST(arr, mid+1, end); return r; } Tree *createMinimalBST(char arr[], int size) { return addToBST(arr,0,size-1); } /* Breadth first traversal using queue */ void BreadthFirstTraversal(Tree *root) { if (root == NULL) return; deque queue; queue.push_back(root); while (!queue.empty()) { Tree *p = queue.front(); cout left); if (p->right != NULL) queue.push_back(p->right); } cout left, elm, level+1); else return getLevel(node->right, elm, level+1); } /* This code prints out all nodes at the same depth (level) */ void BreadthFirst_LevelElement_Print (struct Tree *root, vector &v) { if(root == NULL) return; deque q; q.push_back(root); while(!q.empty()) { Tree *p = q.front(); int lev = getLevel(root, p->data, 0); v[lev].push_back(p->data); q.pop_front(); if(p->left) q.push_back(p->left); if(p->right)q.push_back(p->right); } return; } /* levelPrint() prints nodes at the same level This is simpler than the BreadthFirstTraversal(root) above It takes 2D vector with the same size of level (= MaxDepth+1) and fills elements as we traverse (preOrder) */ void levelPrint(struct Tree *node, vector&elm, int level) { if(node == NULL) return; // leaf nodes if(node->left == NULL && node->right == NULL) { elm[level].push_back(node->data); return; } // other nodes elm[level++].push_back(node->data); levelPrint(node->left, elm, level); levelPrint(node->right, elm, level); } /* find n-th max node from a tree */ void NthMax(struct Tree* t) { static int n_th_max = 5; static int num = 0; if(t == NULL) return; NthMax(t->right); num++; if(num == n_th_max) cout data); else oddVec.push_back(p->data); que.pop_front(); if(p->left) que.push_back(p->left); if(p->right) que.push_back(p->right); } cout

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.