BST.cpp
#include "BST.h"
#include "BT-visualize.h"
#include <assert.h>
#include <stdio.h>
#include <string.h>
#include <string>
// Implement the following five methods
// inserts val into BST rooted at x and returns the tree's new
root
BTnode * insert(BTnode * x, int val) {}
// returns true iff target in tree rooted at x
bool search(BTnode * x, int target) {}
// Find the maximum value of a tree rooted at x
int findmax(BTnode * x) {}
// Find the manimum value of a tree rooted at x
int findmin(BTnode * x) {}
// Given a binary tree, print its nodes in in-order
void printAscendOrder(BTnode * x){}
// You don't need to worry about these methods below
BTascii print_helper(BTnode * x);
void print(BTnode * x) {
BTascii ret = print_helper(x);
ret.display();
}
BTascii print_helper(BTnode * x) {
if (x == NULL) return BTascii();
BTascii left = print_helper(x->left);
BTascii right = print_helper(x->right);
char buf[25];
sprintf(buf, "%d", x->val); return join(left, right,
std::string(buf));
}
void postfree(BTnode * x) {
if (x == NULL) return;
postfree(x->left);
postfree(x->right);
delete x;
}
BST.h
#ifndef _BST_H_
#define _BST_H_
#include <iostream>
#include "BT-node.h"
// Implement the following five methods in BST.cpp file.
// Insert val into BST rooted at x and returns the tree's new
root
BTnode * insert(BTnode * x, int val);
// Return true iff target in tree rooted at x
bool search(BTnode * x, int target);
// Return maxmium value of the tree rooted at x. Return 0 if
tree is empty.
int findmax(BTnode * root);
// Return maxmium value of the tree rooted at x. Return 0 if
tree is empty.
int findmin(BTnode * root);
// Given a binary tree, print its nodes in in-order
void printAscendOrder(BTnode * root);
// You don't need to implement these below in BST.cpp file
void print(BTnode * root);
void postfree(BTnode * root);
#endif // _BT_H_
BT-node.h
#ifndef _BT_NODE_H_
#define _BT_NODE_H_
struct BTnode {
public:
int val; // this is only valid if type == intNode
struct BTnode * left;
struct BTnode * right;
};
#endif // _BT_NODE_H_
BT-visualize.cpp
#include "BT-visualize.h"
#include <vector>
#include <string>
#include <assert.h>
#include <stdio.h>
bool BTascii::isEmpty() {
return rows == 0;
}
BTascii join(BTascii left, BTascii right, std::string root)
{
BTascii ret;
if (left.isEmpty() && right.isEmpty()) return
BTascii(root);
int leftpad = 0;
int midpad = 1;
int rightpad = 0;
int rootlen = root.length();
char leftdot = '.';
char rightdot = '.';
char leftup = ':';
char rightup = ':';
ret.rootcol = (left.rootcol + (left.cols + midpad +
right.rootcol))/2;
if (left.isEmpty()) {
left.rows = 1;
left.cols = 1;
midpad = 0;
left.rootcol = 0;
leftdot = ' ';
leftup = ' ';
left.grid.push_back(std::string(" "));
}
if (right.isEmpty()) {
right.rows = 1;
right.cols = 1;
midpad = 0;
right.rootcol = 0;
rightdot = ' ';
rightup = ' ';
right.grid.push_back(std::string(" "));
}
int rootstartpos = ret.rootcol - rootlen/2;
while (rootstartpos < 0) {
leftpad++;
rootstartpos++;
ret.rootcol++;
}
ret.cols = leftpad + left.cols + midpad + right.cols +
rightpad;
while (rootstartpos + rootlen > ret.cols) {
rightpad++;
ret.cols++;
}
int parity = root.length() % 2;
std::string mid;
if (parity) {
mid = std::string(":");
} else {
mid = std::string("::");
}
//ret.rows = std::max(left.rows, right.rows) + 2;
ret.rows = std::max(left.rows, right.rows) + 3;
ret.grid.push_back(std::string(rootstartpos, ' ') + root +
std::string(ret.cols - rootlen - rootstartpos, ' '));
ret.grid.push_back(std::string(leftpad + left.rootcol, ' ') +
std::string(ret.rootcol - leftpad - left.rootcol - !parity,
leftdot) + mid + std::string(leftpad + left.cols + midpad +
right.rootcol - ret.rootcol, rightdot) + std::string(ret.cols -
leftpad - left.cols - midpad - right.rootcol - 1, ' '));
//ret.grid.push_back(std::string(leftpad + left.rootcol, ' ') +
std::string(":") + std::string(ret.rootcol - leftpad - left.rootcol
- 1, ' ') + mid + std::string(leftpad + left.cols + midpad +
right.rootcol - ret.rootcol - !parity - 1, ' ') + std::string(":")
+ std::string(ret.cols - leftpad - left.cols - midpad -
right.rootcol - 1, ' '));
ret.grid.push_back(std::string(leftpad + left.rootcol, ' ') +
std::string(1,leftup) + std::string(left.cols + midpad +
right.rootcol - left.rootcol - 1, ' ') + std::string(1,rightup) +
std::string(ret.cols - leftpad - left.cols - midpad - right.rootcol
-1, ' '));
//for (int i = 0; i < ret.rows - 2; i++) {
for (int i = 0; i < ret.rows - 3; i++) {
if (i >= left.rows) {
assert(i < right.rows);
ret.grid.push_back(std::string(leftpad + left.cols + midpad, ' ') +
right.grid[i] + std::string(rightpad, ' '));
} else if (i >= right.rows) {
ret.grid.push_back(std::string(leftpad, ' ') + left.grid[i] +
std::string(midpad + right.cols + rightpad, ' '));
} else {
ret.grid.push_back(std::string(leftpad, ' ') + left.grid[i] +
std::string(midpad, ' ') + right.grid[i] + std::string(rightpad, '
'));
}
}
return ret;
}
void BTascii::display() {
assert(rows == grid.size());
for (int i = 0; i < rows; i++) {
assert(cols == grid[i].length());
puts(grid[i].c_str());
}
}
BTascii& BTascii::operator=(const BTascii& other)
{
BTascii temp(other);
swap(*this, temp);
return *this;
}
BT_visualize.h
#ifndef _BT_VISUALIZE_H_
#define _BT_VISUALIZE_H_
#include <vector>
#include <string>
class BTascii;
BTascii join(BTascii left, BTascii right, std::string root);
class BTascii {
private:
public:
unsigned int rootcol;
unsigned int rows;
unsigned int cols;
std::vector <std::string>
grid;
bool isEmpty();
BTascii() { rows = cols = rootcol =
0; }
BTascii(std::string s) {
grid.push_back(s); rows = 1; cols = s.length(); rootcol = cols/2;
}
~BTascii() {}
// both left, right must be
nonempty, or else the nonempty one is returned and root is not
used
friend BTascii join(BTascii left,
BTascii right, std::string root);
void display();
friend void swap(BTascii
&first, BTascii &second) {
std::swap(first.rootcol, second.rootcol);
std::swap(first.rows, second.rows);
std::swap(first.cols, second.cols);
std::swap(first.grid, second.grid);
}
BTascii& operator=(const
BTascii& other);
};
#endif // _BT_VISUALIZE_H_
main.cpp
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "BST.h"
#include "BT-node.h"
// Test your methods in the main function
int main () {
BTnode * tree = NULL;
for (int i = 0; i < 10; i++) {
int newnum = rand() % 900 + 100;
printf("Inserting . . . %d\n", newnum);
// Test your insert function
tree = insert(tree, newnum);
print(tree);
putchar('\n');
// This is just to pause until you
press enter after every insert
getchar();
}
// Test your search function
printf("303: %d\n", search(tree, 303));
printf("209: %d\n", search(tree, 209));
// Print out the maximum value in the tree
int max = findmax(tree);
printf("maximum value: %d\n", max);
// Print out the minimum value in the tree
int min = findmin(tree);
printf("minimum value: %d\n", min);
// Test your printAscendOrder function
printf("Elements in ascending order:");
printAscendOrder(tree);
postfree(tree);
return 0;
}
PLEASE HELP ME REGARDING THE ABOVE QUESTION ASAP!
PLEASE TYPE CODES AND PROVIDE THEM IN C++!
Add below implemented function in your BST.cpp file -
BST.cpp
#include "BST.h"
#include "BT_visualize.h"
#include <assert.h>
#include <stdio.h>
#include <string.h>
#include <string>
#include <stdlib.h>
BTnode * insert(BTnode * x, int val) {
/* If the tree is empty, return a new node */
if (x == NULL) {
struct BTnode *temp = (struct
BTnode *)malloc(sizeof(struct BTnode));
temp->val = val;
temp->left = temp->right =
NULL;
return temp;
}
/* Otherwise, recur down the tree */
if (val < x->val)
x->left = insert(x->left,
val);
else if (val > x->val)
x->right = insert(x->right,
val);
/* return the (unchanged) node pointer */
return x;
}
bool search(BTnode * x, int target) {
// Base Cases: root is null or target is present at
root
if (x == NULL || x->val == target)
return x;
// Target is greater than root's val
if (x->val < target)
return search(x->right,
target);
// Target is smaller than root's val
return search(x->left, target);
}
int findmax(BTnode * x) {
// Base case
if (x == NULL)
return -1;
// Return maximum of 3 values:
// 1) Root's data 2) Max in Left Subtree
// 3) Max in right subtree
int res = x->val;
if (x->left != NULL) {
int lres =
findmax(x->left);
if (lres > res)
res =
lres;
}
if (x->right != NULL) {
int rres =
findmax(x->right);
if (rres > res)
res =
rres;
}
return res;
}
int findmin(BTnode * x) {
// Return minimum of 3 values:
// 1) Root's data 2) Max in Left Subtree
// 3) Max in right subtree
int res = x->val;
if (x->left != NULL) {
int lres =
findmin(x->left);
if (lres < res)
res =
lres;
}
if (x->right != NULL) {
int rres =
findmin(x->right);
if (rres < res)
res =
rres;
}
return res;
}
void printAscendOrder(BTnode * x){
if (x != NULL)
{
printAscendOrder(x->left);
printf("%d ",x->val);
printAscendOrder(x->right);
}
}
BST.cpp #include "BST.h" #include "BT-visualize.h" #include <assert.h> #include <stdio....
C++ (Using Binary Search Trees) other methods will result in downvote Implement the binary search tree methods (bst.cpp) for the binary search tree provided in the header file. Test your implementation with the included test. bst.h bst_test.cpp Note: Your implementation must correspond to declarations in the header file, and pass the test. Do not modify these two. I will compile your code against these. If the compilation fails, you will get down vote. bst.h #ifndef BINARY_SEARCH_TREE_H #define BINARY_SEARCH_TREE_H #include <string>...
I need help in C++ implementing binary search tree. I have the .h file for the binary search tree class. I have 4 classic texts, and 2 different dictionaries. Classic Texts: Alice In Wonderland.txt A Tale of Two Cities.txt Pride And Prejudice.txt War and Peace.txt 2 different dictionaries: Dictionary.txt Dictionary-brit.txt The data structures from the standard template library can not be used.The main program should open the text file, read in the words, remove the punctuation and change all the...
Question B1 You are given the following Java classes: public class Queue { private static class Node { Object object; Node next; Node () { object = null; next = null; } Node (Object object, Node next) { this.object = object; this.next = next; private Node header; private int size = 0; // size shows the no of elements in queue public Object dequeue () { if (size == 0 ) { return null; else { Object remove_object = header.object;...
in c++ please program for this code #include <iostream> #include <fstream> #include <string> #include <cstring> // for string tokenizer and c-style string processing #include <algorithm> // max function #include <stdlib.h> #include <time.h> using namespace std; // Extend the code here as needed class BTNode{ private: int nodeid; int data; int levelNum; BTNode* leftChildPtr; BTNode* rightChildPtr; public: BTNode(){} void setNodeId(int id){ nodeid = id; } int getNodeId(){ return nodeid; } void setData(int d){ data = d; } int getData(){ return data;...
Q1) Write a method called inToTree of ExpressionTree class which takes a string of infix expression (fully parenthesized), resets the root of the expression tree to such tree which constructed from the expression. The root set to null of the expression contains characters other than value, operator, and parenthesis or if it’s not an in-fix full parenthesized expression. You may assume each value is single digit only . public void inToTree(String expression){ You may use a JCF Deque class as...
Question 1: Fix the 2D dynamic array initialization in following code #include <iostream> using namespace std; int main(){ int rows = 5; int cols = 5; int x; int** arr = new int[rows][cols] cin >> x; arr[x][x] = x; cout << "arr[x][x] = " << arr[x][x]; return 0; } Question 2: Fix the code to initialize the 2D array elements to x #include <iostream> using namespace std; int main(){ int rows; int cols; int x;...
Write loop(s) that print ALL the content of the following 2D array #include <iostream> using namespace std; int main(){ int rows; int cols; int offset; cin >> rows; cin >> cols; cin >> offset; int** arr = new int*[rows]; for(int i = 0; i < rows; ++i) arr[i] = new int[cols]; for(int i = 0; i < rows; i++) // initialization for(int j = 0; j < cols; j++) arr[i][j] = offset + i; // printing, your code goes here ...
C++: PLEASE HELP~!!! ~~~~~~~~ Implement bool AVLTree::deleteNode(string ss) method. Function deleteNode() tries to delete the node containing value ss. If there is no such node, it returns false. Otherwise, it deletes the node, check the balance of the tree, rebalance the tree if it is necessary. When you delete a node, consider three different scenarios: -The node is a leaf -The node has only ONE child subtree -The node has two child subtrees Important: When you implement this project, do...
Having code issues wth my C++ program. My program checks if two binary trees are similar and if they're not they return false. My program is return true with different binary trees. Could use some help thanks #include <iostream> #include <string> using namespace std; //Struct of Nodes struct BinarySearchTree { int data; BinarySearchTree *left; BinarySearchTree *right; }; // Inserting nodes into BST BinarySearchTree* insert( BinarySearchTree* node, int val) { if (node == NULL) { BinarySearchTree *newNode = new BinarySearchTree(); newNode->data...
Please do in C please. Edit sliding.c. Comments on code would be nice. Thank you. Here is main.c #include "sliding.h" #include <malloc.h> #include <stdlib.h> //Prints grid in row major order. Tries to ensure even spacing. void print_grid(int * my_array, int rows, int cols){ int i,j; for(i=0; i<rows; i++){ for(j=0; j<cols; j++){ if(my_array[i*cols + j]!=-1){ printf(" %d ", my_array[i*cols + j]); } else{ printf("%d ", my_array[i*cols + j]); } } printf("\n"); } } int main(int argc, char *argv[]) { int seed,rows,cols;...