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();

}


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();
}

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();
}

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();

}


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();

}


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();

}

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();

}



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();
}

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();

}