Advertisement
Josif_tepe

Untitled

Jun 19th, 2023
877
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 2.41 KB | None | 0 0
  1. public class Main {
  2.     public static void main(String[] args) {
  3.         BST tree = new BST();
  4.         tree.insert(45);
  5.         tree.insert(10);
  6.         tree.insert(7);
  7.         tree.insert(12);
  8.         tree.insert(90);
  9.         tree.insert(50);
  10.  
  11.         tree.inorder();
  12.         System.out.println();
  13.         tree.delete(10);
  14.  
  15.         tree.inorder();
  16.     }
  17.  
  18. }
  19.  
  20. class BST {
  21.     class Node {
  22.         int info;
  23.         Node left, right;
  24.  
  25.         Node(int info) {
  26.             this.info = info;
  27.             left = null;
  28.             right = null;
  29.         }
  30.     }
  31.     Node root;
  32.     BST() {
  33.         root = null;
  34.     }
  35.     void insert(int value) {
  36.         root = insertRecursive(root, value);
  37.     }
  38.     Node insertRecursive(Node node, int value) {
  39.         if(node == null) {
  40.             node = new Node(value);
  41.             return node;
  42.         }
  43.         if(value < node.info) {
  44.             node.left = insertRecursive(node.left, value);
  45.         }
  46.         else if(value > node.info) {
  47.             node.right = insertRecursive(node.right, value);
  48.         }
  49.         return node;
  50.     }
  51.     void delete(int value) {
  52.         root = deleteRecursive(root, value);
  53.     }
  54.     Node deleteRecursive(Node node, int value) {
  55.         if(node == null) {
  56.             return null;
  57.         }
  58.  
  59.         if(value < node.info) {
  60.             node.left = deleteRecursive(node.left, value);
  61.         }
  62.         else if(value > node.info) {
  63.             node.right = deleteRecursive(node.right, value);
  64.         }
  65.         else if(value == node.info){ // sme go nasle, treba da go izbriseme
  66.             if(node.left == null) {
  67.                 return node.right;
  68.             }
  69.             else if(node.right == null) {
  70.                 return node.left;
  71.             }
  72.             node.info = findMinimumValue(node.right);
  73.             node.right = deleteRecursive(node.right, node.info);
  74.         }
  75.         return node;
  76.     }
  77.     int findMinimumValue(Node node) {
  78.         int result = node.info;
  79.         while(node.left != null) {
  80.             result = node.left.info;
  81.             node = node.left;
  82.         }
  83.         return result;
  84.     }
  85.     void inorder() {
  86.         inorderRecursive(root);
  87.     }
  88.     void inorderRecursive(Node node) {
  89.         if(node == null) {
  90.             return;
  91.         }
  92.         inorderRecursive(node.left);
  93.         System.out.println(node.info + " ");
  94.         inorderRecursive(node.right);
  95.     }
  96. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement