Binary Tree Algorithm - Java

Java Programming

Node class

public class Node {

    public int id;
    public String data;
    public Node leftChild;
    public Node rightChild;


    Node(int id) {
        this.id = id;
        leftChild = null;
        rightChild = null;
    }

    public void displayNode() {
        System.out.print("( " + id + ", " + data + " )");
    }
}

Tree class for implementing TreeAPP

import java.util.*;

public class Tree {

    public Node root;

    public Tree() {
        root = null;
    }
    //find method with int key to find//
    public Node find(int key) {
        Node current = root;
        while (current.id != key) {
            if (key < current.id) {
                current = current.leftChild;
            } else {
                current = current.rightChild;
            }
            if (current == null) {
                return null;
            }
        }
        return current;
    }
    
    //insert method for double tree value id//
    public void insert(int id, String data) {
        Node newNode = new Node(100);
        newNode.id = id;
        newNode.data = data;
        if (root == null) {
            root = newNode;
        } else {
            Node current = root;
            Node parent;
            while (true) {
                parent = current;
                if (id < current.id) {
                    current = current.leftChild;
                    if (current == null) {
                        parent.leftChild = newNode;
                        return;
                    }
                } 
                //to make distinct id//
                else if (id == current.id) {
                    System.out.println("Make sure the ID number is different!!");
                    parent = null;
                } else {
                    current = current.rightChild;
                    if (current == null) {
                        parent.rightChild = newNode;
                        return;
                    }
                }
            }
        }
    }
    
    //delete method with key for finding key//
    public boolean delete(int key) {
        Node current = root;
        Node parent = root;
        boolean isLeftChild = true;
        while (current.id != key) {
            parent = current;
            if (key < current.id) {
                isLeftChild = true;
                current = current.leftChild;
            } else {
                isLeftChild = false;
                current = current.rightChild;
            }
            if (current == null) {
                return false;
            }
        }
        if (current.leftChild == null && current.rightChild == null) {
            if (current == root) {
                root = null;
            } else if (isLeftChild) {
                parent.leftChild = current.leftChild;
            } else {
                parent.rightChild = current.leftChild;
            }
        } else if (current.rightChild == null) {
            if (current == root) {
                root = current.leftChild;
            } else if (isLeftChild) {
                parent.leftChild = current.leftChild;
            } else {
                parent.rightChild = current.leftChild;
            }
        } else if (current.leftChild == null) {
            if (current == root) {
                root = null;
            } else if (isLeftChild) {
                parent.leftChild = current.leftChild;
            } else {
                parent.rightChild = current.rightChild;
            }
        } else {
            Node successor = getSuccessor(current);
            if (current == root) {
                root = successor;
            } else if (isLeftChild) {
                parent.leftChild = successor;
            } else {
                parent.rightChild = successor;
            }
        }
        return true;
    }

    private Node getSuccessor(Node delNode) {
        Node successorParent = delNode;
        Node successor = delNode;
        Node current = delNode.rightChild;
        while (current != null) {
            successorParent = successor;
            successor = current;
            current = current.leftChild;
        }
        if (successor != delNode.rightChild) {
            successorParent.leftChild = successor.rightChild;
            successor.rightChild = delNode.rightChild;
        }
        return successor;
    }
    
    //tranverse method for preorder, postorder and traversal case//
    public void traverse(int traverseType) {
        switch (traverseType) {
            case 1:
                System.out.print("Preorder Traversal: ");
                preOrder(root);
                break;
            case 2:
                System.out.print("Inorder Traversal: ");
                inOrder(root);
                break;
            case 3:
                System.out.print("Postorder Traversal: ");
                postOrder(root);
                break;
        }
        System.out.println("");
    }
    
    //method for preorder case in traversal method//
    private void preOrder(Node localRoot) {
        if (localRoot != null) {
            System.out.print(localRoot.id + " ");
            preOrder(localRoot.leftChild);
            preOrder(localRoot.rightChild);
        }
    }
    
