Take Maximum Node Make it Root Node

Take Maximum Node Make it Root Node and attach rest of tree with it so that BST Property will not volatilized 

#include<iostream.h>
#include<conio.h>
class Node{
private:
int data,i;
Node* right,*q,*p;
Node* left;
public:
Node(){
root=NULL;
right=left=NULL;
}Node *root;


Node* remove(Node *root, int value){
Node *t;
int cmpr = value - root->data;
if (cmpr < 0){
t = remove(root->left, value);
root->left = t;
} else if (cmpr > 0){
t = remove(root->right, value);
root->right = t;
} else if (root->left != NULL && root->right != NULL){
Node* minNode;
minNode = findMin(root->right);
root->data = minNode->data;
t = remove(root->right, minNode->data);
root->right = t;
} else {
Node* nodeToDelete = root;
if (root->left == NULL)
root = root->right;
else if (root->right == NULL)
root = root->left;
else root = NULL;
delete nodeToDelete;
}       return root;
}

void insert(int data){
Node* newnode = new Node();
newnode->data = data;
if (root == NULL){
root=newnode;
return;
}       Node *p,*q;
p=q=root;
while (q!=NULL){
p=q;
if (newnode->data> q->data)
q = q->right;
else q = q->left;
}
if (newnode->data> p->data)
p->right = newnode;
else p->left = newnode;
}

Node* findMax(Node* te)
{
if (te->right == NULL){
return te;           }
return findMax(te->right);
}

Node* findMin(Node* te)
{
if (te->left == NULL){
return te;           }
return findMin(te->left);
}

 void _preorder(Node *root){
if (root == NULL) return;
else {  B[i]=root->data;
i++;
_preorder(root->left);
_preorder(root->right);
} }

void preorder(Node *root){
if (root == NULL) return;
else {  cout <<root->data <<"  ";B[i]=root->data;
i++;
preorder(root->left);
preorder(root->right);
} }

void inorder(Node *root){
if (root == NULL) return;
else {
inorder(root->left);
cout << root->data <<"  ";
inorder(root->right);
} }



 void Max_to_root(){
root->data=(findMax(root)->data);
remove(root->right,root->data);
i=0;
cout<<endl;
_preorder(root);
}
int B[];


};

void main()
{
int c,A[]={9,4,3,2,5,6,8,1,33,12,44};
Node b,obj;
clrscr();
for(int i=0;i<=10;i++){
b.insert(A[i]); }
cout<<"\n\nInorder triversal: ";
b.inorder(b.root);
cout<<"\n\nPreOrder triversal: ";
b.preorder(b.root);
b.Max_to_root();

   for(int j=0;j<=10;j++){
   obj.insert(obj.B[j]);}

  cout<<"\n\nAfter Process: \n\nInorder: ";
  obj.inorder(b.root);

  cout<<"\n\nPreorder: ";
  obj.preorder(b.root);

   getch();
}

No comments

Powered by Blogger.