Find Minimum node make it Root node attach rest of Tree with it such that BST property is not violated

Find Minimum node make it Root node attach rest of Tree with it such that BST property is not violated 


#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* 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 min_to_root(){
root->data=(findMin(root)->data);
remove(root->left,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.min_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.