Friday, June 6, 2014

Duplicate Finder [Tree Implementation][Dynamically allocated nodes] in C++ and Java

The program finds duplicate numbers as the user enters a list of numbers:

                                                                   C++

#include <iostream>

using namespace std;
 
struct nodetype{
 int info;
 struct nodetype *left;
 struct nodetype *right; 
};

typedef struct nodetype *NODEPTR;

NODEPTR getnode(){
 return new nodetype;
}

NODEPTR maketree(int x){
 NODEPTR p = getnode();
 p->info = x;
 p->left = NULL;
 p->right = NULL;
 return p;
}

void setleft(NODEPTR p, int x){
 if (p == NULL)
  printf("void insertion\n");
 else if (p->left != NULL)
  printf("invalid insertion\n");
 else p->left = maketree(x);
}

void setright(NODEPTR p, int x){
 if (p == NULL)
  printf("void insertion\n");
 else if (p->right != NULL)
  printf("invalid insertion\n");
 else p->right = maketree(x);
}


int main(){
 NODEPTR ptree;
 NODEPTR p, q;
 int number;

 cout << "Enter a number from the list: ";
 cin >> number;
 ptree = maketree(number);
 while ((cout<<"\nEnter number: ")&&cin >> number){
  p = q = ptree;
  while (number != p->info && q != NULL){
   p = q;
   if (number < p->info)
    q = p->left;
   else
    q = p->right;
  }
  if (number == p->info)
   cout << endl << "*** " << number << " is a duplicate *** \n";
  else if (number < p->info)
   setleft(p, number);
  else
   setright(p, number);
 }
}



                               [JAVA]

import java.util.Scanner;


class nodetype{
    public int info;
    public nodetype left;
    public nodetype right;
}


public class Tree {
    static nodetype getnode(){
        return new nodetype();
    }
    
    static nodetype maketree(int x){
        nodetype p = getnode();
        p.info = x;
        p.left = null;
        p.right = null;
        return p;
    }
    
    static void setleft(nodetype p, int x){
        if(p==null)
            System.out.println("void insertion\n");
        else if(p.left != null)
            System.out.println("invalid insertion\n");
        else p.left = maketree(x);
    }
    
    static void setright(nodetype p, int x){
        if(p==null)
            System.out.println("void insertion\n");
        else if(p.right != null)
            System.out.println("invalid insertion\n");
        else p.right = maketree(x);
    }
    
    public static void main(String[] args){
        nodetype ptree;
        nodetype p = null, q;
        int number;
        
        System.out.println("Duplicate finder\n\n");
        System.out.println("Enter numbers :");
        Scanner scan = new Scanner(System.in);
        number = scan.nextInt();
        
        ptree = maketree(number);
        
        while((number=scan.nextInt())!=-999){
            p = q = ptree;
            while(number != p.info && q!=null){
                p=q;
            if(number<p.info)
                q = p.left;
            else
                q = p.right;
        }
        
        if(number == p.info)
            System.out.println("*** "+number+" is a duplicate ***\n");
        else if (number<p.info)
            setleft(p, number);
        else
            setright(p, number);
        }
    }
}

No comments:

Post a Comment