Previous post on BST did not use Father field. This program uses Father field in Node.
Source:
import java.util.Scanner; public class BSTFather { Node root; class Node { Node father, left, right; int key; public Node(int key, Node left, Node right, Node father) { this.key = key; this.left = left; this.right = right; this.father = father; } public String toString() { return Integer.toString(key); } } public void insert(Node toInsert, Node node) { if (root == null) { root = toInsert; return; } if (toInsert.key < node.key) { if (node.left != null) { insert(toInsert, node.left); } else { toInsert.father = node; node.left = toInsert; } } else if (toInsert.key >= node.key) { if (node.right != null) { insert(toInsert, node.right); } else { toInsert.father = node; node.right = toInsert; } } } public Node findNode(Node findNode, Node node) { if (root == null) { return null; } if (findNode.key < node.key) { if (node.left != null) { return findNode(findNode, node.left); } } else if (findNode.key > node.key) { if (node.right != null) { return findNode(findNode, node.right); } } else if (findNode.key == node.key) { return node; } return null; } public boolean deleteNode(Node deleteNode, Node node) { if (root == null) return false; else if (root.key == deleteNode.key) { if(root.left == null && root.right == null) root = null; else if (root.left == null) { root = root.right; root.father = null; } else if (root.right == null) { root = root.left; root.father = null; } else { Node min = root.right; //min element has no left or right child. if(min.left==null && min.right==null){ root.key = min.key; root.right = null; return true; } while(min.left!=null){ //Min element has left child. min = min.left; } root.key = min.key; if(min.right!=null) min.right.father = min.father; //Min element has no left child but has right child. if(min.father!=root) min.father.left = min.right; else{ min.father.right = min.right;} } return true; } else { Node locatedNode = findNode(deleteNode, root); if(locatedNode!=null) deleteHelper(locatedNode); else return false; } return true; } private void deleteHelper(Node locatedNode) { boolean left = (locatedNode.father.left == locatedNode); if(locatedNode.right == null && locatedNode.left == null){ if(left) locatedNode.father.left = null; else locatedNode.father.right = null; } else if(locatedNode.left!=null && locatedNode.right == null){ locatedNode.left.father = locatedNode.father; if(left) locatedNode.father.left = locatedNode.left; else locatedNode.father.right = locatedNode.left; }else if(locatedNode.left==null && locatedNode.right!=null){ locatedNode.right.father = locatedNode.father; if(left) locatedNode.father.left = locatedNode.right; else locatedNode.father.right = locatedNode.right; }else if(locatedNode.left!=null && locatedNode.right!=null){ Node min = locatedNode.right; //min element has no left or right child. if(min.left==null && min.right==null){ locatedNode.key = min.key; locatedNode.right = null; return; } while(min.left!=null){ //Min element has left child. min = min.left; } locatedNode.key = min.key; if(min.right!=null) min.right.father = min.father; //Min element has no left child but has right child. if(min.father!=locatedNode) min.father.left = min.right; else{ min.father.right = min.right;} } } public void deleteTree(){ root = null; } public void printTree(Node node) { if (node == null) { return; } printTree(node.left); System.out.print(node.key+" "); printTree(node.right); } public void consoleUI(){ Scanner scan = new Scanner(System.in); while (true) { System.out.println("\n1.- Add items\n" + "2.- Delete items\n" + "3.- Check items\n" + "4.- Print tree\n" + "5.- Delete tree\n"); int choice = scan.nextInt(); int item; Node node; switch (choice) { case 1: item = scan.nextInt(); while (item != -999) { node = new Node(item, null, null, null); insert(node, root); item = scan.nextInt(); } printTree(root); break; case 2: item = scan.nextInt(); while (item != -999) { node = new Node(item, null, null, null); System.out.print("\nDeleting item "+item); if(deleteNode(node, root)){ System.out.print(": deleted!"); }else System.out.print(": does not exist!"); item = scan.nextInt(); } System.out.println(); printTree(root); break; case 3: item = scan.nextInt(); while (item != -999) { node = new Node(item, null, null, null); System.out.println((findNode(node, root)!=null)?"found":"not found"); item = scan.nextInt(); } break; case 4: printTree(root); break; case 5: deleteTree(); System.out.println("Tree deleted!"); break; } } } public static void main(String[] args) { BSTFather bst = new BSTFather(); bst.consoleUI(); } }
Output:
1.- Add items
2.- Delete items
3.- Check items
4.- Print tree
5.- Delete tree
1
1 2 77 5 4 99 7 4 6 -999
1 2 4 4 5 6 7 77 99
1.- Add items
2.- Delete items
3.- Check items
4.- Print tree
5.- Delete tree
2
4 5 7 4 6 77 99 1 2 -999
Deleting item 4: deleted!
Deleting item 5: deleted!
Deleting item 7: deleted!
Deleting item 4: deleted!
Deleting item 6: deleted!
Deleting item 77: deleted!
Deleting item 99: deleted!
Deleting item 1: deleted!
Deleting item 2: deleted!
As expected!
No comments:
Post a Comment