C++ Program Please create a C++ program that demonstrates use of a binary tree.
ID: 665938 • Letter: C
Question
C++ Program
Please create a C++ program that demonstrates use of a binary tree. Details below:
There will be two users. The program will prompt the users to take turns entering values into the binary tree. More details below:
First, the program should ask the users for a pre-determined depth to the tree.
So, if the user enters a node depth of 2 for example, you would tell the program to continue until a node depth of 2 had been reached, which would be a total of 21+20 = 3 nodes.
Second, the program will populate the binary tree by prompting the two users to enter values between 1 and 100.
If a value outside of 1-100 is chosen, the user should be prompted to re-choose a number between 1-100. Also, the same number cannot be entered twice. So if a user attempts to enter a number that has already been entered, they must be prompted to try another number within the 1-100 range.
Next, the program should always display each user's previously entered values.
Once the binary tree is fully populated based on the pre-determined node depth value, the program should automatically delete the root node (the node at the top and center of your tree).
Below is a visual representation of how the program should operate
Please, do not use any binary search tree function libraries for this project. Thanks.
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.