Question
#include using namespace std; //===================================================================== struct Node { int x; Node * left; Node * right; Node(){left = NULL; right = NULL;} Node(int d, Node*
#include
using namespace std;
//=====================================================================
struct Node
{
int x;
Node * left;
Node * right;
Node(){left = NULL; right = NULL;}
Node(int d, Node* l = 0, Node* r = 0)
{
x = d;
left = l;
right = r;
}
};
//=====================================================================
class Tree
{
private:
Node * root;
public:
Tree()
{
root = NULL;
}
//-----------------------------------------------------------------
void insert(int x)
{
Node * ptr = new Node(x);
cout << " -------------------------------------" << endl;
cout << "Node Address: " << ptr << endl;
if (root == NULL)
root = ptr;
else
{
Node * temp = root;
while (true)
{
if (temp -> x > x)
{
if (temp -> left == NULL)
{
cout << "Node Parent Address: " << temp << endl;
cout << "Node Parent Value: " << temp -> x << endl;
temp -> left = ptr; break;
} else
temp = temp -> left;
} else
{
if (temp -> right == NULL)
{
cout << "Node Parent Address: " << temp << endl;
cout << "Node Parent Value: " << temp -> x << endl;
temp -> right = ptr;
break;
} else
temp = temp -> right;
}
}
}
cout << "Root: " << root << endl;
cout << "-------------------------------------" << endl;
}
//-----------------------------------------------------------------
public: void inOrder(){ inOrder(root); }
private: void inOrder(Node * temp) {
if (temp != NULL)
{
inOrder(temp -> left);
cout << temp -> x << " ";
inOrder(temp -> right);
}
}
//-----------------------------------------------------------------
public: void preOrder(){ inOrder(root); }
private: void preOrder(Node * temp)
{
if (temp != NULL) {
cout << temp -> x << " ";
preOrder(temp -> left);
preOrder(temp -> right);
}
}
//-----------------------------------------------------------------
public: void postOrder(){ inOrder(root); }
private: void postOrder(Node * temp)
{
if (temp != NULL) {
postOrder(temp -> left);
postOrder(temp -> right);
cout << temp -> x << " ";
}
}
//-----------------------------------------------------------------
public: void serial(){ serial(root); }
private: void serial(Node *n)
{
cout << '(';
if (n != 0)
{
cout << n->x << ' ';
serial(n->left); cout << ' ';
serial(n->right);
}
cout << ')';
}
//-----------------------------------------------------------------
public: Node * getRoot() {
return root;
}
//-----------------------------------------------------------------
public: void display(){ display(root); }
private: void display(Node * temp)
{
if (temp != NULL) {
cout << endl;
cout << "Parent: " << temp -> x << endl;
cout << " Left Child of " << temp -> x << ": ";
if (temp -> left == NULL) cout << "NULL" << endl;
else
cout << temp -> left -> x << endl;
cout << " Right Child of " << temp -> x << ": ";
if (temp -> right == NULL)
cout << "NULL" << endl;
else
cout << temp -> right -> x << endl;
display(temp -> left);
display(temp -> right);
}
}
//-----------------------------------------------------------------
bool isEmpty()
{
if (root == NULL)
return true;
return false;
}
public:
//-----------------------------------------------------------------
void removeAll(int value)
{
while (true)
{
Node * temp = root, * ptemp = root;
while (temp != NULL && temp -> x != value)
{
ptemp = temp;
if (temp -> x < value)
temp = temp -> right;
else if (temp -> x > value)
temp = temp -> left;
}
if (temp == NULL)
{
cout << "All nodes cotaining " << value << " are deleted" << endl;
break;
} else
{
if (temp -> left == NULL && temp -> right == NULL)
{
if (temp == root)
root = NULL;
else if (ptemp -> left == temp)
ptemp -> left = NULL;
else if (ptemp -> right == temp)
ptemp -> right = NULL;
} else if (temp -> left == NULL && temp -> right != NULL)
{
if (temp == root)
root = temp -> right;
else if (ptemp -> left == temp)
ptemp -> left = temp -> right;
else if (ptemp -> right == temp)
ptemp -> right = temp -> left;
} else if (temp -> right == NULL && temp -> left != NULL)
{
if (temp == root)
root = temp -> left;
else if (ptemp -> left == temp)
ptemp -> left = temp -> left;
else if (ptemp -> right == temp)
ptemp -> right = temp -> right;
} else if (temp -> left != NULL && temp -> right != NULL)
{
Node * tempHolder = temp, * ptempHolder = temp;
while (tempHolder -> left != NULL)
{
ptempHolder = tempHolder;
tempHolder = tempHolder -> left;
}
temp -> x = tempHolder -> x;
ptempHolder -> left = tempHolder -> right;
temp = tempHolder;
}
delete temp;
cout << "Node Removed Successfully." << endl;
}
}
}
//-----------------------------------------------------------------
void remove(int value)
{
Node * temp = root, * ptemp = root;
while (temp != NULL && temp -> x != value)
{
ptemp = temp;
if (temp -> x < value)
temp = temp -> right;
else if (temp -> x > value)
temp = temp -> left;
}
if (temp == NULL) {
cout << "Value Not Found...." << endl;
} else
{
if (temp -> left == NULL && temp -> right == NULL)
{
if (temp == root)
root = NULL;
else if (ptemp -> left == temp)
ptemp -> left = NULL;
else if (ptemp -> right == temp)
ptemp -> right = NULL;
} else if (temp -> left == NULL && temp -> right != NULL)
{
if (temp == root)
root = temp -> right;
else if (ptemp -> left == temp)
ptemp -> left = temp -> right;
else if (ptemp -> right == temp)
ptemp -> right = temp -> left;
} else if (temp -> right == NULL && temp -> left != NULL)
{
if (temp == root)
root = temp -> left;
else if (ptemp -> left == temp)
ptemp -> left = temp -> left;
else if (ptemp -> right == temp)
ptemp -> right = temp -> right;
} else if (temp -> left != NULL && temp -> right != NULL)
{
Node * tempHolder = temp, * ptempHolder = temp;
while (tempHolder -> left != NULL)
{
ptempHolder = tempHolder;
tempHolder = tempHolder -> left;
}
temp -> x = tempHolder -> x;
ptempHolder -> left = tempHolder -> right;
temp = tempHolder;
}
delete temp;
cout << "Node Removed Successfully." << endl;
}
}
//-----------------------------------------------------------------
void deleteAllNodes(Node * temp) {
if (temp != NULL) {
deleteAllNodes(temp -> left);
deleteAllNodes(temp -> right);
cout << "Address: " << temp << endl;
cout << "Value: " << temp -> x << endl << endl;
delete temp;
}
}
//-----------------------------------------------------------------
~Tree() {
cout << "Below Nodes Deleted Successfully:" << endl;
deleteAllNodes(root);
}
};
//=====================================================================
int main(){
Tree T, S;
T.insert(50);
T.insert(20);
T.insert(80);
T.insert(60);
T.insert(90);
T.display();
T.serial(); cout << endl;
S = T;
S.serial(); cout << endl;
T.insert(100);
cout << "After insert 100 ";
T.serial(); cout << endl;
S.serial(); cout << endl;
system("pause");
return 0;
}
/* (50 (20 () ()) (80 (60 () ()) (90 () ())))
(50 (20 () ()) (80 (60 () ()) (90 () ()))
-------------------------------------
Node Address: 0x941a40
Node Parent Address: 0x941a20
Node Parent Value: 90
Root: 0x941500
-------------------------------------
After insert 100 (50 (20 () ()) (80 (60 () ()) (90 () (100 () ()))))
(50 (20 () ()) (80 (60 () ()) (90 () (100 () ()))))
*/
1) find1, an iterative version of find that takes an int parameter and looks for it in the tree. Return NULL if not found, or a pointer to the Node containing the value if found.
2) find2, a recursive version of the method.
3) node_count, returns a count of the number of nodes in the tree.
4) depth, returns the depth of the deepest node in the tree. A null tree will have depth zero, a one node tree depth 1
C++
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
Secrets Of Analytical Leaders Insights From Information Insiders
Authors: Wayne Eckerson
1st Edition
1935504347, 9781935504344
