#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 =...
Binary Tree Template Write your own version of a class template that will create a binary tree that can hold values of any data type. Demonstrate the class with a driver program. Place your binary tree template in it's own header file, Btree.h. Include methods for the following: inserting new values into the tree removing nodes from the tree searching the tree returning the number of nodes in the tree displaying the contents of the tree using preorder traversal Your...