- Forum
- General C++ Programming
- BST Help
BST Help
C++ Help please, Binary Search Tree
I have written some code below, and need help to finish the rest of my assignment, I got stuck. Please extend my code, here are some parts that I still need help:
Next, rearrange the sorted array into a second array which moves the middle element into the first position, the elements in the first quarter and third quarter positions of the sorted array into the second and third positions of the second array, the elements in the first, third, fifth and seven-eighths positions into the fourth through seventh positions, and so forth, until all elements of the sorted array have been entered into the second array. (I think I did this part by findMiddlePoint, but I am unsure)
Move each of the elements of the second array in succession into a new binary tree structure. Be sure to delete the original binary tree when the input names have all been moved to the second binary tree, which will be as balanced as possible.
Display the second binary tree from (4) using the available binary tree display algorithm which was adapted from M&S pages 505-506.
class Node {
private:
string val; // current value in collating sequence
Node* lh; // pointer to left-hand descendant Node
Node* rh; // pointer to right-hand descendant Node
public:
Node() { lh = rh = NULL; val = ""; } // Node () {}
void putVal(string v) { val = v; }
string getVal() { return val; }
void putLH(Node* x) { lh = x; }
Node* getLH() { return lh; }
void putRH(Node* x) { rh = x; }
Node* getRH() { return rh; }
void write(Node* n);
};
void Node::write(Node* n) { // Diagnostic to display a node of a Binary Tree
cout << "Value " << val << " in Node at " << (int)n;
cout << "\t Its LH child " << (int)(lh) << "\t Its RH child "
<< (int)(rh) << endl;
}
class BT { // Container class - does most of the work
private:
int count;
int idx = 0;
Node* root;
Node* tree;
array listofnames;
array array;
private:
Node* addNode(Node*, string);
Node* findInsertion(Node*, string);
void inOrder(Node*);
void locate(Node*, string);
void treePrint(Node*, int);
public:
BT();
sort ();
static const size_t numberofnames = 7;
void comeBineArray();
void addRootNode(string);
void inOrderTraverse();
void locateRoot(string);
void treePrintWrapper();
void findMiddlepoint(int,int,int,int,int);
};
BT::BT() { root = tree = NULL; count = 0;
//ask for input
} // BT::BT () {}
void BT::comeBineArray(){
for (int = 0; i < numberofnames; i++){
addRootNode(bArray[i]);
}
}
void BT::addRootNode(string v)
{
if (root == NULL)
{
root = tree = addNode(tree, v);
// cout << "ptr to root " << root << endl;
}
else
{
tree = root;
tree = findInsertion(tree, v);
}
}
Node* BT::findInsertion(Node* tree, string v)
{
string x;
x = tree->getVal();
cout << "comparing the values:" << nameinput << " and " << x << "\n" << endl;
if (v <= x) // v = nameinput; x = currentname
if (tree->getLH() != NULL)
{
tree = findInsertion(tree->getLH(), v);
return tree; // *** from Paul Pollack 11/13/13 ***new code to prevent
// a new node from being added twice
}
else
{
Node* temp = NULL;
temp = addNode(temp, v);
tree->putLH(temp);
}
else // if ( v > x )
if (tree->getRH() != NULL)
{
tree = findInsertion(tree->getRH(), v);
return tree; // *** from Paul Pollack 11/13/13 ***new code to prevent
// a new node from being added twice
}
else
{
Node* temp = NULL;
temp = addNode(temp, v);
tree->putRH(temp);
}
return tree;
}
Node* BT::addNode(Node* x, string v)
{
if (x = new Node)
{
x->putVal(v);
x->putLH(NULL);
x->putRH(NULL);
}
return x;
}
void BT::inOrderTraverse()
{ //tree = root;
cout << endl;
inOrder(root);
}
void BT::inOrder(Node* n, string array[])
{
if (n != NULL) {
inOrder(n->getLH());
n->write(n);
array[idx] = n;
idx ++;
cout << endl;
inOrder(n->getRH());
}
return;
}
void BT::findMiddlepoint(int a, int b, int level, int number, int round){
int mid;
if (abs(a-b)<2){
if(a==1){
array[idx] = listofnames[a-1];
idx++;
}
if (b==number){
array[idx] = listofnames[b-1];
idx++;
}
return;
}
if ((b+a)%2){
mid=(a+b+round)/2;
array[idx] = listofnames[mid-1];
idx++;
}
else{
mid = (a+b)/2;
array[idx]= listofnames[mid-1];
idx++;
}
}
findMiddlepoint(a,mid,(level+1),number,-1);
findMiddlepoint(mid,b,(level+1),number,1);
return;
}
void BT::locateRoot(string v) {
if (root == NULL)
cout << "Tree is empty" << endl;
else
locate(root, v);
}
void BT::locate(Node* y, string v) { // Bug mentioned by Dan Glade
string x;
x = y->getVal();
if (v == x)
{
cout << "Value " << v << " is in Node at address " << (int)y << endl;
// cout << "Its LH reference is " << (int)(y -> getLH()) << endl << "Its RH reference is " << (int)(y -> getRH()) << endl;
}
else if (v < x)
if (y->getLH() != NULL)
locate(y->getLH(), v);
else
cout << "Value not in tree" << endl;
else // if ( v > x )
if (y->getRH() != NULL)
locate(y->getRH(), v);
else
cout << "Value not in tree" << endl;
}
void BT::treePrintWrapper() {
treePrint(root, 0);
}
void BT::treePrint(Node* ref, int depth) {
// from Main & Savitch page 506
cout << setw(4 * depth) << ""; // indentation
if (ref == NULL) {
// reached a NULL reference in an interior node
cout << "[NULL]" << endl;
}
else if (ref->getLH() == NULL && ref->getRH() == NULL) {
// a leaf
cout << "Value " << ref->getVal() << " at Ref " << (int)root;
cout << " [leaf]" << endl;
}
else {
// a nonleaf - interior node
cout << "Value " << ref->getVal() << " at Ref " << (int)ref << endl;
cout << "LH" << depth + 1;
treePrint(ref->getLH(), depth + 1);
cout << "RH" << depth + 1;
treePrint(ref->getRH(), depth + 1);
}
}
int main() {
string x;
char op = ' ';
BT TREE;
//Node* test;
// Create inorder Binary treee
cout << "To create your Binary tree, use the menu below." << endl << endl;
cout << "Enter your operation using the capital letter shown in your selection." << endl;
cout << "Add a node, display Tree, Show sorted list, Display a node, Help, Exit: ";
while (!cin.eof() && op != 'E' && op != 'e') // build a binary tree in this while loop
{
cout << ">";
cin >> op;
if (!cin.eof() && op != 'E' && op != 'e')
switch (op)
{
case 'A': case 'a':
{ cout << "Please enter in" << numberofnames<< " names: \n" << endl;
string nameinput;
for(int i=0; i < numberofnames; i ++){
cin >> nameinput;
if(!cin.eof() && cin.good()){
listofnames[i] = nameinput;
}
}
}
if (!cin.eof())
TREE.addRootNode(x);
break;
}
case 'S': case 's':
{
cout << endl << "In-OrderTree Traversal:" << endl;
TREE.inOrderTraverse();
break;
}
case 'T': case 't':
{
cout << endl << "Display Tree:" << endl;
TREE.treePrintWrapper();
break;
}
case 'D': case 'd':
{ cout << endl << "Enter User value of Node to Display: ";
cin >> x;
if (!cin.eof())
TREE.locateRoot(x);
break;
}
case 'E': case 'e':
{ break;
}
case 'H': case 'h':
{ cout << "Enter your operation using the capital letter shown in your selection." << endl;
cout << "Add a node, display Tree, Show sorted list, Display a node, Help, Exit: ";
break;
}
default:
{ cout << "Invalid operation. Try again!" << endl;
break;
}
}
}
// system("PAUSE");
return EXIT_SUCCESS;
}
I have written some code below, and need help to finish the rest of my assignment, I got stuck. Please extend my code, here are some parts that I still need help:
Next, rearrange the sorted array into a second array which moves the middle element into the first position, the elements in the first quarter and third quarter positions of the sorted array into the second and third positions of the second array, the elements in the first, third, fifth and seven-eighths positions into the fourth through seventh positions, and so forth, until all elements of the sorted array have been entered into the second array. (I think I did this part by findMiddlePoint, but I am unsure)
Move each of the elements of the second array in succession into a new binary tree structure. Be sure to delete the original binary tree when the input names have all been moved to the second binary tree, which will be as balanced as possible.
Display the second binary tree from (4) using the available binary tree display algorithm which was adapted from M&S pages 505-506.
class Node {
private:
string val; // current value in collating sequence
Node* lh; // pointer to left-hand descendant Node
Node* rh; // pointer to right-hand descendant Node
public:
Node() { lh = rh = NULL; val = ""; } // Node () {}
void putVal(string v) { val = v; }
string getVal() { return val; }
void putLH(Node* x) { lh = x; }
Node* getLH() { return lh; }
void putRH(Node* x) { rh = x; }
Node* getRH() { return rh; }
void write(Node* n);
};
void Node::write(Node* n) { // Diagnostic to display a node of a Binary Tree
cout << "Value " << val << " in Node at " << (int)n;
cout << "\t Its LH child " << (int)(lh) << "\t Its RH child "
<< (int)(rh) << endl;
}
class BT { // Container class - does most of the work
private:
int count;
int idx = 0;
Node* root;
Node* tree;
array listofnames;
array array;
private:
Node* addNode(Node*, string);
Node* findInsertion(Node*, string);
void inOrder(Node*);
void locate(Node*, string);
void treePrint(Node*, int);
public:
BT();
sort ();
static const size_t numberofnames = 7;
void comeBineArray();
void addRootNode(string);
void inOrderTraverse();
void locateRoot(string);
void treePrintWrapper();
void findMiddlepoint(int,int,int,int,int);
};
BT::BT() { root = tree = NULL; count = 0;
//ask for input
} // BT::BT () {}
void BT::comeBineArray(){
for (int = 0; i < numberofnames; i++){
addRootNode(bArray[i]);
}
}
void BT::addRootNode(string v)
{
if (root == NULL)
{
root = tree = addNode(tree, v);
// cout << "ptr to root " << root << endl;
}
else
{
tree = root;
tree = findInsertion(tree, v);
}
}
Node* BT::findInsertion(Node* tree, string v)
{
string x;
x = tree->getVal();
cout << "comparing the values:" << nameinput << " and " << x << "\n" << endl;
if (v <= x) // v = nameinput; x = currentname
if (tree->getLH() != NULL)
{
tree = findInsertion(tree->getLH(), v);
return tree; // *** from Paul Pollack 11/13/13 ***new code to prevent
// a new node from being added twice
}
else
{
Node* temp = NULL;
temp = addNode(temp, v);
tree->putLH(temp);
}
else // if ( v > x )
if (tree->getRH() != NULL)
{
tree = findInsertion(tree->getRH(), v);
return tree; // *** from Paul Pollack 11/13/13 ***new code to prevent
// a new node from being added twice
}
else
{
Node* temp = NULL;
temp = addNode(temp, v);
tree->putRH(temp);
}
return tree;
}
Node* BT::addNode(Node* x, string v)
{
if (x = new Node)
{
x->putVal(v);
x->putLH(NULL);
x->putRH(NULL);
}
return x;
}
void BT::inOrderTraverse()
{ //tree = root;
cout << endl;
inOrder(root);
}
void BT::inOrder(Node* n, string array[])
{
if (n != NULL) {
inOrder(n->getLH());
n->write(n);
array[idx] = n;
idx ++;
cout << endl;
inOrder(n->getRH());
}
return;
}
void BT::findMiddlepoint(int a, int b, int level, int number, int round){
int mid;
if (abs(a-b)<2){
if(a==1){
array[idx] = listofnames[a-1];
idx++;
}
if (b==number){
array[idx] = listofnames[b-1];
idx++;
}
return;
}
if ((b+a)%2){
mid=(a+b+round)/2;
array[idx] = listofnames[mid-1];
idx++;
}
else{
mid = (a+b)/2;
array[idx]= listofnames[mid-1];
idx++;
}
}
findMiddlepoint(a,mid,(level+1),number,-1);
findMiddlepoint(mid,b,(level+1),number,1);
return;
}
void BT::locateRoot(string v) {
if (root == NULL)
cout << "Tree is empty" << endl;
else
locate(root, v);
}
void BT::locate(Node* y, string v) { // Bug mentioned by Dan Glade
string x;
x = y->getVal();
if (v == x)
{
cout << "Value " << v << " is in Node at address " << (int)y << endl;
// cout << "Its LH reference is " << (int)(y -> getLH()) << endl << "Its RH reference is " << (int)(y -> getRH()) << endl;
}
else if (v < x)
if (y->getLH() != NULL)
locate(y->getLH(), v);
else
cout << "Value not in tree" << endl;
else // if ( v > x )
if (y->getRH() != NULL)
locate(y->getRH(), v);
else
cout << "Value not in tree" << endl;
}
void BT::treePrintWrapper() {
treePrint(root, 0);
}
void BT::treePrint(Node* ref, int depth) {
// from Main & Savitch page 506
cout << setw(4 * depth) << ""; // indentation
if (ref == NULL) {
// reached a NULL reference in an interior node
cout << "[NULL]" << endl;
}
else if (ref->getLH() == NULL && ref->getRH() == NULL) {
// a leaf
cout << "Value " << ref->getVal() << " at Ref " << (int)root;
cout << " [leaf]" << endl;
}
else {
// a nonleaf - interior node
cout << "Value " << ref->getVal() << " at Ref " << (int)ref << endl;
cout << "LH" << depth + 1;
treePrint(ref->getLH(), depth + 1);
cout << "RH" << depth + 1;
treePrint(ref->getRH(), depth + 1);
}
}
int main() {
string x;
char op = ' ';
BT TREE;
//Node* test;
// Create inorder Binary treee
cout << "To create your Binary tree, use the menu below." << endl << endl;
cout << "Enter your operation using the capital letter shown in your selection." << endl;
cout << "Add a node, display Tree, Show sorted list, Display a node, Help, Exit: ";
while (!cin.eof() && op != 'E' && op != 'e') // build a binary tree in this while loop
{
cout << ">";
cin >> op;
if (!cin.eof() && op != 'E' && op != 'e')
switch (op)
{
case 'A': case 'a':
{ cout << "Please enter in" << numberofnames<< " names: \n" << endl;
string nameinput;
for(int i=0; i < numberofnames; i ++){
cin >> nameinput;
if(!cin.eof() && cin.good()){
listofnames[i] = nameinput;
}
}
}
if (!cin.eof())
TREE.addRootNode(x);
break;
}
case 'S': case 's':
{
cout << endl << "In-OrderTree Traversal:" << endl;
TREE.inOrderTraverse();
break;
}
case 'T': case 't':
{
cout << endl << "Display Tree:" << endl;
TREE.treePrintWrapper();
break;
}
case 'D': case 'd':
{ cout << endl << "Enter User value of Node to Display: ";
cin >> x;
if (!cin.eof())
TREE.locateRoot(x);
break;
}
case 'E': case 'e':
{ break;
}
case 'H': case 'h':
{ cout << "Enter your operation using the capital letter shown in your selection." << endl;
cout << "Add a node, display Tree, Show sorted list, Display a node, Help, Exit: ";
break;
}
default:
{ cout << "Invalid operation. Try again!" << endl;
break;
}
}
}
// system("PAUSE");
return EXIT_SUCCESS;
}
> I have written some code below,
More likely, you have found some code below.
Like tell-tale comments leading to searches like this.
https://www.google.com/search?q=%22from+Paul+Pollack+11/13/13%22&filter=0&biw=1472&bih=697
If it were really substantially yours, it wouldn't have comments like that in it.
Not to mention, the cross-posting.
https://www.chegg.com/homework-help/questions-and-answers/c-help-please-binary-search-tree-written-code-need-help-finish-rest-assignment-got-stucked-q37566234
More likely, you have found some code below.
Like tell-tale comments leading to searches like this.
https://www.google.com/search?q=%22from+Paul+Pollack+11/13/13%22&filter=0&biw=1472&bih=697
If it were really substantially yours, it wouldn't have comments like that in it.
Not to mention, the cross-posting.
https://www.chegg.com/homework-help/questions-and-answers/c-help-please-binary-search-tree-written-code-need-help-finish-rest-assignment-got-stucked-q37566234
Topic archived. No new replies allowed.