Below is btree.cpp #include<iostream> using namespace std; class TNode { public:
ID: 3740919 • Letter: B
Question
Below is btree.cpp
#include<iostream>
using namespace std;
class TNode
{
public:
int val;
TNode(){}
TNode(int v){val = v;}
TNode * left;
TNode * right;
TNode * parent;
};
class BTree
{
public:
//constructors and destructor
BTree();
BTree(TNode *r);// initialize BTree with the root r. r is the only node.
BTree(const BTree & t); // copy constructor
BTree(const int *p, const int n);// similar to the copy constructor, but your input is of the array form.
// input is given an array that denotes a tree that uses up to n slots. The size of the tree is not given directly as input.
// the array is pointed by p and has size n, where p[0] is used to store the empty symbol.
//the function converts the array representation into a linked-list representation, i.e. BTree
~BTree();
int size;
TNode *root;
TNode * convertpos(int position);// find the pointer where the position points to
void add2left(TNode newnode, TNode *p); // you should new a node that copies newnode and then add to left of p
void add2right(TNode newnode, TNode *p);
void add2left(TNode newnode, int position);
void add2right(TNode newnode, int position);
void add2left(BTree newsubtree, int position); // you should create a separate new tree that copies
//newsubtree and then add to left of p
void add2right(BTree newsubtree, int position);
void removeleaf(int position); // should check if position is leaf
void removeleaf(TNode *p);
void swapnodes(TNode *n1, TNode *n2);//swap-the-values is fine
int * Toarray(int &n);// convert the BT into the array form. Determine what n should be, and new an array of size n+1, and store the empty symbol at array[0]. Convert the BT into the array form and retrun the array pointer. The size of the array will be given to the variable n.
void print_pre_order();// print the node as you traverse according to the order.
void print_in_order();
void print_post_order();
bool isValidBST(); // return whether this BT is a valid BST
};
bool isValidBT(const int *p, const int n);
//Determine whether the array forms a valid BT.
// the input format is the same as the above
int main()
{
return 0;
}
In this assignment, you are given several classes in the cpp file "BTree.cpp". Your task is to complete the implementation of the classes specified as below. You need to submit a single cpp file that contains everything about your source code. It must be compilable and executable. Do not submit things irrelevant (such as .exe) 1 Your Task You are given a class "TNode" that contains one integer value, and three pointers one to the parent, one to the left child, and one to the right child. You need to complete the class "BTree" and two other functions specified in the cpp file. Task 1: Write a function isValidBT that given inputs as a binary tree in the array form, and outputs whether the array forms a correct binary tree. The inputs contain a pointer p to an array and an integer n denoting the number of slots used in the array representation. Here the array has size n, and we use p0 to store the empty symbol for the binary tree as discussed in the class. For this representation, the tree has size n -1. Task 2: Implement the constructors (default and copy) of BTree, and the destructor. You need to make sure that the copy constructor makes a separate copy of the list In addition to the normal copy constructor, here we ask you to implement a special "copy constructor that takes input a binary tree of the array form. The inputs have the same format as Task 1, and you need to copy the binary tree, and convert the array form/to the pointer-based construction Task 3: Implement the function convertpos that takes input an integer position, and returns the TNode pointer that points to the position-th node in the tree. We discussed about how to do this in the class Task 4: Implement the add2left, add2right functions. The functionalities are just as the names Here you need to consider how to handle different input of positions, i.e. places that you want tExplanation / Answer
Code with comments:
#include <iostream>
#include <string>
using namespace std;
// Task 1:
bool isValidBT(const int *p, const int n);
class TNode
{
public:
int val;
TNode() {}
TNode(int v) { val = v; }
TNode * left;
TNode * right;
TNode * parent;
};
class BTree
{
// public members
public:
// Task 2:
// constructors and destructor
BTree();
// initialize BTree with the root r.
// r is the only node.
BTree(TNode *r);
// copy constructor
BTree(const BTree & t);
// similar to the copy constructor, but your
// input is of the array form.
// input is given an array that denotes a tree
// that uses up to n slots. The size of the tree
// is not given directly as input.
// the array is pointed by p and has size n,
// where p[0] is used to store the empty symbol.
// the function converts the array representation
// into a linked-list representation, i.e. BTree
BTree(const int *p, const int n);
~BTree();
// Task 3:
// find the pointer where the position points to
TNode * convertpos(int position);
// Task 4:
void addNode(TNode *newnode);
void add2left(TNode *newnode, TNode *p);
void add2right(TNode *newnode, TNode *p);
void add2left(TNode *newnode, int position);
void add2right(TNode *newnode, int position);
void add2left(BTree *newsubtree, int position);
void add2right(BTree *newsubtree, int position);
// Task 5:
void removeleaf(int position);
void removeleaf(TNode *p);
// Task 6:
// convert the BT into the array form. Determine what n
// should be, and new an array of size n+1, and store
// the empty symbol at array[0]. Convert the BT into the
// array form and retrun the array pointer. The size of
// the array will be given to the variable n.
int * Toarray(int &n);
// Task 7:
// swap-the-values is fine
void swapnodes(TNode *n1, TNode *n2);
// print the node as you traverse according to the order.
void print_pre_order();
void print_in_order();
void print_post_order();
// Task 8:
// return whether this BT is a valid BST
bool isValidBST();
// private members
private:
int size;
TNode *root;
void recCopy(TNode * r1, TNode * r2);
void recInOrder(TNode * r);
void recPreOrder(TNode * r);
void recPostOrder(TNode * r);
bool recIsValidBST(TNode* r);
};
// Task 9:
// start main function
int main()
{
try
{
// create a tree 1
BTree tree1;
// add nodes to the tree 1
tree1.addNode(new TNode(13));
tree1.addNode(new TNode(17));
tree1.addNode(new TNode(12));
tree1.addNode(new TNode(15));
tree1.addNode(new TNode(11));
tree1.addNode(new TNode(16));
// create a tree 2
BTree tree2;
// add nodes to the tree 2
tree2.addNode(new TNode(5));
tree2.addNode(new TNode(3));
tree2.addNode(new TNode(7));
tree2.addNode(new TNode(2));
tree2.addNode(new TNode(4));
tree2.addNode(new TNode(6));
tree2.addNode(new TNode(8));
tree2.addNode(new TNode(1));
// print tree 1
cout << "Tree1..." << endl;
cout << "Preorder: ";
tree1.print_pre_order();
cout << " Inorder: ";
tree1.print_in_order();
cout << " Postorder: ";
tree1.print_post_order();
cout << endl << endl;
// print tree 2
cout << "Tree2..." << endl;
cout << "Preorder: ";
tree2.print_pre_order();
cout << " Inorder: ";
tree2.print_in_order();
cout << " Postorder: ";
tree2.print_post_order();
cout << endl << endl;
// verify and display whether tree 1 is a BT
int n = 0;
int* p = tree1.Toarray(n);
if (isValidBT(p, n))
cout << "Tree1 is a valid Binary Tree." << endl;
else
cout << "Tree1 is not a valid Binary Tree." << endl;
// verify and display whether tree 2 is a BT
p = tree2.Toarray(n);
if (isValidBT(p, n))
cout << "Tree2 is a valid Binary Tree." << endl;
else
cout << "Tree2 is not a valid Binary Tree." << endl;
cout << endl;
// verify and display whether tree 1 is a BST
if (tree1.isValidBST())
cout << "Tree1 is a valid Binary Search Tree." << endl;
else
cout << "Tree1 is not a valid Binary Search Tree." << endl;
// verify and display whether tree 2 is a BST
if (tree2.isValidBST())
cout << "Tree2 is a valid Binary Search Tree." << endl;
else
cout << "Tree2 is not a valid Binary Search Tree." << endl;
cout << endl;
}
catch (string mes)
{
cout << mes << endl;
}
return 0;
} // end of main function
// constructor implementation
BTree::BTree()
{
root = NULL;
size = 0;
} // end of constructor
// constructor implementation
BTree::BTree(TNode *r)
{
root = r;
r->parent = NULL;
r->left = NULL;
r->right = NULL;
size = 1;
} // end of constructor
// constructor implementation
BTree::BTree(const BTree &t)
{
root = new TNode(t.root->val);
recCopy(t.root, root);
} // end of constructor
// constructor implementation
BTree::BTree(const int *p, const int n)
{
if (isValidBT(p, n))
{
for (int i = 1; i < n + 1; i++)
{
if (p[i] != p[0])
{
if (size % 2 == 0)
{
add2right(new TNode(p[i]), i);
}
else
{
add2left(new TNode(p[i]), i);
}
}
}
}
} // end of constructor
// destructor implementation
BTree::~BTree()
{}
// convertpos function implementation
TNode * BTree::convertpos(int position)
{
if (position <= 1)
{
return root;
}
TNode* newnode = NULL;
if (position & 1)
{
newnode = (convertpos(position>> 1))->right;
}
else
{
newnode = (convertpos(position>> 1))->left;
}
if (newnode == NULL)
{
string errorMessage = "It is an invalid position!";
throw errorMessage;
}
return newnode;
} // end of convertpos function
// addNode function implementation
void BTree::addNode(TNode *newnode)
{
if (size % 2 == 0)
{
add2right(newnode, size + 1);
}
else
{
add2left(newnode, size + 1);
}
} // end of addNode function
// add2left function implementation
void BTree::add2left(TNode *newnode, TNode *p)
{
if (p == NULL)
{
root = newnode;
newnode->parent = p;
size++;
}
else if (p->val == newnode->val)
{
cout << "This position is already filled." << endl;
}
else if (p->left == NULL)
{
p->left = newnode;
newnode->parent = p;
size++;
}
else
{
string errorMessage = "This position is already filled.";
throw errorMessage;
}
} // end of add2left function
// add2right function implementation
void BTree::add2right(TNode *newnode, TNode *p)
{
if (p == NULL)
{
root = newnode;
newnode->parent = p;
size++;
}
else if (p->val == newnode->val)
{
cout << "This position is already filled." << endl;
}
else if (p->right == NULL)
{
p->right = newnode;
newnode->parent = p;
size++;
}
else
{
string errorMessage = "This position is already filled.";
throw errorMessage;
}
} // end of add2right function
// add2left function implementation
void BTree::add2left(TNode *newnode, int position)
{
int loc = position / 2;
add2left(newnode, convertpos(loc));
} // end of add2left function
// add2right function implementation
void BTree::add2right(TNode *newnode, int position)
{
int loc = position / 2;
add2right(newnode, convertpos(loc));
} // end of add2right function
// add2left function implementation
void BTree::add2left(BTree *newsubtree, int position)
{
BTree newtree = *newsubtree;
add2left(newtree.root, position);
size = size + newtree.size - 1;
} // end of add2left function
// add2right function implementation
void BTree::add2right(BTree *newsubtree, int position)
{
BTree newtree = *newsubtree;
add2right(newtree.root, position);
size = size + newtree.size - 1;
} // end of add2right function
// removeleaf function implementation
void BTree::removeleaf(int position)
{
removeleaf(convertpos(position));
} // end of removeleaf function
// removeleaf function implementation
void BTree::removeleaf(TNode *p)
{
if (p->left == NULL && p->right == NULL)
{
if (p->parent->left == p)
{
p->parent->left = NULL;
}
else if (p->parent->right == p)
{
p->parent->right = NULL;
}
delete p;
}
size--;
} // end of removeleaf function
// print_pre_order function implementation
void BTree::print_pre_order()
{
recPreOrder(root);
} // end of print_pre_order function
// print_in_order function implementation
void BTree::print_in_order()
{
recInOrder(root);
} // end of print_in_order function
// print_post_order function implementation
void BTree::print_post_order()
{
recPostOrder(root);
} // end of print_post_order function
// swapnodes function implementation
void BTree::swapnodes(TNode *n1, TNode *n2)
{
int tempVal = n1->val;
n1->val = n2->val;
n2->val = tempVal;
} // end of swapnodes function
// Toarray function implementation
int * BTree::Toarray(int &n)
{
int i = 1;
int j = 1;
while (i < size)
{
try
{
convertpos(i)->val;
i++;
}
catch (...)
{}
j++;
}
int * arr = new int[j];
n = 1;
for (int k = 1; k <= j; k++)
{
try
{
arr[k] = convertpos(k)->val;
}
catch (...)
{
arr[k] = -1;
}
n++;
}
arr[0] = -1;
return arr;
} // end of Toarray function
// isValidBST function implementation
bool BTree::isValidBST()
{
return recIsValidBST(root);
} // end of isValidBST function
// recCopy function implementation
void BTree::recCopy(TNode * r1, TNode * r2)
{
if (r1->left != NULL)
{
TNode* newnode = new TNode(r1->left->val);
add2left(newnode, r2);
recCopy(r1->left, r2->left);
}
if (r1->right != NULL)
{
TNode* newnode = new TNode(r1->right->val);
add2right(newnode, r2);
recCopy(r1->right, r2->right);
}
} // end of recCopy function
// recPreOrder function implementation
void BTree::recPreOrder(TNode * r)
{
if (r == NULL)
return;
cout << r->val << " ";
if (r->left != NULL)
recPreOrder(r->left);
if (r->right != NULL)
recPreOrder(r->right);
} // end of recPreOrder function
// recInOrder function implementation
void BTree::recInOrder(TNode * r)
{
if (r == NULL)
return;
if (r->left != NULL)
recInOrder(r->left);
cout << r->val << " ";
if (r->right != NULL)
recInOrder(r->right);
} // end of recInOrder function
// recPostOrder function implementation
void BTree::recPostOrder(TNode * r)
{
if (r == NULL)
return;
if (r->left != NULL)
recPostOrder(r->left);
if (r->right != NULL)
recPostOrder(r->right);
cout << r->val << " ";
} // end of recPostOrder function
// recIsValidBST function implementation
bool BTree::recIsValidBST(TNode* r)
{
if (r == NULL)
return true;
if (r->left != NULL && r->left->val > r->val)
return false;
if (r->right != NULL && r->right->val < r->val)
return false;
if (!recIsValidBST(r->left) || !recIsValidBST(r->right))
return false;
return true;
} // end of recIsValidBST function
// isValidBT function implementation
bool isValidBT(const int *p, const int n)
{
for (int i = 2; i < n + 1; i++)
{
if (p[i] != p[0] && p[i / 2] == p[0])
{
return false;
}
}
return true;
} // end of isValidBT function
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.