Today Pageviews
Facebook Page
Featured Post
Upload file from URL to Server using cURL in PHP
This Post show how to upload data or audio files on server getting from URL and how to download that file in PC using URL. First put URL...
Categories
- Data Structure
- C++
- Interesting Programs
- programming
- Assembly Language
- COAL
- web development
- tree
- html
- css
- Article's
- web designing
- php
- C Programming
- C#
- Data base
- java-script
- Android
- Java
- liner algabra
- Sorting
- .net
- Queue
- SQL
- link list
- Projects
- Stack
- Interfaces
- advance
- Matlab
- ajax
- heap
- jquery
- xml
- E-books
- computer tricks
- vb.net
Pages
Labels
Data Structure
(57)
C++
(52)
Interesting Programs
(50)
programming
(32)
Assembly Language
(31)
COAL
(31)
web development
(31)
tree
(24)
html
(22)
css
(21)
Article's
(20)
web designing
(20)
php
(17)
C Programming
(15)
C#
(15)
Data base
(11)
java-script
(10)
Android
(9)
Java
(9)
liner algabra
(9)
Sorting
(8)
.net
(7)
Queue
(7)
SQL
(7)
link list
(7)
Projects
(6)
Stack
(5)
Interfaces
(4)
advance
(3)
Matlab
(2)
ajax
(2)
heap
(2)
jquery
(2)
xml
(2)
E-books
(1)
computer tricks
(1)
vb.net
(1)
Facebook Profile
Showing posts with label tree. Show all posts
Showing posts with label tree. Show all posts
Monday, December 26, 2022
Tuesday, December 20, 2022
Wednesday, September 21, 2016
BFS (breadth first search) in BST (binary search tree)
BFS code in red color highlighted.
1) Insertion in BST
2) Normal Searching in BST.
3) BFS in BST
#include<iostream.h>
#include<conio.h>
class Node{
private:
int data;
Node* right;
Node* left;
public:
Node(){
root=NULL;
right=left=NULL;
}Node *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;
}
void inorder(Node *root){
if (root == NULL) return;
else {
cout << root->data <<" ";
inorder(root->left);
// cout << root->data <<" ";
inorder(root->right);
}
}
void search(Node *root,int v)
{
int flag=0;
Node *q=root;
while(v != q->data)
{
if(v < q->data && q->left != NULL)
{
flag=2;
q=q->left;
}
else if( v > q->data && q-right !=NULL)
{
flag=2;
q=q->right;
}else{
flag=1;
cout<<"\n Node value not found . "<<endl;
break;
}
}
if(flag == 0 || flag ==2){
cout<<"\nNode is found= "<<q->data<<endl;
}
}
void BFS(Node* root,int value){
Node **arry=NULL;
int i=0,j=0;
arry[i]=root;
if(root->data == value){
cout<<root->data<<" ";
}
else{ i++;
while(arry[j]->data != value){
Node *a=arry[j];
if(a->left != NULL)
{
arry[i]=a->left;i++;
if( a->left->data==value)
{break;}
}
if(a->right !=NULL)
{
arry[i]=a->right;i++;
if(a->right->data==value)
{break;}
}
j++;}//end of loop
for(int x=0;x<=(sizeof(arry)/sizeof(*arry));x++){
cout<<arry[x]->data<<" ";
}//end of for
}//end of else
}//end of function
};
void main()
{
int c,A[]={8,4,5,1,12,11,13,3,14};
Node b;
clrscr();
for(int i=0;i<=8;i++){
b.insert(A[i]);
}
b.inorder(b.root);
getch();
cout<<"\n\nEnter Value For Search ";cin>>c;
b.BFS(b.root,c);
getch();
// b.search(b.root,c);
//getch();
// cout<<"\n\nInsert a New Value ";cin>>c;
// b.insert(c);
// b.inorder(b.root);
// getch();
}
1) Insertion in BST
2) Normal Searching in BST.
3) BFS in BST
#include<iostream.h>
#include<conio.h>
class Node{
private:
int data;
Node* right;
Node* left;
public:
Node(){
root=NULL;
right=left=NULL;
}Node *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;
}
void inorder(Node *root){
if (root == NULL) return;
else {
cout << root->data <<" ";
inorder(root->left);
// cout << root->data <<" ";
inorder(root->right);
}
}
void search(Node *root,int v)
{
int flag=0;
Node *q=root;
while(v != q->data)
{
if(v < q->data && q->left != NULL)
{
flag=2;
q=q->left;
}
else if( v > q->data && q-right !=NULL)
{
flag=2;
q=q->right;
}else{
flag=1;
cout<<"\n Node value not found . "<<endl;
break;
}
}
if(flag == 0 || flag ==2){
cout<<"\nNode is found= "<<q->data<<endl;
}
}
void BFS(Node* root,int value){
Node **arry=NULL;
int i=0,j=0;
arry[i]=root;
if(root->data == value){
cout<<root->data<<" ";
}
else{ i++;
while(arry[j]->data != value){
Node *a=arry[j];
if(a->left != NULL)
{
arry[i]=a->left;i++;
if( a->left->data==value)
{break;}
}
if(a->right !=NULL)
{
arry[i]=a->right;i++;
if(a->right->data==value)
{break;}
}
j++;}//end of loop
for(int x=0;x<=(sizeof(arry)/sizeof(*arry));x++){
cout<<arry[x]->data<<" ";
}//end of for
}//end of else
}//end of function
};
void main()
{
int c,A[]={8,4,5,1,12,11,13,3,14};
Node b;
clrscr();
for(int i=0;i<=8;i++){
b.insert(A[i]);
}
b.inorder(b.root);
getch();
cout<<"\n\nEnter Value For Search ";cin>>c;
b.BFS(b.root,c);
getch();
// b.search(b.root,c);
//getch();
// cout<<"\n\nInsert a New Value ";cin>>c;
// b.insert(c);
// b.inorder(b.root);
// getch();
}
Thursday, June 11, 2015
DFS tree in C++
#include<iostream.h>
#include<conio.h>
int cost[10][10],i,j,k,n;
int stack[10],top,v,visit[10],visited[10];
void main()
{
clrscr();
int m;
cout <<"Enter no of vertices\Nodes: ";
cin >> n;
cout <<"\nEnter no of Edges: ";
cin >> m;
cout <<"\n\tEnter All EDGES Source & Distination\n";
for(k=1;k<=m;k++)
{
cout<<"\nEnter Source: ";
cin >>i;
cout<<"\nEnter Distination: ";
cin>>j;
cost[i][j]=1;
cout<<"\n-----------------------\n";
}
cout <<"\nEnter initial vertex: ";
cin >>v;
cout <<"\nORDER OF VISITED VERTICES:\n";
cout <<v<<" ";
visited[v]=1;
k=1;
while(k<n)
{
for(j=n;j>=1;j--)
if(cost[v][j]!=0 && visited[j]!=1 && visit[j]!=1)
{
visit[j]=1;
stack[top]=j;
top++;
}
v=stack[--top];
cout<<v << " ";
k++;
visit[v]=0;
visited[v]=1;
}
getch();
}
#include<conio.h>
int cost[10][10],i,j,k,n;
int stack[10],top,v,visit[10],visited[10];
void main()
{
clrscr();
int m;
cout <<"Enter no of vertices\Nodes: ";
cin >> n;
cout <<"\nEnter no of Edges: ";
cin >> m;
cout <<"\n\tEnter All EDGES Source & Distination\n";
for(k=1;k<=m;k++)
{
cout<<"\nEnter Source: ";
cin >>i;
cout<<"\nEnter Distination: ";
cin>>j;
cost[i][j]=1;
cout<<"\n-----------------------\n";
}
cout <<"\nEnter initial vertex: ";
cin >>v;
cout <<"\nORDER OF VISITED VERTICES:\n";
cout <<v<<" ";
visited[v]=1;
k=1;
while(k<n)
{
for(j=n;j>=1;j--)
if(cost[v][j]!=0 && visited[j]!=1 && visit[j]!=1)
{
visit[j]=1;
stack[top]=j;
top++;
}
v=stack[--top];
cout<<v << " ";
k++;
visit[v]=0;
visited[v]=1;
}
getch();
}
Breadth First Search (BFS) in Graphs Algorithm Code in C++
#include<iostream.h>
#include<conio.h>
int cost[10][10],i,j,k,n;
int que[10],front,rare,v,visit[10],visited[10];
void main()
{
clrscr();
int m;
cout <<"Enter no of vertices\ Nodes: ";
cin >> n;
cout <<"\nEnter no of Edges: ";
cin >> m;
cout <<"\n\tEnter All EDGES by source & destination\n";
for(k=1;k<=m;k++)
{
cout<<"\nEnter Source: ";
cin >>i;
cout<<"\nEnter Destination: ";
cin>>j;
cost[i][j]=1;
cout<<"\n-----------------------\n";
}
cout <<"\nEnter initial vertex: ";
cin >>v;
cout <<"Visitied vertices:\n";
cout << v<<" ";
visited[v]=1;
k=1;
while(k<n)
{
for(j=1;j<=n;j++)
if(cost[v][j]!=0 && visited[j]!=1 && visit[j]!=1)
{
visit[j]=1;
que[rare++]=j;
}
v=que[front++];
cout<<v << " ";
k++;
visit[v]=0;
visited[v]=1;
}
getch();
}
#include<conio.h>
int cost[10][10],i,j,k,n;
int que[10],front,rare,v,visit[10],visited[10];
void main()
{
clrscr();
int m;
cout <<"Enter no of vertices\ Nodes: ";
cin >> n;
cout <<"\nEnter no of Edges: ";
cin >> m;
cout <<"\n\tEnter All EDGES by source & destination\n";
for(k=1;k<=m;k++)
{
cout<<"\nEnter Source: ";
cin >>i;
cout<<"\nEnter Destination: ";
cin>>j;
cost[i][j]=1;
cout<<"\n-----------------------\n";
}
cout <<"\nEnter initial vertex: ";
cin >>v;
cout <<"Visitied vertices:\n";
cout << v<<" ";
visited[v]=1;
k=1;
while(k<n)
{
for(j=1;j<=n;j++)
if(cost[v][j]!=0 && visited[j]!=1 && visit[j]!=1)
{
visit[j]=1;
que[rare++]=j;
}
v=que[front++];
cout<<v << " ";
k++;
visit[v]=0;
visited[v]=1;
}
getch();
}
Saturday, June 6, 2015
AVL Balance Tree in C++
AVL TREE IMPLEMENTAION:
#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
struct avl_node
{
int data;
struct avl_node *left;
struct avl_node *right;
}*root;
int max(int a,int b){
if (a>b){
return a;}
else { return b;
}
}
class avlTree
{
public:
avlTree()
{
root = NULL;
}
int height(avl_node *temp)
{
int h = 0;
if (temp != NULL)
{
int l_height = height (temp->left);
int r_height = height (temp->right);
int max_height = max (l_height, r_height);
h = max_height + 1;
}
return h;
}
int diff(avl_node *temp)
{
int l_height = height (temp->left);
int r_height = height (temp->right);
int b_factor= l_height - r_height;
return b_factor;
}
avl_node* rr_rotation(avl_node *parent)
{
avl_node *temp;
temp = parent->right;
parent->right = temp->left;
temp->left = parent;
return temp;
}
avl_node *ll_rotation(avl_node *parent)
{
avl_node *temp;
temp = parent->left;
parent->left = temp->right;
temp->right = parent;
return temp;
}
avl_node* lr_rotation(avl_node *parent)
{
avl_node *temp;
temp = parent->left;
parent->left = rr_rotation (temp);
return ll_rotation (parent);
}
avl_node *rl_rotation(avl_node *parent)
{
avl_node *temp;
temp = parent->right;
parent->right = ll_rotation (temp);
return rr_rotation (parent);
}
avl_node* balance(avl_node *temp)
{
int bal_factor = diff (temp);
if (bal_factor > 1)
{
if (diff (temp->left) > 0)
temp = ll_rotation (temp);
else
temp = lr_rotation (temp);
}
else if (bal_factor < -1)
{
if (diff (temp->right) > 0)
temp = rl_rotation (temp);
else
temp = rr_rotation (temp);
}
return temp;
}
avl_node *insert(avl_node *root, int value)
{
if (root == NULL)
{
root = new avl_node;
root->data = value;
root->left = NULL;
root->right = NULL;
return root;
}
else if (value < root->data)
{
root->left = insert(root->left, value);
root = balance (root);
}
else if (value >= root->data)
{
root->right = insert(root->right, value);
root = balance (root);
}
return root;
}
void display(avl_node *ptr, int level)
{
int i;
if (ptr!=NULL)
{
display(ptr->right, level + 1);
cout<<endl;
if (ptr == root)
cout<<"Root -> ";
for (i = 0; i < level && ptr != root; i++)
cout<<" ";
cout<<ptr->data;
display(ptr->left, level + 1);
}
}
void inorder(avl_node *tree)
{
if (tree == NULL)
return;
inorder (tree->left);
cout<<tree->data<<" ";
inorder (tree->right);
}
void preorder(avl_node *tree)
{
if (tree == NULL)
return;
cout<<tree->data<<" ";
preorder (tree->left);
preorder (tree->right);
}
void postorder(avl_node *tree)
{
if (tree == NULL)
return;
postorder ( tree ->left );
postorder ( tree ->right );
cout<<tree->data<<" ";
}
};
void main()
{
int choice, item;
avlTree avl;
clrscr();
while (1)
{
cout<<"\n\n-----------------------------------\n"<<endl;
cout<<" AVL Tree Implementation "<<endl;
cout<<"\n---------------------------------------\n"<<endl;
cout<<"[ 1. Insert Element into the tree]"<<endl;
cout<<"[ 2. Display Balanced AVL Tree ]"<<endl;
cout<<"[ 3. InOrder traversal ]"<<endl;
cout<<"[ 4. PreOrder traversal ]"<<endl;
cout<<"[ 5. PostOrder traversal ]"<<endl;
cout<<"[ 6. Exit ]"<<endl<<endl;
cout<<"[ Enter your Choice:. . . .: ";
cin>>choice;
cout<<"\n\n--------------------------------------\n\n";
switch(choice)
{
case 1:
cout<<"\nHow Many Node You want to insert: ";
cin>>choice;
for(int x=0;x<=choice;x++){
cout<<"\nEnter value to be inserted: ";
cin>>item;
root = avl.insert(root, item);}
break;
case 2:
if (root == NULL)
{
cout<<"\nTree is Empty\n"<<endl;
continue;
}
cout<<"\nBalanced AVL Tree:"<<endl;
avl.display(root, 1);
break;
case 3:
cout<<"\nInorder Traversal:"<<endl;
avl.inorder(root);
cout<<endl;
break;
case 4:
cout<<"\nPreorder Traversal:"<<endl;
avl.preorder(root);
cout<<endl;
break;
case 5:
cout<<"\nPostorder Traversal:"<<endl;
avl.postorder(root);
cout<<endl;
break;
case 6:
exit(1);
break;
default:
cout<<"\nWrong Choice\n"<<endl;
}
}
}
Wednesday, May 20, 2015
Red and Black Tree in C++
RED AND BLACK TREE:
All the case's of Insertion Deletion , Searching and Display "Using typedef and Structure user define data types.
Code in C++
↓↓↓↓↓↓↓
Code is Bellow ☺ ☻ ↓↓↓↓↓↓
↓↓↓↓↓↓
Source code:
Programming Seekerz : ☺
#include <iostream.h>
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
enum rbtree_node_color { RED, BLACK };
typedef struct rbtree_node_t {
void* key;
void* value;
struct rbtree_node_t* left;
struct rbtree_node_t* right;
struct rbtree_node_t* parent;
enum rbtree_node_color color;
} *rbtree_node;
typedef struct rbtree_t {
rbtree_node root;
} *rbtree;
typedef int (*compare_func)(void* left, void* right);
rbtree rbtree_create();
void* rbtree_lookup(rbtree t, void* key, compare_func compare);
void rbtree_insert(rbtree t, void* key, void* value, compare_func compare);
void rbtree_delete(rbtree t, void* key, compare_func compare);
typedef rbtree_node node;
typedef enum rbtree_node_color color;
static node grandparent(node n);
static node sibling(node n);
static node uncle(node n);
static void verify_properties(rbtree t);
static void verify_property_1(node root);
static void verify_property_2(node root);
static color node_color(node n);
static void verify_property_4(node root);
static void verify_property_5(node root);
static void verify_property_5_helper(node n, int black_count, int* black_count_path);
static node new_node(void* key, void* value, color node_color, node left, node right);
static node lookup_node(rbtree t, void* key, compare_func compare);
static void rotate_left(rbtree t, node n);
static void rotate_right(rbtree t, node n);
static void replace_node(rbtree t, node oldn, node newn);
static void insert_case1(rbtree t, node n);
static void insert_case2(rbtree t, node n);
static void insert_case3(rbtree t, node n);
static void insert_case4(rbtree t, node n);
static void insert_case5(rbtree t, node n);
static node maximum_node(node root);
static void delete_case1(rbtree t, node n);
static void delete_case2(rbtree t, node n);
static void delete_case3(rbtree t, node n);
static void delete_case4(rbtree t, node n);
static void delete_case5(rbtree t, node n);
static void delete_case6(rbtree t, node n);
node grandparent(node n) {
//assert (n != NULL);
//assert (n->parent != NULL); /* Not the root node */
//assert (n->parent->parent != NULL); /* Not child of root */
return n->parent->parent;
}
node sibling(node n) {
//assert (n != NULL);
//assert (n->parent != NULL); /* Root node has no sibling */
if (n == n->parent->left)
return n->parent->right;
else
return n->parent->left;
}
node uncle(node n) {
//assert (n != NULL);
//assert (n->parent != NULL); /* Root node has no uncle */
//assert (n->parent->parent != NULL); /* Children of root have no uncle */
return sibling(n->parent);
}
void verify_properties(rbtree t) {
verify_property_1(t->root);
verify_property_2(t->root);
/* Property 3 is implicit */
verify_property_4(t->root);
verify_property_5(t->root);
t;
}
void verify_property_1(node n) {
//assert(node_color(n) == RED || node_color(n) == BLACK);
if (n == NULL) return;
verify_property_1(n->left);
verify_property_1(n->right);
}
void verify_property_2(node root) {
root; //assert(node_color(root) == BLACK);
}
color node_color(node n) {
return n == NULL ? BLACK : n->color;
}
void verify_property_4(node n) {
if (node_color(n) == RED) {
//assert (node_color(n->left) == BLACK);
//assert (node_color(n->right) == BLACK);
//assert (node_color(n->parent) == BLACK);
}
if (n == NULL) return;
verify_property_4(n->left);
verify_property_4(n->right);
}
void verify_property_5(node root) {
int black_count_path = -1;
verify_property_5_helper(root, 0, &black_count_path);
}
void verify_property_5_helper(node n, int black_count, int* path_black_count) {
if (node_color(n) == BLACK) {
black_count++;
}
if (n == NULL) {
if (*path_black_count == -1) {
*path_black_count = black_count;
} else {
//assert (black_count == *path_black_count);
}
return;
}
verify_property_5_helper(n->left, black_count, path_black_count);
verify_property_5_helper(n->right, black_count, path_black_count);
}
rbtree rbtree_create() {
rbtree t= new rbtree_t();
t->root = NULL;
verify_properties(t);
return t;
}
node new_node(void* key, void* value, color node_color, node left, node right) {
node newnode=new rbtree_node_t();
newnode->key = key;
newnode->value = value;
newnode->color = node_color;
newnode->left = left;
newnode->right = right;
if (left != NULL) left->parent = newnode;
if (right != NULL) right->parent = newnode;
newnode->parent = NULL;
return newnode;
}
node lookup_node(rbtree t, void* key, compare_func compare) {
node n = t->root;
while (n != NULL) {
int comp_newnode = compare(key, n->key);
if (comp_newnode == 0) {
return n;
} else if (comp_newnode < 0) {
n = n->left;
} else {
//assert(comp_newnode > 0);
n = n->right;
}
}
return n;
}
void* rbtree_lookup(rbtree t, void* key, compare_func compare) {
node n = lookup_node(t, key, compare);
return n == NULL ? NULL : n->value;
}
void rotate_left(rbtree t, node n) {
node r = n->right;
replace_node(t, n, r);
n->right = r->left;
if (r->left != NULL) {
r->left->parent = n;
}
r->left = n;
n->parent = r;
}
void rotate_right(rbtree t, node n) {
node L = n->left;
replace_node(t, n, L);
n->left = L->right;
if (L->right != NULL) {
L->right->parent = n;
}
L->right = n;
n->parent = L;
}
void replace_node(rbtree t, node oldn, node newn) {
if (oldn->parent == NULL) {
t->root = newn;
} else {
if (oldn == oldn->parent->left)
oldn->parent->left = newn;
else
oldn->parent->right = newn;
}
if (newn != NULL) {
newn->parent = oldn->parent;
}
}
void rbtree_insert(rbtree t, void* key, void* value, compare_func compare) {
node inserted_node = new_node(key, value, RED, NULL, NULL);
if (t->root == NULL) {
t->root = inserted_node;
} else {
node n = t->root;
while (1) {
int comp_newnode = compare(key, n->key);
if (comp_newnode == 0) {
n->value = value;
return;
} else if (comp_newnode < 0) {
if (n->left == NULL) {
n->left = inserted_node;
break;
} else {
n = n->left;
}
} else {
//assert (comp_newnode > 0);
if (n->right == NULL) {
n->right = inserted_node;
break;
} else {
n = n->right;
}
}
}
inserted_node->parent = n;
}
insert_case1(t, inserted_node);
verify_properties(t);
}
void insert_case1(rbtree t, node n) {
if (n->parent == NULL)
n->color = BLACK;
else
insert_case2(t, n);
}
void insert_case2(rbtree t, node n) {
if (node_color(n->parent) == BLACK)
return; /* Tree is still valid */
else
insert_case3(t, n);
}
void insert_case3(rbtree t, node n) {
if (node_color(uncle(n)) == RED) {
n->parent->color = BLACK;
uncle(n)->color = BLACK;
grandparent(n)->color = RED;
insert_case1(t, grandparent(n));
} else {
insert_case4(t, n);
}
}
void insert_case4(rbtree t, node n) {
if (n == n->parent->right && n->parent == grandparent(n)->left) {
rotate_left(t, n->parent);
n = n->left;
} else if (n == n->parent->left && n->parent == grandparent(n)->right)
{
rotate_right(t, n->parent);
n = n->right;
}
insert_case5(t, n);
}
void insert_case5(rbtree t, node n) {
n->parent->color = BLACK;
grandparent(n)->color = RED;
if (n == n->parent->left && n->parent == grandparent(n)->left)
{
rotate_right(t, grandparent(n));
} else {
//assert (n == n->parent->right && n->parent == grandparent(n)->right);
rotate_left(t, grandparent(n));
}
}
void rbtree_delete(rbtree t, void* key, compare_func compare) {
node child;
node n = lookup_node(t, key, compare);
if (n == NULL) return; /* Key not found, do nothing */
if (n->left != NULL && n->right != NULL) {
/* Copy key/value from predecessor and then delete it instead */
node pred = maximum_node(n->left);
n->key = pred->key;
n->value = pred->value;
n = pred;
}
//assert(n->left == NULL || n->right == NULL);
child = n->right == NULL ? n->left : n->right;
if (node_color(n) == BLACK) {
n->color = node_color(child);
delete_case1(t, n);
}
replace_node(t, n, child);
if (n->parent == NULL && child != NULL) // root should be black
child->color = BLACK;
// free(n);
verify_properties(t);
}
static node maximum_node(node n) {
//assert (n != NULL);
while (n->right != NULL) {
n = n->right;
}
return n;
}
void delete_case1(rbtree t, node n) {
if (n->parent == NULL)
return;
else
delete_case2(t, n);
}
void delete_case2(rbtree t, node n) {
if (node_color(sibling(n)) == RED) {
n->parent->color = RED;
sibling(n)->color = BLACK;
if (n == n->parent->left)
rotate_left(t, n->parent);
else
rotate_right(t, n->parent);
}
delete_case3(t, n);
}
void delete_case3(rbtree t, node n) {
if (node_color(n->parent) == BLACK &&
node_color(sibling(n)) == BLACK &&
node_color(sibling(n)->left) == BLACK &&
node_color(sibling(n)->right) == BLACK)
{
sibling(n)->color = RED;
delete_case1(t, n->parent);
}
else
delete_case4(t, n);
}
void delete_case4(rbtree t, node n) {
if (node_color(n->parent) == RED &&
node_color(sibling(n)) == BLACK &&
node_color(sibling(n)->left) == BLACK &&
node_color(sibling(n)->right) == BLACK)
{
sibling(n)->color = RED;
n->parent->color = BLACK;
}
else
delete_case5(t, n);
}
void delete_case5(rbtree t, node n) {
if (n == n->parent->left &&
node_color(sibling(n)) == BLACK &&
node_color(sibling(n)->left) == RED &&
node_color(sibling(n)->right) == BLACK)
{
sibling(n)->color = RED;
sibling(n)->left->color = BLACK;
rotate_right(t, sibling(n));
}
else if (n == n->parent->right &&
node_color(sibling(n)) == BLACK &&
node_color(sibling(n)->right) == RED &&
node_color(sibling(n)->left) == BLACK)
{
sibling(n)->color = RED;
sibling(n)->right->color = BLACK;
rotate_left(t, sibling(n));
}
delete_case6(t, n);
}
void delete_case6(rbtree t, node n) {
sibling(n)->color = node_color(n->parent);
n->parent->color = BLACK;
if (n == n->parent->left) {
//assert (node_color(sibling(n)->right) == RED);
sibling(n)->right->color = BLACK;
rotate_left(t, n->parent);
}
else
{
//assert (node_color(sibling(n)->left) == RED);
sibling(n)->left->color = BLACK;
rotate_right(t, n->parent);
}
}
static int compare_int(void* left, void* right);
static void print_tree(rbtree t);
static void print_tree_helper(rbtree_node n, int indent);
int compare_int(void* leftp, void* rightp) {
int left = (int)leftp;
int right = (int)rightp;
if (left < right)
return -1;
else if (left > right)
return 1;
else {
//assert (left == right);
return 0;
}
}
#define INDENT_STEP 4
void print_tree_helper(rbtree_node n, int indent);
void print_tree(rbtree t) {
print_tree_helper(t->root, 0);
puts(" ");
}
void print_tree_helper(rbtree_node n, int indent) {
int i;
if (n == NULL) {
cout<<"\n\n \t\t --< Empty tree >--\n\n ";
return;
}
if (n->right != NULL) {
print_tree_helper(n->right, indent + INDENT_STEP);
}
for(i=0; i<indent; i++)
cout<<" ";
if (n->color == BLACK)
printf(" Black: %d\n", (int)n->key);
else
printf(" Red= %d\n", (int)n->key);
if (n->left != NULL) {
print_tree_helper(n->left, indent + INDENT_STEP);
}
}
static int x=0;
int search1(rbtree_node n,int value) {
int i;
if (n == NULL) {
cout<<"\n\n \t\t --< Empty tree >--\n\n ";
return 0;
}
if (n->right != NULL) {
search1(n->right,value);
}
if(value==(int)n->key){
cout<<" \n Node is Found \n";
if (n->color == BLACK)
printf("\nColor:: Black= %d\n", (int)n->key);
else
printf("\nColor:: Red= %d\n", (int)n->key);
x=32;
return 0; }
if (n->left != NULL) {
search1(n->left,value);
}
return 0;
}
void search(rbtree t,int v) {
search1(t->root, v);if( x != 32 )cout<<"\n\nNot Found...\n";
x=0; }
void main() {
int i,x,y,c=0;
rbtree tree = rbtree_create();
while(!0){
cout<<"\n============================================\n";
cout<<"\n\nChoose Any Of Following Option:\n\n\n\t\t[ 1 for Insertion]\n\t\t";
cout<<"[ 2 for Deletion ]\n\t\t[ 3 for Display ]\n\t\t[ 4 For Searching]\n\t\t[ 5 For Exit ]\n\n";
cin>>c;
cout<<"\n============================================\n";
switch(c){
case 1:{
cout<<"\n\nHow Many Values You Want To Insert: ";
cin>>y;
for(i=0; i<y; i++) {
cout<<"\n Insert Value For insertion: ";
cin>>x;
int y = rand() % 10000;
printf("\nInserting value is= %d \n\n", x);
rbtree_insert(tree, (void*)x, (void*)y, compare_int);
} break; }
case 2:{
cout<<" \n Enter Value For Deletion: ";
cin>>x;
printf("Deleting key %d\n\n", x);
rbtree_delete(tree, (void*)x, compare_int);
break; }
case 3:{
print_tree(tree);
break;
}
case 4:{
cout<<"\n\nEnter A value for search: ";
cin>>x;
search(tree,x);
break;}
case 5:{
exit(0);
}
default:{break;}
}
}
}
Tuesday, May 5, 2015
Make all values of tree negative -ive
#include<iostream.h>
#include<conio.h>
class Node{
private:
int data;
Node* right;
Node* left;
public:
Node(){
root=NULL;
right=left=NULL;
}Node *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;
}
void makeneg(Node *r){
if (r == NULL) return;
else {
makeneg(r->left);
r->data=r->data*(-1);
makeneg(r->right);
}
}
void inorder(Node *r){
if (r == NULL) return;
else {
inorder(r->left);
cout << r->data <<" ";
inorder(r->right);
}
}
};
void main()
{
int c,A[]={19,54,63,22,75,6,8,1,33,12,44};
Node b;
clrscr();
for(int i=0;i<=10;i++){
b.insert(A[i]); }
cout<<"\nIn-Order display :\n\n";
b.inorder(b.root);
b.makeneg(b.root);
cout<<"\n\nAfter Making all values Nagitive -ive: \n\n ";
b.inorder(b.root);
getch();
}
#include<conio.h>
class Node{
private:
int data;
Node* right;
Node* left;
public:
Node(){
root=NULL;
right=left=NULL;
}Node *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;
}
void makeneg(Node *r){
if (r == NULL) return;
else {
makeneg(r->left);
r->data=r->data*(-1);
makeneg(r->right);
}
}
void inorder(Node *r){
if (r == NULL) return;
else {
inorder(r->left);
cout << r->data <<" ";
inorder(r->right);
}
}
};
void main()
{
int c,A[]={19,54,63,22,75,6,8,1,33,12,44};
Node b;
clrscr();
for(int i=0;i<=10;i++){
b.insert(A[i]); }
cout<<"\nIn-Order display :\n\n";
b.inorder(b.root);
b.makeneg(b.root);
cout<<"\n\nAfter Making all values Nagitive -ive: \n\n ";
b.inorder(b.root);
getch();
}
Making all even values odd in a tree
#include<iostream.h>
#include<conio.h>
class Node{
private:
int data;
Node* right;
Node* left;
public:
Node(){
root=NULL;
right=left=NULL;
}Node *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;
}
void makeeven(Node *r){
if (r == NULL) return;
else {
makeeven(r->left);
if(r->data % 2 == 0){
r->data=r->data+1; }
makeeven(r->right);
}
}
void inorder(Node *r){
if (r == NULL) return;
else {
inorder(r->left);
cout << r->data <<" ";
inorder(r->right);
}
}
};
void main()
{
int c,A[]={19,54,63,22,75,6,8,1,33,12,44};
Node b;
clrscr();
for(int i=0;i<=10;i++){
b.insert(A[i]); }
cout<<"\nIn-Order display :\n\n";
b.inorder(b.root);
b.makeeven(b.root);
cout<<"\n\nAfter Making all even values Odd: \n\n ";
b.inorder(b.root);
getch();
}
Make all Odd values Even in a tree
#include<iostream.h>
#include<conio.h>
class Node{
private:
int data;
Node* right;
Node* left;
public:
Node(){
root=NULL;
right=left=NULL;
}Node *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;
}
void makeeven(Node *r){
if (r == NULL) return;
else {
makeeven(r->left);
if(r->data % 2 != 0){
r->data=r->data+1; }
makeeven(r->right);
}
}
void inorder(Node *r){
if (r == NULL) return;
else {
inorder(r->left);
cout << r->data <<" ";
inorder(r->right);
}
}
};
void main()
{
int c,A[]={19,54,63,22,75,6,8,1,33,12,44};
Node b;
clrscr();
for(int i=0;i<=10;i++){
b.insert(A[i]); }
cout<<"\nIn-Order display :\n";
b.inorder(b.root);
b.makeeven(b.root);
cout<<"\nAfter Making all Odd values even: \n ";
b.inorder(b.root);
getch();
}
#include<conio.h>
class Node{
private:
int data;
Node* right;
Node* left;
public:
Node(){
root=NULL;
right=left=NULL;
}Node *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;
}
void makeeven(Node *r){
if (r == NULL) return;
else {
makeeven(r->left);
if(r->data % 2 != 0){
r->data=r->data+1; }
makeeven(r->right);
}
}
void inorder(Node *r){
if (r == NULL) return;
else {
inorder(r->left);
cout << r->data <<" ";
inorder(r->right);
}
}
};
void main()
{
int c,A[]={19,54,63,22,75,6,8,1,33,12,44};
Node b;
clrscr();
for(int i=0;i<=10;i++){
b.insert(A[i]); }
cout<<"\nIn-Order display :\n";
b.inorder(b.root);
b.makeeven(b.root);
cout<<"\nAfter Making all Odd values even: \n ";
b.inorder(b.root);
getch();
}
Display only Odd values from tree
#include<iostream.h>
#include<conio.h>
class Node{
private:
int data;
Node* right;
Node* left;
public:
Node(){
root=NULL;
right=left=NULL;
}Node *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;
}
void inorder(Node *r){
if (r == NULL) return;
else {
inorder(r->left);
if(r->data % 2 != 0){
cout << r->data <<" "; }
inorder(r->right);
}
}
};
void main()
{
int c,A[]={9,4,3,2,5,6,8,1,33,12,44};
Node b;
clrscr();
for(int i=0;i<=10;i++){
b.insert(A[i]); }
cout<<"\nIn-Order display :\nDisplaing only ODD values:\n\n";
b.inorder(b.root);
getch();
}
Display only even Values from tree
#include<iostream.h>
#include<conio.h>
class Node{
private:
int data;
Node* right;
Node* left;
public:
Node(){
root=NULL;
right=left=NULL;
}Node *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;
}
void inorder(Node *r){
if (r == NULL) return;
else {
inorder(r->left);
if(r->data % 2 == 0){
cout << r->data <<" "; }
inorder(r->right);
}
}
};
void main()
{
int c,A[]={9,4,3,2,5,6,8,1,33,12,44};
Node b;
clrscr();
for(int i=0;i<=10;i++){
b.insert(A[i]); }
cout<<"\nIn-Order display :\nDisplaing only Even values:\n\n";
b.inorder(b.root);
getch();
}
#include<conio.h>
class Node{
private:
int data;
Node* right;
Node* left;
public:
Node(){
root=NULL;
right=left=NULL;
}Node *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;
}
void inorder(Node *r){
if (r == NULL) return;
else {
inorder(r->left);
if(r->data % 2 == 0){
cout << r->data <<" "; }
inorder(r->right);
}
}
};
void main()
{
int c,A[]={9,4,3,2,5,6,8,1,33,12,44};
Node b;
clrscr();
for(int i=0;i<=10;i++){
b.insert(A[i]); }
cout<<"\nIn-Order display :\nDisplaing only Even values:\n\n";
b.inorder(b.root);
getch();
}
Friday, May 1, 2015
Insert 100 in all Leaf nodes and 10 in all non leaf nodes using BST
Insert 100 in all Leaf nodes and 10 in all non leaf nodes using BST in C++
#include<iostream.h>
#include<conio.h>
class Node{
private:
int data;
Node* right,*q,*p;
Node* left;
public:
Node(){
root=NULL;
right=left=NULL;
}Node *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;
}
void inorder(Node *r){
if (r == NULL) return;
else {
inorder(r->left);
if(r->left==NULL && r->right==NULL){
r->data=100;}
else r->data=10;
cout << r->data <<" ";
inorder(r->right);
} }
void _inorder(Node *r){
if (r == NULL) return;
else {
_inorder(r->left);
cout << r->data <<" ";
if(r->left==NULL && r->right==NULL){
r->data=100;}
_inorder(r->right);
} }
};
void main()
{
int c,A[]={9,4,3,2,5,6,8,1,33,12,44};
Node b;
clrscr();
for(int i=0;i<=10;i++){
b.insert(A[i]); }
cout<<"\n\n\nSimple Tree: BST inorder:\n \n";
b._inorder(b.root);
cout<<"\n\n\nAfter Puting 100 in all leaf Node:\n \n";
b._inorder(b.root);
cout<<"\n\n\nAfter Puting 10 in all Non leaf Node:\n\n ";
b.inorder(b.root);
getch();
}
#include<iostream.h>
#include<conio.h>
class Node{
private:
int data;
Node* right,*q,*p;
Node* left;
public:
Node(){
root=NULL;
right=left=NULL;
}Node *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;
}
void inorder(Node *r){
if (r == NULL) return;
else {
inorder(r->left);
if(r->left==NULL && r->right==NULL){
r->data=100;}
else r->data=10;
cout << r->data <<" ";
inorder(r->right);
} }
void _inorder(Node *r){
if (r == NULL) return;
else {
_inorder(r->left);
cout << r->data <<" ";
if(r->left==NULL && r->right==NULL){
r->data=100;}
_inorder(r->right);
} }
};
void main()
{
int c,A[]={9,4,3,2,5,6,8,1,33,12,44};
Node b;
clrscr();
for(int i=0;i<=10;i++){
b.insert(A[i]); }
cout<<"\n\n\nSimple Tree: BST inorder:\n \n";
b._inorder(b.root);
cout<<"\n\n\nAfter Puting 100 in all leaf Node:\n \n";
b._inorder(b.root);
cout<<"\n\n\nAfter Puting 10 in all Non leaf Node:\n\n ";
b.inorder(b.root);
getch();
}
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();
}
#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();
}
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();
}
#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();
}
Subscribe to:
Posts (Atom)
Pages
- Home
- C++ final projects
- Programming Examples
- OOP final projects
- Hacking tricks :-
- C Programming Examples
- OOP Programming Examples
- JAVA
- Simple C program
- Typing Tutor in C++
- Tic-Tac-Toe in C++
- E-Books for C Language
- E-Books for C++ Language
- E-Books for JAVA Language
- E-Books for OOP in C++
- C final Projects
- New Posts
Labels
- .net (7)
- advance (3)
- ajax (2)
- Android (9)
- Article's (20)
- Assembly Language (31)
- C Programming (15)
- C# (15)
- C++ (52)
- COAL (31)
- computer tricks (1)
- css (21)
- Data base (11)
- Data Structure (57)
- E-books (1)
- heap (2)
- html (22)
- Interesting Programs (50)
- Interfaces (4)
- Java (9)
- java-script (10)
- jquery (2)
- liner algabra (9)
- link list (7)
- Matlab (2)
- php (17)
- programming (32)
- Projects (6)
- Queue (7)
- Sorting (8)
- SQL (7)
- Stack (5)
- tree (24)
- vb.net (1)
- web designing (20)
- web development (31)
- xml (2)