javajava

//sample implementation of a BST class BST { Node root; //reference to root of the binary search tree public BST() { root = null; } //iterative insert public void insert(int val) { Node newNode,prev,curr; boolean done = false; prev = null; curr = root; newNode = new Node(val,null,null); if (root == null) { root = newNode; } else { while (curr != null) { prev = curr; if (val < curr.key) curr = curr.left; else curr = curr.right; } if (val < prev.key) prev.left = newNode; else prev.right = newNode; } } //recursive insert public drive method public void insertR(int val) { Node newNode; if (root == null) { root = new Node(val,null,null); } else { insertR(null,root,val); } } //recursive insert private helper method. //this method does the actual insertion into a non-empty tree private void insertR(Node prev, Node curr, int val) { //prev-reference to previous node being considered. //curr-reference to current node being considered. //val - value to insert. Node newNode; if (curr == null) { //base case newNode = new Node(val,null,null); if (val < prev.key ) prev.left = newNode; else prev.right = newNode; } //recursive case else { if (val < curr.key) insertR(curr,curr.left,val); else insertR(curr,curr.right,val); } } //iterative search public boolean search(int key) { Node curr=root; boolean result = false; while (curr !=null) { if (curr.key == key) { result = true; break; } else if (key < curr.key) curr = curr.left; else curr = curr.right; } return result; } //recursive search public boolean searchR(int key) { //driver method return searchR(key,root); } //this method does the actual recursive searching. private boolean searchR(int key, Node curr) { boolean result = false; if (curr !=null) { if (curr.key == key) result = true; else if (key < curr.key) result = searchR(key,curr.left); else result = searchR(key,curr.right); } return result; } //inorder traversal (recursive) private void inorder(Node curr) { if (curr != null) { inorder(curr.left); curr.print(); inorder(curr.right); } } public void inorder() { inorder(root); } class Node { int key; Node left; Node right; public Node(int val, Node l, Node r) { key = val; left = l; right = r; } public void print() { System.out.println(key); } } private Node findNode(int val) { Node curr; curr = root; while (curr != null) { if (curr.key == val) break; } return curr; } private void easyDelete(Node delNode, Node delParent, Node delChild) { //delNode-Node to be deleted //delParent-parent of delNode //delChild-child of delNode if (delParent == null) { //deleting root node root = delChild; } else { //delNode is not root if (delNode == delParent.left) delParent.left = delChild; else delParent.right = delChild; } } private void twoChildrenDelete(Node curr) { Node is, isParent; //inorder successor and inorder successor's parent is = curr.right; isParent = curr; while (is.left != null) { //find inorder successor to curr. isParent = is; is = is.left; } curr.key = is.key; //put inorder sucessor's value into node curr. easyDelete(is,isParent,is.right); //delete inorder successor node, which has no left child. } public void delete(int val) { Node curr = root; Node prev = null; while (curr != null && curr.key != val) { prev = curr; if (val < curr.key) curr = curr.left; else curr = curr.right; } if (curr != null) { //key found if (curr.left == null) easyDelete(curr,prev, curr.right); else if (curr.right == null) easyDelete(curr,prev,curr.left); else twoChildrenDelete(curr); } } }