Ask Question

Name:
Title:
Your Question:

Answer Question

Name:
Your Answer:
User Submitted Source Code!


Description:
  BinaryTree
Language: JAVA
Code:
import java.util.*;

class Node {
    int value;
    Node left;
    Node right;
 
    Node(int value) {
        this.value = value;
        right = null;
        left = null;
    }
}

public class BinaryTree {
 
    static Node root;
    
    //insert
    private static Node addNewNode(Node current, int value) {
        if (current == null) {
            return new Node(value);
        }
 
        if (value < current.value) {
            current.left = addNewNode(current.left, value);
        }
            else if (value > current.value) {
                current.right = addNewNode(current.right, value);
            }
        // value already exists
        return current;
    }
    //call insert
    public static void add(int value) {
    root = addNewNode(root, value);
    }
    //call insert example
    public static void add_ex(){
        add(1);
        add(2);
        add(3);
        add(5);
        add(4);
        add(6);
    }
    
    //find
    
    //find the exact value (search)
    private boolean containsNode(Node current, int value) {
        if (current == null) {
            return false;
        } 
        if (value == current.value) {
            return true;
        } 
        return value < current.value ? containsNode(current.left, value) : containsNode(current.right, value);
    }
    
    //call find the exact value (search)
    public boolean contains(int value) {
        return containsNode(root, value);
    }
    
    //find min
    private static int findMinValue(Node current) {
        while (current.left != null)  
        current = current.left; 
      
        return (current.value);
    }
    //find max
    private static int findMaxValue(Node current) {
        while (current.right != null)  
        current = current.right; 
      
        return (current.value);
    }
    
    //delete
    private Node deleteNode(Node current, int value) {
        if (current == null) {
            return null;
        }
        
        //search value node
        if (value < current.value) {
            current.left = deleteNode(current.left, value);
            return current;
        }
        if (value > current.value) {
            current.right = deleteNode(current.right, value);
            return current;
        }
        //delete node
            //no children
        if (current.left == null && current.right == null) {
            return null;
        }

        //only 1 child
        if (current.right == null) {
            return current.left;
        }

        if (current.left == null) {
            return current.right;
        }

        //2 children
        int minValue = findMinValue(current.right);
        current.value = minValue;
        current.right = deleteNode(current.right, minValue);
        return current;
    }
    //call delete func
    public void delete(int value) {
        root = deleteNode(root, value);
    }
    //tranverse and print
    public static void printAll(int printMode) {
        System.out.println("Binary tree traversal :");
            if(printMode==1){//preorder
                Stack<Node> stack = new Stack<Node>();
                Node current = root;
                stack.push(root);
                while(! stack.isEmpty()) {
                    current = stack.pop();
                    transverse(current.value);
                    
                    if(current.right != null)
                        stack.push(current.right);
                
                    if(current.left != null)
                        stack.push(current.left);
                }
            }
            if(printMode==2){//inorder
                Stack<Node> stack = new Stack<Node>();
                Node current = root;
                stack.push(root);
                while(! stack.isEmpty()) {
                    while(current.left != null) {
                        current = current.left;                
                        stack.push(current);                
                    }
                    current = stack.pop();
                    transverse(current.value);
                    if(current.right != null) {
                        current = current.right;                
                        stack.push(current);
                    }
                }
            }   
            if(printMode==3){//postorder
                Stack<Node> stack = new Stack<Node>();
                Node prev = root;
                Node current = root;
                stack.push(root);
                while (!stack.isEmpty()) {
                    current = stack.peek();
                    boolean hasChild = (current.left != null || current.right != null);
                    boolean isPrevLastChild = (prev == current.right || (prev == current.left && current.right == null));
    
                    if (!hasChild || isPrevLastChild) {
                        current = stack.pop();
                        transverse(current.value);
                    prev = current;
                    }
                        else {
                            if (current.right != null) {
                                stack.push(current.right);
                            }
                            if (current.left != null) {
                                stack.push(current.left);
                            }
                        }
                }
            }
        System.out.println();
    }
    //call print
    private static void transverse(int value) {
        System.out.print(value + " ");
    }
    
    //main program
    public static void main(String[] args) {
        Scanner scanner  = new Scanner(System.in);
        boolean exit = false;
        //create tree
        BinaryTree bt = new BinaryTree();
        //create menu
        System.out.println("===========================================");
        System.out.println("BINARY SEARCH TREE KELOMPOK 1 STRUKTUR DATA");
        System.out.println("===========================================");
        System.out.println("===========================================");
        System.out.println("1. Add a node\n2. Delete a node\n3. Show min node\n4. Show max node\n5. Find a node\n6. Print all nodes\n0. Exit\n99. Add example tree");
        while(exit==false){
            int menu = scanner.nextInt();
            if(menu==99)
            add_ex();
            
            if(menu==0){
                exit = true;
            }
            //add
            else if(menu==1){
                System.out.println("Input value to be added :");
                int val = scanner.nextInt();
                bt.add(val);
            }
            //delete
            else if(menu==2){
                System.out.println("Input value to be deleted :");
                int val = scanner.nextInt();
                if(bt.contains(val)){
                    bt.delete(val);
                }
                    else{
                        System.out.println("No node with that value found!");
                    }
            }
            //min
            else if(menu==3){
                if (root != null) {
                    System.out.print("Minimum Value is ");
                    System.out.println(findMinValue(root));
                }
                else {
                    System.out.println("Add tree node first!");
                }
            }
            //max
            else if(menu==4){
                if (root != null) {
                    System.out.print("Maximum Value is ");
                    System.out.println(findMaxValue(root));
                }
                else {
                    System.out.println("Add tree node first!");
                }
            }
            //find
            else if(menu==5){
                System.out.println("Input value to be found :");
                int val = scanner.nextInt();
                if(bt.contains(val)){
                    System.out.println("Node with that value found!");
                }
                else {
                        System.out.println("No node with that value found!");
                }
            }
            //print node
            else if(menu==6){
                if(root!=null){
                    System.out.println("Choose print mode :\n1. PreOrder\n2. InOrder\n3. PostOrder");
                    printAll(scanner.nextInt());
                }
                    else
                        System.out.println("No tree found!");
            }
            System.out.println("Operation Completed!");
        }
        System.exit(0);
    }
}
Comments: