C++ Program *MUST FOLLOW DIRECTIONS* Assignment Objectives: To create a C++ comp
ID: 665491 • Letter: C
Question
C++ Program
*MUST FOLLOW DIRECTIONS*
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 of3had 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 of3again 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 & be sure to follow the directions exactly. Example game (above) demonstrates how the program/game should work. Please include an example output from your program as well as any #includes. Thanks!
More points can be awarded if needed!!
Explanation / Answer
import java.io.*;
import java.util.*;
class BNode {
String data;
BNode left,right,parent;
int hi;
public BNode(){
this(null,null,null,null,0);
}
public BNode(String e,BNode p,BNode l,BNode r,int h){
data=e;
left=l; right=r; parent=p;
hi=h;
}
}
class LinkedBST {
BNode root=new BNode();
BNode currentNode;
int size=0;
public LinkedBST(){
root.data=null; root.hi=0;
size=0;
}
public LinkedBST(String a){
root.data=a;
root.hi=1;
BNode Left=new BNode(); BNode Right=new BNode();
root.left=Left; root.right=Right;
Left.parent=root; Right.parent=root;
size++;
}
boolean IsExternal(BNode n){
return (n.left==null && n.right==null);
}
int SubTreeSize(BNode n){
if (IsExternal(n)) return 0;
else return 1+SubTreeSize(n.left)+SubTreeSize(n.right);
}
boolean op(String a,String b){
int x=a.compareTo(b) ;
if (x<0) return true;
else return false;
}
BNode search(String o){
currentNode=root;
while (!IsExternal(currentNode)){
if (o.compareTo(currentNode.data)==0) {return currentNode; }
else if (op(o,currentNode.data)) { currentNode=currentNode.left; }
else { currentNode=currentNode.right; }
}
if (currentNode.data!=o) { return null; }
else return currentNode;
}
int height(BNode x){ if (x==null) return 0; return x.hi; }
void updatehieght(BNode x) { if (x==null) return; else x.hi=Math.max(height(x.left),height(x.right))+1; }
int mod(int x){ if (x<0) return -1*x; else return 1*x; }
boolean Imbalance(BNode b){ if (mod(b.left.hi-b.right.hi)>=2) return true; else return false; }
BNode taller(BNode m){ return (height(m.right)<height(m.left))?m.left:m.right; }
void rotate(BNode z){
BNode y=taller(z);
BNode x=taller(y);
if (z.right==y && y.right==x) {
BNode temp=y.left;
if (z.parent==null){
root=y;
y.parent=null;
y.left=z;
z.parent=y;
z.right=temp;
temp.parent=z;
updatehieght(z);
updatehieght(x);
updatehieght(y);
}
else{
if (z.parent.right==z) z.parent.right=y;
else if (z.parent.left==z) z.parent.left=y;
y.parent=z.parent;
y.left=z;
z.parent=y;
z.right=temp;
temp.parent=z;
updatehieght(z);
updatehieght(x);
updatehieght(y);
updatehieght(y.parent);
}
}
else if (z.left==y && y.left==x) {
BNode temp=y.right;
if (z.parent==null){
root=y;
y.parent=null;
y.right=z;
z.parent=y;
z.left=temp;
temp.parent=z;
updatehieght(z);
updatehieght(x);
updatehieght(y);
}
else {
if (z.parent.right==z) z.parent.right=y;
else if(z.parent.left==z) z.parent.left=y;
y.parent=z.parent;
y.right=z;
z.parent=y;
z.left=temp;
temp.parent=z;
updatehieght(z);
updatehieght(x);
updatehieght(y);
updatehieght(y.parent);
}
}
else if (z.right==y && y.left==x){
BNode temp1=x.left;
BNode temp2=x.right;
if (z.parent==null){
root=x;
x.parent=null;
x.left=z;
z.parent=x;
x.right=y;
y.parent=x;
z.right=temp1;
temp1.parent=z;
y.left=temp2;
temp2.parent=y;
updatehieght(z);
updatehieght(y);
updatehieght(x);
}
else{
if (z.parent.right==z) z.parent.right=x;
else if (z.parent.left==z) z.parent.left=x;
x.parent=z.parent;
x.left=z;
z.parent=x;
x.right=y;
y.parent=x;
z.right=temp1;
temp1.parent=z;
y.left=temp2;
temp2.parent=y;
updatehieght(z);
updatehieght(y);
updatehieght(x);
updatehieght(x.parent);
}
}
else if (z.left==y && y.right==x){
BNode temp1=x.left;
BNode temp2=x.right;
if (z.parent==null){
root=x;
x.parent=null;
x.left=y;
y.parent=x;
x.right=z;
z.parent=x;
y.right=temp1;
temp1.parent=y;
z.left=temp2;
temp2.parent=z;
updatehieght(y);
updatehieght(z);
updatehieght(x);
}
else {
if (z.parent.left==z) z.parent.left=x;
else if (z.parent.right==z) z.parent.right=x;
x.parent=z.parent;
x.left=y;
y.parent=x;
x.right=z;
z.parent=x;
y.right=temp1;
temp1.parent=y;
z.left=temp2;
temp2.parent=z;
updatehieght(z);
updatehieght(y);
updatehieght(x);
updatehieght(x.parent);
}
}
}
void insert(String n){
BNode temp=new BNode();
temp=root;
while (!IsExternal(temp)){
if (op(n,temp.data)) temp=temp.left;
else temp=temp.right;
}
temp.data=n;
temp.hi=1;
BNode left=new BNode(); BNode right=new BNode();
temp.left=left; temp.right=right;
left.parent=temp; right.parent=temp;
size++;
BNode r=temp;
while (temp.parent!=null){
updatehieght(temp.parent);
temp=temp.parent;
}
while (r!=null){
if (Imbalance(r)==true){
rotate(r);
break;
}
r=r.parent;
}
}
void delete1(BNode b) {
BNode r=b.parent;
size--;
if (b.left.data==null && b.right.data==null) {
b.data=null;
b.left=null;
b.right=null;
while (b.parent!=null) {
updatehieght(b.parent);
b=b.parent;
}
while (r!=null){
if (Imbalance(r)==true){
rotate(r);
break;
}
r=r.parent;
}
}
else if (!IsExternal(b.right) && b.left.data==null) {
b.right.parent=b.parent;
if (b.parent.right==b) b.parent.right=b.right;
else b.parent.left=b.right;
while (b.parent!=null) {
updatehieght(b.parent);
b=b.parent;
}
while (r!=null){
if (Imbalance(r)==true){
rotate(r);
break;
}
r=r.parent;
}
}
else if (!IsExternal(b.left) && b.left.data==null) {
b.left.parent=b.parent;
if (b.parent.left==b) b.parent.left=b.left;
else b.parent.right=b.left;
while (b.parent!=null) {
updatehieght(b.parent);
b=b.parent;
}
while (r!=null){
if (Imbalance(r)==true){
rotate(r);
break;
}
r=r.parent;
}
}
}
void delete(String m) {
if (search(m)==null) {}
else {
BNode b=search(m);
BNode r=b.parent;
size--;
if (b.left.data==null && b.right.data==null) {
b.data=null;
b.left=null;
b.right=null;
while (b.parent!=null) {
updatehieght(b.parent);
b=b.parent;
}
while (r!=null){
if (Imbalance(r)==true){
rotate(r);
break;
}
r=r.parent;
}
}
else if (!IsExternal(b.right) && b.left.data==null) {
b.right.parent=b.parent;
if (b.parent.right==b) b.parent.right=b.right;
else b.parent.left=b.right;
while (b.parent!=null) {
updatehieght(b.parent);
b=b.parent;
}
while (r!=null){
if (Imbalance(r)==true){
rotate(r);
break;
}
r=r.parent;
}
}
else if (!IsExternal(b.left) && b.left.data==null) {
b.left.parent=b.parent;
if (b.parent.left==b) b.parent.left=b.left;
else b.parent.right=b.left;
while (b.parent!=null) {
updatehieght(b.parent);
b=b.parent;
}
while (r!=null){
if (Imbalance(r)==true){
rotate(r);
break;
}
r=r.parent;
}
}
else {
size++;
BNode currentNode1=b.left;
while(!IsExternal(currentNode1)){
currentNode1=currentNode1.right;
}
String t=currentNode1.parent.data;
currentNode1.parent.data=b.data;
b.data=t;
delete1(currentNode1.parent);
}
}
}
void printtree(BNode n){
if (!IsExternal(n)){
printtree(n.left);
System.out.print("the element is "+n.data+"----");
System.out.println("its hieght is "+n.hi);
printtree(n.right);
}
}
int winner(BNode n){
if (n != null && n.left == null && n.right == null) return 1;
return 0;
}
}
class run{
public static void main(String[] args) throws IOException{
Scanner sc = new Scanner(System.in);
System.out.print("Please enter the node depth you wish the game to g to : ");
int n = sc.nextInt();
int level = Math.pow(2,n);
int[] l_1 = new int[level/2];
int[] l_2 = new int[level/2];
int size = 0;
boolean start = false;
LinkedBST bst;
while (level > 0){
System.out.println("Player 1's numbers : ");
for (int i = 0; i < (size+1)/2; i++){
System.out.print(l_1[i]+", ")
}
System.out.println("Player 2's numbers : ");
for (int i = 0; i < size/2; i++){
System.out.print(l_2[i]+", ")
}
size++;
if (size % 2 == 0){
System.out.print("Player "+1+" Please insert your next number into tree ");
n = sc.nextInt();
l_1[size] = n;
}
else{
System.out.print("Player "+2+" Please insert your next number into tree ");
n = sc.nextInt();
l_2[size] = n;
}
if (start == false){
start = true;
bst = new LinkedBST(n);
}
else{
bst.insert(n);
}
level--;
bst.printtree(bst.root);
}
bst.delete(bst.root);
int p_1 = 0;
int p_2 = 0;
for (int i = 0; i < l_1.length; i++){
p_1 += bst.winner(l_1[i]);
p_2 += bst.winner(l_2[i]);
}
System.out.println("Player 1's Terminal Nodes : "+p_1);
System.out.println("Player 2's Terminal Nodes : "+p_2);
if (p_1 > p_2)
System.out.println(" Player 2 Wins.... ")
else if (p_2 > p_1)
System.out.println(" Player 1 Wins.... ")
else
System.out.println(" The game is a Tie !! ")
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.