SHARE
TWEET

Untitled

a guest Feb 23rd, 2019 54 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.io.File;
  2. import java.io.FileInputStream;
  3. import java.io.FileWriter;
  4. import java.io.IOException;
  5. import java.util.Scanner;
  6.  
  7. public class programm_02 implements Runnable {
  8.     public static void main(String[] args) {
  9.         new Thread(null, new programm_02(), "", 64 * 1024 * 1024).start();
  10.     }
  11.  
  12.     public class Knot {
  13.         private long key;
  14.         private Knot left;
  15.         private Knot right;
  16.  
  17.         public Knot(long key) {
  18.             this.key = key;
  19.         }
  20.     }
  21.  
  22.     public class Tree {
  23.         private Knot root;
  24.  
  25.         public Tree() {
  26.         }
  27.  
  28.         public void insert(long x) {
  29.             Knot parent = null;
  30.             Knot knot = root;
  31.  
  32.             while (knot != null) {
  33.                 if (x < knot.key) {
  34.                     parent = knot;
  35.                     knot = knot.left;
  36.                 } else if (x > knot.key) {
  37.                     parent = knot;
  38.                     knot = knot.right;
  39.                 } else {
  40.                     return;
  41.                 }
  42.             }
  43.  
  44.             Knot newKnot = new Knot(x);
  45.  
  46.             if (x < parent.key) {
  47.                 parent.left = newKnot;
  48.             } else if (x > parent.key) {
  49.                 parent.right = newKnot;
  50.             }
  51.         }
  52.  
  53.         public void create(Scanner sc) {
  54.             if (root == null) {
  55.                 root = new Knot(sc.nextLong());
  56.             }
  57.             while (sc.hasNext()) {
  58.                 insert(sc.nextLong());
  59.             }
  60.         }
  61.  
  62.         public void bypass(Knot knot, FileWriter fw) throws IOException {
  63.             if (knot != null) {
  64.                 fw.write(knot.key + "\n");
  65.                 bypass(knot.left, fw);
  66.                 bypass(knot.right, fw);
  67.             }
  68.         }
  69.  
  70.         public void delete (long key) {
  71.             Knot knot = root;
  72.             Knot parent = null;
  73.             if(key == root.key && knot.right == null && knot.left != null) {
  74.                 root = knot.left;
  75.                 return;
  76.             }   else if (key == root.key && knot.right != null && knot.left == null) {
  77.                 root = knot.right;
  78.                 return;
  79.             }
  80.             while (true) {
  81.                 if (key < knot.key) {
  82.                     parent = knot;
  83.                     knot = knot.left;
  84.                     if (knot.key == key && (knot.left == null && knot.right == null)) {
  85.                         parent.left = null;
  86.                         return;
  87.                     } else if (knot.key == key && (knot.left == null && knot.right != null)) {
  88.                         parent.left = knot.right;
  89.                         return;
  90.                     }
  91.                     else if (knot.key == key && (knot.left != null && knot.right == null)) {
  92.                         parent.left = knot.left;
  93.                         return;
  94.                     }
  95.                 } else if (key > knot.key) {
  96.                     parent = knot;
  97.                     knot = knot.right;
  98.                     if (knot.key == key && (knot.left == null && knot.right == null)) {
  99.                         parent.right = null;
  100.                         return;
  101.                     } else if (knot.key == key && (knot.left == null && knot.right != null)) {
  102.                         parent.right = knot.right;
  103.                         return;
  104.                     }
  105.                     else if (knot.key == key && (knot.left != null && knot.right == null)) {
  106.                         parent.right = knot.left;
  107.                         return;
  108.                     }
  109.                 } else if (key == knot.key && knot.left != null && knot.right != null) {
  110.                     Knot newRoot = knot;
  111.                     knot = knot.right;
  112.                     if(knot.left != null) {
  113.                         while (knot.left != null) {
  114.                             knot = knot.left;
  115.                         }
  116.                         long temp = knot.key;
  117.                         delete(knot.key);
  118.                         newRoot.key = temp;
  119.                         return;
  120.                     }
  121.                     else {
  122.                         newRoot.key = knot.key;
  123.                         newRoot.right = knot.right;
  124.                         return;
  125.                     }
  126.                 }
  127.             }
  128.         }
  129.  
  130.         public boolean check (long key) {
  131.             Knot knot = root;
  132.             while(knot != null) {
  133.                 if(key < knot.key) {
  134.                     knot = knot.left;
  135.                 } else if (key > knot.key) {
  136.                     knot = knot.right;
  137.                 } else if (key == knot.key) {
  138.                     return true;
  139.                 }
  140.             }
  141.             return false;
  142.         }
  143.     }
  144.     public void run() {
  145.         FileInputStream fin = null;
  146.         FileWriter fw = null;
  147.         try {
  148.             fin = new FileInputStream("input.txt");
  149.             Scanner sc = new Scanner(fin);
  150.             long deletedKey = sc.nextLong();
  151.             fw = new FileWriter("output.txt");
  152.             Tree tree = new Tree();
  153.             tree.create(sc);
  154.             if (tree.check(deletedKey) == true) {
  155.                 tree.delete(deletedKey);
  156.                 tree.bypass(tree.root, fw);
  157.                 fw.close();
  158.             }
  159.         }
  160.         catch (IOException e) {
  161.             e.printStackTrace();
  162.         }
  163.  
  164.     }
  165. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top