#include<iostream>
#include<vector>
using namespace std;
class TNode
{
public:
int val;
TNode():
val (-9999),
left (NULL) ,
right (NULL) ,
parent (NULL)
{}
TNode(int v):
val (v),
left (NULL),
right (NULL),
parent (NULL)
{}
bool is_valid() {
if ( this->left && this->right )
return true;
return false;
}
TNode * left;
TNode * right;
TNode * parent;
};
class BTree
{
vector<int> m_data;
// [inner] return lowest element
TNode* m_tree_min(TNode *T)
{
TNode *x = T;
while (x->left !=
NULL)
x = x->left;
return x;
}
// [inner] return tree successor
TNode* m_tree_successor(TNode*x)
{
TNode *y;
if (x->right !=
NULL)
return m_tree_min(x->right);
else
{
y = x->parent;
while (y != NULL && x == y->right)
{
x = y;
y = y->parent;
}
}
return y;
}
// [inner] transplant a node
void m_tree_transplant(TNode *&T, TNode *z,
TNode *y)
{
if (z->parent ==
NULL)
T = y;
else
{
if (z->parent->left == z)
z->parent->left = y;
else
z->parent->right = y;
}
if (y != NULL)
y->parent = z->parent;
}
// [inner] deleter
void m_tree_delete(TNode *&T, TNode
*z)
{
TNode *y;
TNode *s =
z->parent;
if (z->left ==
NULL)
m_tree_transplant(T, z, z->right);
else
{
if (z->right == NULL)
m_tree_transplant(T, z, z->left);
else
{
y = m_tree_successor(z);
s = y->parent;
if (y != z->right)
{
m_tree_transplant(T, y, y->right);
y->right = z->right;
y->right->parent = y;
}
y->left = z->left;
y->left->parent = y;
m_tree_transplant(T, z, y);
}
}
delete z;
}
// print in order [ LEFT, ROOT, RIGHT ]
void m_in_order( TNode* node, bool
print_to_arr=false)
{
if ( node ) {
/* first recur on left child */
if(node->left) {
m_in_order(node->left, print_to_arr);
}
// print to arr
if( print_to_arr ) {
this->m_data.push_back( node->val );
// or print to cout
} else {
/* then print the data of node */
cout << " " << node->val << " ";
}
/* now recur on right child */
if(node->right) {
m_in_order(node->right, print_to_arr);
}
}
};
// print post order [ LEFT, ROOT, RIGHT
]
void m_post_order( TNode* node)
{
if ( node ) {
/* first recur on left child */
if(node->left) {
m_post_order(node->left);
}
/* now recur on right child */
if(node->right) {
m_post_order(node->right);
}
/* then print the data of node */
cout << " " << node->val << " ";
}
};
// print pre order [ ROOT , LEFT, RIGHT
]
void m_pre_order( TNode* node)
{
if ( node ) {
/* then print the data of node */
cout << " " << node->val << " ";
/* first recur on left child */
if(node->left) {
m_pre_order(node->left);
}
/* now recur on right child */
if(node->right) {
m_pre_order(node->right);
}
}
};
// [inner] m_tree_search search & return
the node ( if exist )
TNode* m_tree_search(TNode *T, int k)
{
TNode *x = T;
while (x != NULL
&& x->val != k)
{
if (x->val > k)
x = x->left;
else
x = x->right;
}
return x;
};
// [inner] m_get_size compute size
int m_get_size(TNode *node)
{
if (node==NULL)
return 0;
else
return(m_get_size(node->left) + 1 +
m_get_size(node->right));
};
// [inner] insert a new key
void m_tree_insert(TNode *&T, int key)
{
TNode* new_node = new
TNode(key);
cout << " *** insert key [" << new_node->val << "]" << endl ;
// y = parent, if
any
// x = current
element
TNode *y = NULL, *x =
T;
//
while (x != NULL)
{
//cout << " try to locate " << endl;
y = x;
// search on left
if (new_node->val < x->val) {
x = x->left;
// search on right
} else
if (new_node->val > x->val)
{
x = x->right;
// node exists ..
} else {
cout << " value already in tree, exit .. "
<< endl;
delete new_node;
return;
}
}
// Y can be NULL [ we
have root element in this case ]
new_node->parent =
y;
if (y == NULL) {
cout << " [ROOT] added (tree size = 1)"
<< endl;
T = new_node;
this->size = 1;
}
else
{
//bool is_insert = false;
if (new_node->val < y->val) {
(this->size)++ ;
cout << " value inserted as left of ["
<< y->val << "] new size = " << this->size
<< endl;
y->left = new_node;
}
else
if (new_node->val > y->val) {
(this->size)++ ;
cout << " value inserted as right of ["
<< y->val << "] new size = " << this->size
<< endl;
y->right = new_node;
// node exists ..
} else {
cout << " value already in tree, exit .. "
<< endl;
delete new_node;
return;
}
}
}
// [inner] destroy all sub nodes ..
void m_destroyTree (TNode* node)
{
//cout << " ***
delete tree " << endl ;
if ( NULL == node
)
return;
if(node->right)
{
if(node->right->right || node->right->left){
m_destroyTree(node->right);
} else {
(this->size)-- ;
cout << " *** delete node " << node->right->val
<< " new size : " << this->size << endl
;
delete node->right;
}
}
if(node->left)
{
if(node->left->left || node->left->right){
m_destroyTree(node->left);
} else {
(this->size)-- ;
cout << " *** delete node " << node->left->val
<< " new size : " << this->size << endl
;
delete node->left;
}
}
(this->size)--
;
cout << " ***
delete node " << node->val << " new size : "
<< this->size << endl ;
delete node;
};
// [inner] copy node [recursive]
TNode* m_copy_node(const TNode *aCopy) {
if (aCopy ==
NULL)
return NULL;
TNode *copyNode = new
TNode(aCopy->val );
copyNode->left = m_copy_node(aCopy->left );
copyNode->right =
m_copy_node(aCopy->right );
return copyNode;
}
public:
// size of tree .. [
updated on delete & insert ]
int size;
// tree root
TNode *root;
// empty symbol
flag
int empty_symbol;
//constructors and
destructor
BTree():
root ( NULL
),
empty_symbol ( -9999 ),
size (
0 )
{};
// initialize BTree
with the root r. r is the only node.
BTree(TNode *r):
root ( NULL ),
empty_symbol ( -9999 )
{
this->root = this->m_copy_node( r );
this->size = this->m_get_size( this->root );
};
// copy
constructor
BTree(const BTree&
aOther)
{
this->size =
aOther.size ;
this->empty_symbol = aOther.empty_symbol ;
this->root = this->m_copy_node(aOther.root);
};
// 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):
root ( NULL
),
empty_symbol ( -9999 ),
size (
0 )
{
//cout << " *** tree values *** " << endl;
for ( int i = 0; i < n ; i++ ) {
//cout << " " << *p++ ;
// empty simbol
if ( 0 == i ) {
this->empty_symbol = *p;
} else {
// always insert in root
this->m_tree_insert( this->root, *p);
}
p++;
}
//cout << endl ;
};
// destructor
~BTree()
{
cout << "~BTree()" << endl ;
// dealocate memory
this->m_destroyTree( this->root );
// reset inner data to defaults
this->root =
NULL ;
this->empty_symbol = -9999 ;
this->size =
0 ;
};
// find the pointer
where the position points to
TNode* convertpos(int
position)
{
TNode* node = this->m_tree_search(this->root, position);
if (node)
cout << " *** search: " << position << " exists
in tree " << endl ;
else
cout << " *** search: " << position << " no such
key " << endl ;
return node; // this is null if node not located in tree
}
void add2left(TNode
*newnode, TNode *p)
{
if ( p && newnode )
p->left = newnode;
}
void add2right(TNode
*newnode, TNode *p)
{
if ( p && newnode )
p->right = newnode;
}
void add2left(TNode
*newnode, int position)
{
TNode* p = this->m_tree_search(this->root, position);
this->add2left(newnode, p);
}
void add2right(TNode
*newnode, int position)
{
TNode* p = this->m_tree_search(this->root, position);
this->add2right(newnode, p);
}
void add2left(BTree
*newsubtree, int position)
{
TNode* p = this->m_tree_search(this->root, position);
if ( p && newsubtree && newsubtree->root )
p->left = newsubtree->root;
}
void add2right(BTree
*newsubtree, int position)
{
TNode* p = this->m_tree_search(this->root, position);
if ( p && newsubtree && newsubtree->root )
p->right = newsubtree->root;
}
// remove a no by
position
void removeleaf(int
position)
{
cout << " *** delete position [" << position <<
"] " << endl ;
TNode* node = this->m_tree_search(this->root, position);
if ( node && node->parent /* delete root is not supported */ ) {
//int node_size = m_get_size( node );
//cout << " *** deleted [" << node_size << "]
elements " << endl ;
this->m_tree_delete( this->root, node );
return;
}
cout << " deleted [0] elements, key not in tree [" << position << "] " << endl ;
}
// remove a node by
pointer ..
void removeleaf(TNode
*p)
{
if ( p )
this->removeleaf( p->val );
}
//swap-the-values is
fine
void swapnodes(TNode*
n1, TNode *n2)
{
// null check for both ..
if ( n1 && n2 ) {
int tmp = n1->val;
n1->val = n2->val;
n2->val = tmp;
}
}
// 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 return the array pointer.
//The size of the array
will be given to the variable n.
int* toarray(int
&n)
{
this->m_data.clear();
this->m_data.push_back( this->empty_symbol );
this->m_in_order( this->root, true /*print_to_arr*/ );
n = (int)this->m_data.size();
//cout << " *** sz = " << n << endl ;
return &this->m_data[0]; // return the inner array
}
// pre_order
traversing (Root, Left, Right)
void
print_pre_order()
{
cout << " print [pre order] (Root, Left, Right) " <<
endl;
this->m_pre_order( this->root );
cout << endl;
};
// in_order
traversing (Left, Root, Right)
void
print_in_order()
{
cout << " print [in order] (Left, Root, Right)" <<
endl;
this->m_in_order( this->root );
cout << endl;
};
// post_order
traversing (Left, Right, Root)
void
print_post_order()
{
cout << " print [post order] (Left, Right, Root) " <<
endl;
this->m_post_order( this->root );
cout << endl;
};
// return whether
this BT is a valid BST
bool isValidBST() {
if ( this->root && (this->size > 0))
return true;
else
return false;
}
};
// Determine whether the array forms a valid BT.
// the input format is the same as the above
bool isValidBT(const int *p, const int n)
{
// check p is not NULL and first value is
0
if ( p && (*p == 0) )
return true;
return false;
}
int main()
{
// declare our array of integers:
int tree_values[] = {0/*empty symbol*/, 16, 2,
77, 29};
cout << endl << "tree_1 init with
values : {0/*empty symbol*/, 16, 2, 77, 29}" << endl ;
BTree tree_1 = BTree(tree_values, 5 );
cout << endl << "tree_1 :
print_in_order" << endl ;
tree_1.print_in_order();
cout << endl << "tree_2 : Copy
C-tor -> object" << endl ;
BTree tree_2 = BTree( tree_1 );
cout << endl << "tree_3 : Copy
C-tor -> pointer" << endl ;
BTree tree_3 = BTree( tree_1.root );
cout << endl << "tree_1 :
print_in_order" << endl ;
tree_3.print_in_order ();
cout << endl <<
"tree_1.removeleaf(2) " << endl ;
tree_1.removeleaf(2);
cout << endl << "tree_1 :
print_in_order" << endl ;
tree_1.print_in_order ();
cout << endl << "tree_2 :
print_in_order" << endl ;
tree_2.print_in_order ();
cout << endl << "tree_2 : toarray() -> print values " << endl ;
int n = -1;
int* arr = tree_2.toarray(n);
cout << endl << endl ;
for ( int i = 0; i < n ; i++ ) {
cout << " ["
<< *arr++ << "] ";
}
cout << endl << endl << " testing swap " << endl ;
TNode* p_77 = tree_1.convertpos( 77 );
TNode* p_29 = tree_1.convertpos( 29 );
cout << endl ;
if ( p_77 && p_29 ) {
cout << " p_77->val = " << p_77->val << " , p_29->val = " << p_77->val << endl ;
tree_1.swapnodes(p_77, p_29);
cout << "
p_77->val = " << p_77->val << " , p_29->val =
" << p_77->val << endl ;
}
cout << endl << " testing is
isValidBST() " << endl ;
cout << endl << "is_valid_bst
tree_1
: " << ( tree_1.isValidBST() ? "TRUE" : "FALSE" ) ;
BTree empty_tree = BTree();
cout << endl << "is_valid_bst new tree (no data) : " << ( empty_tree.isValidBST() ? "TRUE" : "FALSE" ) ;
cout << endl << endl ;
return 0;
}
#include<iostream> using namespace std; class TNode { public: int val; TNode(){} TNode(int v){val = v;} TNode...
class BTree { private: int size; Node* root; public: // constructors BTree() : root(nullptr), size(0) {} // default constructor BTree(const BTree& other); // copy constructor BTree(BTree&& other); // move constructor BTree& operator=(const BTree& other); BTree& operator=(BTree&& other); }; Implement the following function BTree& BTree::operator=(BTree&& other) { if (this != &other) { } return *this; } Can you implement the move assigment and the move constructor
#include <iostream> #include <cstddef> using std::cout; using std::endl; class Node { int value; public: Node* left; // left child Node* right; // right child Node* p; // parent Node(int data) { value = data; left = NULL; right = NULL; p = NULL; } ~Node() { } int d() { return value; } void print() { std::cout << value << std::endl; } }; int main(int argc, const char * argv[]) { } function insert(Node *insert_node, Node *tree_root){ //Your code here...
C++ LinkedList I need the code for copy constructor and assignment operator #include <iostream> #include <string> using namespace std; typedef string ItemType; struct Node { ItemType value; Node *next; }; class LinkedList { private: Node *head; // You may add whatever private data members or private member functions you want to this class. void printReverseRecursiveHelper(Node *temp) const; public: // default constructor LinkedList() : head(nullptr) { } // copy constructor LinkedList(const LinkedList& rhs); // Destroys all the dynamically allocated memory //...
#code for creature.cpp #include <iostream> using namespace std; class Creature { public: Creature(); void run() const; protected: int distance; }; Creature::Creature(): distance(10) {} void Creature::run() const { cout << "running " << distance << " meters!\n"; } class Wizard : public Creature { public: Wizard(); void hover() const; private: int distFactor; }; Wizard::Wizard() : distFactor(3) {} void Wizard::hover() const { cout << "hovering " << (distFactor * distance) << " meters!\n"; } //Created new derived class from Creature class Widget...
#ifndef PROCESSREQUESTRECORD_CLASS #define PROCESSREQUESTRECORD_CLASS #include <iostream> #include <string> using namespace std; class procReqRec { public: // default constructor procReqRec() {} // constructor procReqRec(const string& nm, int p); // access functions int getPriority(); string getName(); // update functions void setPriority(int p); void setName(const string& nm); // for maintenance of a minimum priority queue friend bool operator< (const procReqRec& left, const procReqRec& right); // output a process request record in the format // name: priority friend ostream& operator<< (ostream& ostr, const procReqRec&...
C++ program: Convert the classes to template classes #include <iostream> #include <string> using namespace std; class Node { private: int data; Node* next; public: Node(int data) { this->data=data; this->next = 0; } int getData(){return data;} Node* getNext(){return next;} void setNext(Node* next){this->next=next;} }; class LinkedList { private: Node* head = 0; public: int isEmpty() {return head == 0;} void print() { Node* currNode = head; while(currNode!=0) { cout << currNode->getData() << endl; currNode = currNode->getNext(); } } void append(int data) {...
#include <iostream> using namespace std; int main(void) { int SIZE; cout<<"Enter the size of the array"<<endl; cin>>SIZE; int *numlist = new int[SIZE]; // Read SIZE integers from the keyboard for (int i = 0; i<SIZE; i++ ) { cout << "Enter value #" << i+1 << ": "; cin >> numlist[i]; } // Display the numbers in a reverse order for (int i = SIZE; i > 0; i--...
// PLACE YOUR NAME HERE #include <iostream> using namespace std; float findAverage (int [], int); // finds average of all //grades int findHighest (int [], int); // finds highest of all //grades int findFirstFail( int[]); int main() { int grades[100]; // the array holding 100 grades. int numberOfGrades; // the number of grades read. int pos; // index to the array. float avgOfGrades; // contains the average of the grades. int highestGrade; // contains the highest grade. int inderOfFail; //...
Please help me with FLOWCHART and UML diagram for class, thank you! #include <iostream> #include <fstream> #define MAX 10 using namespace std; class WordListTree { public: // Structure of a node struct Node { string key; // Create an array of up to MAX children Node* child[MAX]; }; // Create a tree of strings Node* newNode(string key) { Node* temp = new Node; (*temp).key =...
USING THIS CODE: #include <iostream> #include <string> using namespace std; class Contact { //this class cannot be viewed from outside of the private class. //only the class functions within the class can access private members. private: string name; string email; string phone; //the public class is accessible from anywhere outside of the class //however can only be within the program. public: string getName() const { return name; } void setName(string name) { this->name = name; } string getEmail() const {...