    //method for inorder case in traversal method//
    private void inOrder(Node localRoot) {
        if (localRoot != null) {
            inOrder(localRoot.leftChild);
            System.out.print(localRoot.id + " ");
            inOrder(localRoot.rightChild);
        }
    }

    //method for postorder case in traversal method//
    private void postOrder(Node localRoot) {
        if (localRoot != null) {
            postOrder(localRoot.leftChild);
            postOrder(localRoot.rightChild);
            System.out.print(localRoot.id + " ");
        }
    }

    //displpay method//
    public void displayTree() {
        Stack globalStack = new Stack();
        globalStack.push(root);
        int nBlanks = 32;
        boolean isRowEmpty = false;
        System.out.println("...................................................");
        while (isRowEmpty == false) {
            Stack localStack = new Stack();
            isRowEmpty = true;
            for (int j = 0; j < nBlanks; j++) {
                System.out.print(' ');
            }
            while (globalStack.isEmpty() == false) {
                Node temp = (Node) globalStack.pop();
                if (temp != null) {
                    System.out.print(temp.data);
                    localStack.push(temp.leftChild);
                    localStack.push(temp.rightChild);
                    if (temp.leftChild != null || temp.rightChild != null) {
                        isRowEmpty = false;
                    }
                } else {
                    System.out.print("xxxxx");
                    localStack.push(null);
                    localStack.push(null);
                }
                for (int j = 0; j < nBlanks * 2 - 2; j++) {
                    System.out.print(' ');
                }
            }
            System.out.println();
            nBlanks /= 2;
            while (localStack.isEmpty() == false) {
                globalStack.push(localStack.pop());
            }
        }
        System.out.println("...................................................");
    }
}

TreeAPP class for programming Binary Tree algorithm

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class TreeApp {

    public static void main(String args[]) throws IOException {
        int value;
        String data;
        //the new binary tree//
        Tree theTree = new Tree();
        theTree.insert(50, "Ahmad");
        theTree.insert(25, "Rosa");
        theTree.insert(75, "Raisa");
        theTree.insert(12, "Naya");
        theTree.insert(37, "Gagas");
        theTree.insert(43, "Ainun");
        theTree.insert(30, "Beri");
        theTree.insert(33, "Vivid");
        theTree.insert(87, "Orin");
        theTree.insert(93, "Wiwid");
        theTree.insert(97, "Sasa");
        while (true) {
            System.out.print("Enter the first letter of show, insert, "
                    + "find, delete, or traverse: ");
            int choice = getChar();
            switch (choice) {
                case 's':
                    theTree.displayTree();
                    break;
                case 'i':
                    putText("Enter value to insert:");
                    value = getInt();
                    data = getString();
                    theTree.insert(value, data);
                    break;
                case 'f':
                    putText("Enter value to find:");
                    value = getInt();
                    Node found = theTree.find(value);
                    if (found != null) {
                        putText("Found:");
                        found.displayNode();
                        putText("\n");
                    } else {
                        putText("Could not find" + value + '\n');
                    }
                    break;
                case 't':
                    putText("Enter type 1:preOrder, 2:inOrder or 3:postOrder :-");
                    value = getInt();
                    theTree.traverse(value);
                    break;
                case 'e':
                    System.exit(0);
                default:
                    putText("Invalid entry\n");
            }
        }
    }
    
    //method for put the print out//
    public static void putText(String s) {
        System.out.print(s);
        System.out.flush();
    }

    public static String getString() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        return s;
    }

    //method to get char from case//
    public static char getChar() throws IOException {
        String s = getString();
        return s.charAt(0);
    }
    
    //method to get integer from case//
    public static int getInt() throws IOException {
        String s = getString();
        return Integer.parseInt(s);
    }
}

Binary Tree Algorithm - Java

By Solve Program

Binary Tree Algorithm - Java

Programming Language

Data Structure

Binary Tree Algorithm - Java

By Solve Program

Binary Tree Algorithm - Java

Related Solving and Tutorial:

Programming Language

Data Structure