Question
//Complete function: pair sort(Node* p); //pair Tree::sort(Node* p) { // write code below //use recursion, but while loop is allowed. //sorting such that ascending sequence
//Complete function: pair
//pair
// write code below
//use recursion, but while loop is allowed.
//sorting such that ascending sequence in pre-order traversal
//function returns a pair of pointers, which point to the node with the smallest value and the node with the largest values in the tree rooted at node //pointed by p.
//}
#include
#include
using namespace std;
class Node {
public:
int value;
Node* l_child;
Node* r_child;
Node() : l_child(nullptr), r_child(nullptr) {}
Node(int i) :value(i), l_child(nullptr), r_child(nullptr) {}
};
class Tree {
public:
Node* root;
Tree() : root(nullptr) {}
Node* makeTree(int n, int m);
void printTree1(Node* p);
void printTree2(Node* p); //pre-order printing
void printTree3(Node* p);
void mirror(Node* p);
int sum(Node* p);
Node* mirrorCopy(Node* p);
void minHeap(Node* p);
pair
Node* Tree::mirrorCopy(Node* p) {
if (!p) return nullptr;
if (!p->l_child) return p;
Node* p1, * p2;
p1 = mirrorCopy(p->l_child);
p2 = mirrorCopy(p->r_child);
if (p1->value > p2->value) {
swap(p->l_child, p->r_child);
swap(p1, p2);
}
if (p->value > p2->value) swap(p->value, p2->value);
if ((p->l_child->value < p->value) || (p->r_child->value < p->value)) {
if (p->l_child->value <= p->r_child->value) {
int i = p->value;
p->value = p->l_child->value;
p->l_child->value = i;
mirrorCopy(p->l_child);
}
else {
int i = p->value;
p->value = p->r_child->value;
p->r_child->value = i;
mirrorCopy(p->r_child);
}
}
return p2;
}
void Tree::minHeap(Node* p) {
if (!p || !p->l_child || !p->r_child) return;
minHeap(p->l_child);
minHeap(p->r_child);
if ((p->l_child->value < p->value) || (p->r_child->value < p->value)) {
if (p->l_child->value <= p->r_child->value) {
int i = p->value;
p->value = p->l_child->value;
p->l_child->value = i;
minHeap(p->l_child);
}
else {
int i = p->value;
p->value = p->r_child->value;
p->r_child->value = i;
minHeap(p->r_child);
}
}
if (p->l_child->value < p->r_child->value) swap(p->l_child, p->r_child);
}
pair
// write code below
//use recursion, but while loop is allowed.
//sorting such that ascending sequence in pre-order traversal
//function returns a pair of pointers, which point to the node with the smallest value and the node with the largest values in the tree rooted at node pointed by p.
}
int Tree::sum(Node* p) {
if (!p) return 0;
if (!p->l_child) return p->value;
return p->value + sum(p->l_child) + sum(p->r_child);
}
void Tree::mirror(Node* p) {
if (!p || !p->l_child) return;
mirror(p->l_child);
mirror(p->r_child);
swap(p->l_child, p->r_child);
}
Node* Tree::makeTree(int n, int m) {
Node* p = new Node(rand() % m);
if (n == 1) return p;
p->l_child = makeTree(n - 1, m);
p->r_child = makeTree(n - 1, m);
return p;
}
void Tree::printTree1(Node* p) { //in-order printing
if (p == nullptr) return;
printTree1(p->l_child);
cout << p->value << " ";
printTree1(p->r_child);
}
void Tree::printTree2(Node* p) {
if (p == nullptr) return;
cout << p->value << " ";
printTree2(p->l_child);
printTree2(p->r_child);
}
void Tree::printTree3(Node* p) {
if (p == nullptr) return;
printTree3(p->l_child);
printTree3(p->r_child);
cout << p->value << " ";
}
int main() {
Tree T1;
T1.root = T1.makeTree(4, 20);
T1.printTree1(T1.root);
cout << endl;
T1.printTree2(T1.root);
cout << endl;
T1.printTree3(T1.root);
cout << endl;
Tree T2;
T2.root = T1.mirrorCopy(T1.root);
T2.printTree1(T2.root);
cout << endl;
T2.printTree2(T2.root);
cout << endl;
T2.printTree3(T2.root);
cout << endl;
T2.minHeap(T2.root);
T2.printTree1(T2.root);
cout << endl;
T2.printTree2(T2.root);
cout << endl;
T2.printTree3(T2.root);
cout << endl;
Tree T3;
T3.root = T3.makeTree(5, 20);
T3.sort(T3.root);
T3.printTree1(T3.root);
cout << endl;
T3.printTree2(T3.root);
cout << endl;
T3.printTree3(T3.root);
cout << endl;
return 0;
}
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started