PENUGASAN 8 -- BST

 Implementasi Program BST (Binary Search Tree)

A Binary search tree (referred to as BST hereafter) is a type of binary tree. It can also be defined as a node-based binary tree. BST is also referred to as ‘Ordered Binary Tree’. In BST, all the nodes in the left subtree have values that are less than the value of the root node.

Similarly, all the nodes of the right subtree of the BST have values that are greater than the value of the root node. This ordering of nodes has to be true for respective subtrees as well.

Method in BST

1. Insert  : Add an element to the BST by not violating the BST properties.

2. Delete : Remove a given node from the BST. The node can be the root node, non leaf, o leaf node

3. Search : Search the location of the given element in the BST. This operation checks if the tree contains the specified key.

Source

class BST_Class {
    class Node {
        int key;
        Node left, right;
        
        public Node(int data){
            key=data;
            left = right = null;
        }
    }
    //BST ROOT NODE
    Node root;
    
    BST_Class(){
        root = null;
    }
    
    //delete node from bst
    void deleteKey (int key){
        root = delete_Recursive(root, key);
    }
    
    //recursive delete function
Node delete_Recursive(Node root, int key){
//tree is empty
if(root == null)
    return root;

//tranverse the tree
if(key < root.key)
    root.left = delete_Recursive(root.left, key);
else if(key > root.key)
    root.right = delete_Recursive(root.right, key);
else {
    //one child
    if (root.left == null)
        return root.right;
    else if (root.right == null)
        return root.left;
        
    //two children
    root.key = minValue(root.right);
    
    root.right = delete_Recursive(root.right,root.key);
}
return root;
}

int minValue(Node root){
    int minval = root.key;
    while (root.left != null){
        minval = root.left.key;
        root = root.left;
    }
    return minval;
}

// insert a node in BST 
    void insert(int key)  { 
        root = insert_Recursive(root, key); 
    } 
   
    //recursive insert function
    Node insert_Recursive(Node root, int key) { 
          //tree is empty
        if (root == null) { 
            root = new Node(key); 
            return root; 
        } 
        //traverse the tree
        if (key < root.key)     //insert in the left subtree
            root.left = insert_Recursive(root.left, key); 
        else if (key > root.key)    //insert in the right subtree
            root.right = insert_Recursive(root.right, key); 
          // return pointer
        return root; 
    } 
 
// method for inorder traversal of BST 
    void inorder() { 
        inorder_Recursive(root); 
    } 
   
    // recursively traverse the BST  
    void inorder_Recursive(Node root) { 
        if (root != null) { 
            inorder_Recursive(root.left); 
            System.out.print(root.key + " "); 
            inorder_Recursive(root.right); 
        } 
    } 
     
    boolean search(int key)  { 
        root = search_Recursive(root, key); 
        if (root!= null)
            return true;
        else
            return false;
    } 
   
    //recursive insert function
    Node search_Recursive(Node root, int key)  { 
        // Base Cases: root is null or key is present at root 
        if (root==null || root.key==key) 
            return root; 
        // val is greater than root's key 
        if (root.key > key) 
            return search_Recursive(root.left, key); 
        // val is less than root's key 
        return search_Recursive(root.right, key); 
    } 
}
public class Main{
    public static void main(String[] args)  { 
       //create a BST object
        BST_Class bst = new BST_Class(); 
        
        //insert data into BST
        bst.insert(45); 
        bst.insert(10); 
        bst.insert(7); 
        bst.insert(12); 
        bst.insert(90); 
        bst.insert(50); 
        //print the BST
        System.out.println("The BST Created with input data(Left-root-right):"); 
        bst.inorder(); 
        
        //delete leaf node  
        System.out.println("\nThe BST after Delete 12(leaf node):"); 
        bst.deleteKey(12); 
        bst.inorder(); 
        //delete the node with one child
        System.out.println("\nThe BST after Delete 90 (node with 1 child):"); 
        bst.deleteKey(90); 
        bst.inorder(); 
                 
        //delete node with two children  
        System.out.println("\nThe BST after Delete 45 (Node with two children):"); 
        bst.deleteKey(45); 
        bst.inorder(); 
        //search a key in the BST
        boolean ret_val = bst.search (50);
        System.out.println("\nKey 50 found in BST:" + ret_val );
        ret_val = bst.search (12);
        System.out.println("\nKey 12 found in BST:" + ret_val );
     } 
}

Output

Implementasi Program BST (Binary Search Tree) Transversal

A tree is a hierarchical structure, thus we cannot traverse it linearly like other data structures such as arrays. Any type of tree needs to be traversed in a special way so that all its subtrees and nodes are visited at least once.

Depending on the order in which the root node, left subtree and right subtree are traversed in a tree, there are certain traversals as shown below:

1. Inorder Traversal

2. Preorder Traversal

3. PostOrder Traversal

Source

//define node of the BST
class Node { 
    int key; 
    Node left, right; 
   
    public Node(int data){ 
        key = data; 
        left = right = null; 
    } 
} 
//BST class
class BST_class { 
    // BST root node 
    Node root; 
   
    BST_class(){ 
        root = null; 
    } 
   
    //PostOrder Traversal - Left:Right:rootNode (LRn)
    void postOrder(Node node)  { 
        if (node == null) 
            return; 
   
        // first traverse left subtree recursively 
        postOrder(node.left); 
   
        // then traverse right subtree recursively 
        postOrder(node.right); 
   
        // now process root node 
        System.out.print(node.key + " "); 
    } 
  // InOrder Traversal - Left:rootNode:Right (LnR) 
    void inOrder(Node node)  { 
        if (node == null) 
            return; 
        //first traverse left subtree recursively
        inOrder(node.left); 
   
        //then go for root node
        System.out.print(node.key + " "); 
   
        //next traverse right subtree recursively
        inOrder(node.right); 
    } 
   
//PreOrder Traversal - rootNode:Left:Right (nLR)
    void preOrder(Node node)  { 
        if (node == null) 
            return; 
   
        //first print root node first
        System.out.print(node.key + " "); 
        // then traverse left subtree recursively
        preOrder(node.left); 
        // next traverse right subtree recursively
        preOrder(node.right); 
    } 
   // Wrappers for recursive functions 
    void postOrder_traversal()  {    
        postOrder(root);  } 
    void inOrder_traversal() { 
        inOrder(root);   } 
    void preOrder_traversal() {
        preOrder(root);  } 
}
public class BST_Transversal{
    public static void main(String[] args) { 
        //construct a BST
        BST_class tree = new BST_class(); 
        
        tree.root = new Node(45); 
        tree.root.left = new Node(10); 
        tree.root.right = new Node(90); 
        tree.root.left.left = new Node(7); 
        tree.root.left.right = new Node(12); 
        //PreOrder Traversal
        System.out.println("BST => PreOrder Traversal:"); 
        tree.preOrder_traversal(); 
        //InOrder Traversal
        System.out.println("\nBST => InOrder Traversal:"); 
        tree.inOrder_traversal(); 
        //PostOrder Traversal
        System.out.println("\nBST => PostOrder Traversal:"); 
        tree.postOrder_traversal(); 
    } 
}

Output

Referensi

https://www.softwaretestinghelp.com/binary-search-tree-in-java/

Adelia Hasna Surya Putri/5025201200