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