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();
}
#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();
}
0 comments:
Post a Comment