Hi I'm really new to Java, and I'm trying to make a switch right now. I have the following code in C, and I was just wondering what differences I would have to change to make the code work in Java. The code is a Dictionary library ADT and it's based on a Binary Search Tree. Thanks a lot! Code: /* * Dictionary.c * Binary Search Tree implementation of the Dictionary ADT */ #include<stdio.h> #include<stdlib.h> #include<string.h> #include<assert.h> #include"Dictionary.h" /********************************* Private types and functions ***********************/ /* * Node */ typedef struct Node{ int key; int value; struct Node* left; struct Node* right; } Node; /* * NodeRef */ typedef Node* NodeRef; /* * Dictionary */ typedef struct Dictionary{ NodeRef root; int numPairs; } Dictionary; /* * newNode * Constructor for the private Node type */ NodeRef newNode(int k, int v) { NodeRef N = malloc(sizeof(Node)); assert(N!=NULL); N->key = k; N->value = v; N->left = N->right = NULL; return(N); } /* * freeNode * Destructor for the private Node type */ void freeNode(NodeRef* pN){ if( pN!=NULL && *pN!=NULL ){ free(*pN); *pN = NULL; } } /* * findKey * returns a reference to the Node containing key k in the subtree rooted at R, * or NULL if no such Node exists */ NodeRef findKey(NodeRef R, int k){ if(R==NULL || k==R->key) return R; if( k<R->key ) return findKey(R->left, k); else return findKey(R->right, k); } /* * findParent * returns a reference to the Node which is the parent of N in the subtree rooted * at R, or returns NULL if N is equal to R. */ NodeRef findParent(NodeRef N, NodeRef R){ NodeRef P=NULL; if( N!=R ){ P = R; for( ; P->left!=N && P->right!=N; P=(N->key<P->key?P->left:P->right) ); } return P; } /* * findLeftmost * returns the leftmost Node in the subtree rooted at R, or NULL if R is NULL. */ NodeRef findLeftmost(NodeRef R){ NodeRef L = R; if( L!=NULL) for( ; L->left!=NULL; L=L->left) ; return L; } /* * printInOrder * prints the (key, value) pairs belonging to the subtree rooted at R in order * of increasing keys to file pointed to by out. */ void printInOrder(NodeRef R, FILE* out){ if( R!=NULL ){ printInOrder(R->left, out); fprintf(out, "%d %d\n", R->key, R->value); printInOrder(R->right, out); } } /* * deleteAll * deletes all Nodes in the subtree rooted at N. */ void deleteAll(NodeRef N){ if( N!=NULL ){ deleteAll(N->left); deleteAll(N->right); freeNode(&N); } } /********************************* Public functions ******************************/ /* * newDictionary * Allocates and initializes a struct representing an empty Dictionary. Returns a * pointer to new memory if successful, terminates if not successful. */ DictionaryRef newDictionary(void){ DictionaryRef D = malloc(sizeof(Dictionary)); assert(D!=NULL); D->root = NULL; D->numPairs = 0; return D; } /* * freeDictionary * Frees all heap memory associated with *pD and sets the reference *pD to NULL */ void freeDictionary(DictionaryRef* pD){ if( pD!=NULL && *pD!=NULL ){ makeEmpty(*pD); free(*pD); *pD = NULL; } } /* * isEmpty * pre: none * post: returns 1 (true) if D is empty, 0 (false) otherwise */ int isEmpty(DictionaryRef D){ if( D==NULL ){ fprintf(stderr, "Dictionary Error: calling isEmpty() on NULL DictionaryRef\n"); exit(EXIT_FAILURE); } return(D->numPairs==0); } /* * size * pre: none * post: returns the number of entries in D */ int size(DictionaryRef D){ if( D==NULL ){ fprintf(stderr, "Dictionary Error: calling size() on NULL DictionaryRef\n"); exit(EXIT_FAILURE); } return(D->numPairs); } /* * lookup * pre: none * post: returns value associated key k, or UNDEF if no such key exists */ int lookup(DictionaryRef D, int k){ NodeRef N; if( D==NULL ){ fprintf(stderr, "Dictionary Error: calling lookup() on NULL DictionaryRef\n"); exit(EXIT_FAILURE); } N = findKey(D->root, k); if( N!=NULL ) return N->value; else return UNDEF; } /* * insert * inserts new (key,value) pair into D * pre: key k currently does not exist in D, i.e. lookup(D, k)==UNDEF * post: !isEmpty(D), size(D) is increased by one */ void insert(DictionaryRef D, int k, int v){ NodeRef N, A, B; if( D==NULL ){ fprintf(stderr, "Dictionary Error: calling insert() on NULL DictionaryRef\n"); exit(EXIT_FAILURE); } if( findKey(D->root, k)!=NULL ){ fprintf(stderr, "Dictionary Error: cannot insert() duplicate keys\n"); exit(EXIT_FAILURE); } N = newNode(k, v); B = NULL; A = D->root; while( A!=NULL ){ B = A; if( k<A->key ) A = A->left; else A = A->right; } if( B==NULL ) D->root = N; else if( k<B->key ) B->left = N; else B->right = N; D->numPairs++; } /* * delete * deletes pair with the key k * pre: key k currently exists in D, i.e. lookup(D, k)!=UNDEF * post: size(D) is decreased by one */ void delete(DictionaryRef D, int k){ NodeRef N, P, S; if( D==NULL ){ fprintf(stderr, "Dictionary Error: calling delete() on NULL DictionaryRef\n"); exit(EXIT_FAILURE); } N = findKey(D->root, k); if( N==NULL ){ fprintf(stderr, "Dictionary Error: cannot delete() non-existent key\n"); exit(EXIT_FAILURE); } if( N->left==NULL && N->right==NULL ){ if( N==D->root ){ D->root = NULL; freeNode(&N); }else{ P = findParent(N, D->root); if( P->right==N ) P->right = NULL; else P->left = NULL; freeNode(&N); } }else if( N->right==NULL ){ if( N==D->root ){ D->root = N->left; freeNode(&N); }else{ P = findParent(N, D->root); if( P->right==N ) P->right = N->left; else P->left = N->left; freeNode(&N); } }else if( N->left==NULL ){ if( N==D->root ){ D->root = N->right; freeNode(&N); }else{ P = findParent(N, D->root); if( P->right==N ) P->right = N->right; else P->left = N->right; freeNode(&N); } }else{ S = findLeftmost(N->right); N->key = S->key; N->value = S->value; P = findParent(S, N); if( P->right==S ) P->right = S->right; else P->left = S->right; freeNode(&S); } D->numPairs--; } /* * makeEmpty * pre: none * post: isEmpty(D) */ void makeEmpty(DictionaryRef D){ deleteAll(D->root); D->root = NULL; D->numPairs = 0; } /* * printDictionary * pre: none * post: prints a text representation of D to file pointed to by out. */ void printDictionary(DictionaryRef D, FILE* out){ if( D==NULL ){ fprintf(stderr, "Dictionary Error: calling printDictionary() on NULL DictionaryRef\n"); exit(EXIT_FAILURE); } printInOrder(D->root, out); }
This is what I have so far: (any help is appreciated ) Code: // Dictionary.java // Binary Search Tree implementation of the Dictionary ADT public class Dictionary implements DictionaryInterface { // private inner Node class private class Node { int key; int value; Node left; Node right; Node(int k, int v){ key = k; value = v; left = null; right = null; } } // Fields for the IntegerList class private Node root; // reference to root Node in List private int numItems; // number of items in this IntegerList // Dictionary() // constructor for the Dictionary class public Dictionary(){ root = null; numItems = 0; } // findKey // returns a reference to the Node containing key k in the subtree rooted at R, // or NULL if no such Node exists private Node findKey(int index){ Node N = root; if(index < N.key ) return findKey(index-1); else return findKey(index+1); } // isEmpty() // pre: none // post: returns true if this Dictionary is empty, false otherwise public boolean isEmpty(){ return (numItems == 0); } // size() // pre: none // post: returns the number of entries in this Dictionary public int size(){ return numItems; } // lookup() // pre: none // post: returns value associated key k, or UNDEF if no such key exists public int lookup(int k){ return 0; } // insert() // inserts new (key,value) pair into this Dictionary // pre: key k does not exist in this Dictionary, i.e. lookup(k)==UNDEF // post: !isEmpty(), size() is increased by one public void insert(int k, int v) throws KeyCollisionException{ } // delete // deletes the pair with the key k // pre: key k currently exists in this Dictionary, i.e. lookup(k)!=UNDEF // post: size() is decreased by one public void delete(int k) throws KeyNotFoundException{ } // makeEmpty() // pre: none // post: isEmpty() public void makeEmpty(){ root = 0; numPairs = 0; } // toString() // overrides Object's toString() method // pre: none // post: returns a String representation of this Dictionary ordered // by ascending keys public String toString(){ String s = ""; for(Node N=root; N!=null; N=N.left){ s += N.key + ", " + N.value + " "; } return s; } }