fork download
copy 
  1. class BinTree {
  2.     private BinNode root;
  3.  
  4.     public BinTree(BinNode root) {
  5.         this.root = root;
  6.     }
  7.  
  8.     public void recreate(int key) {
  9.         if(root != null) { root = root.getNewRoot(key); }
  10.         if(root != null) { root.search(root, key); }
  11.     }
  12.  
  13.     @Override public String toString() {
  14.         return "{" + (root == null ? "" : "" + root.getKey() + (root.getLeft() == null ? "" : ", left: " + root.getLeft()) + (root.getRight() == null ? "" : ", right: " + root.getRight())) + "}";
  15.     }
  16. }
  17.  
  18. class BinNode {
  19.     private int key;
  20.     private BinNode left;
  21.     private BinNode right;
  22.     private BinNode parent;
  23.  
  24.     public BinNode(int key, BinNode left, BinNode right) {
  25.         this.key = key;
  26.         this.left = left;
  27.         this.right = right;
  28.         if(this.left  != null) { this.left.parent = this; }
  29.         if(this.right != null) { this.right.parent = this; }
  30.     }
  31.  
  32.     public BinNode getNewRoot(int key) {
  33.         BinNode newRoot = this;
  34.         for( ; newRoot != null; ) {
  35.             if(key == newRoot.key) { throw new IllegalArgumentException(); }
  36.             if(key < newRoot.key) { newRoot = newRoot.left; }
  37.             else { break; }
  38.         }
  39.         return newRoot;
  40.     }
  41.  
  42.     public void search(BinNode p, int key) {
  43.         if(p == null) { return; }
  44.         else if(p.key < key) {
  45.             search(p.right, key);
  46.         } else if(p.key > key) {
  47.             if(p.parent != null) { p.parent.right = p.left; }
  48.             search(p.left, key);
  49.         } else {
  50.             throw new IllegalArgumentException();
  51.         }
  52.     }
  53.  
  54.     public int getKey() { return key; }
  55.     public BinNode getLeft() { return left; }
  56.     public BinNode getRight() { return right; }
  57.  
  58.     @Override public String toString() {
  59.         return "[" + key + (left == null ? "" : ", left: " + left) + (right == null ? "" : ", right: " + right) + "]";
  60.     }
  61. }
  62.  
  63. public class BSTMinDistiller {
  64.     public static void main(String[] args) {
  65.         BinNode n02 = new BinNode( 2, null, null);
  66.         BinNode n10 = new BinNode(10, null, null);
  67.         BinNode n14 = new BinNode(14, null, null);
  68.         BinNode n22 = new BinNode(22, null, null);
  69.         BinNode n26 = new BinNode(26, null, null);
  70.         BinNode n34 = new BinNode(34, null, null);
  71.         BinNode n38 = new BinNode(38, null, null);
  72.         BinNode n46 = new BinNode(46, null, null);
  73.         BinNode n52 = new BinNode(52, null, null);
  74.         BinNode n60 = new BinNode(60, null, null);
  75.         BinNode n64 = new BinNode(64, null, null);
  76.         BinNode n72 = new BinNode(72, null, null);
  77.         BinNode n76 = new BinNode(76, null, null);
  78.         BinNode n84 = new BinNode(84, null, null);
  79.         BinNode n88 = new BinNode(88, null, null);
  80.         BinNode n96 = new BinNode(96, null, null);
  81.  
  82.         BinNode n06 = new BinNode( 6, n02, n10);
  83.         BinNode n18 = new BinNode(18, n14, n22);
  84.         BinNode n30 = new BinNode(30, n26, n34);
  85.         BinNode n42 = new BinNode(42, n38, n46);
  86.         BinNode n56 = new BinNode(56, n52, n60);
  87.         BinNode n68 = new BinNode(68, n64, n72);
  88.         BinNode n80 = new BinNode(80, n76, n84);
  89.         BinNode n92 = new BinNode(92, n88, n96);
  90.  
  91.         BinNode n12 = new BinNode(12, n06, n18);
  92.         BinNode n36 = new BinNode(36, n30, n42);
  93.         BinNode n62 = new BinNode(62, n56, n68);
  94.         BinNode n86 = new BinNode(86, n80, n92);
  95.  
  96.         BinNode n25 = new BinNode(25, n12, n36);
  97.         BinNode n75 = new BinNode(75, n62, n86);
  98.  
  99.         BinTree tree01 = new BinTree(new BinNode(50, n25, n75));
  100.         System.out.println("tree01");
  101.         System.out.println(tree01);
  102.  
  103.         BinTree tree02 = new BinTree(new BinNode(50, n25, n75));
  104.         tree02.recreate(65);
  105.         System.out.println("tree02: 65");
  106.         System.out.println(tree02);
  107.  
  108.         BinTree tree03 = new BinTree(new BinNode(50, n25, n75));
  109.         tree03.recreate(49);
  110.         System.out.println("tree03: 49");
  111.         System.out.println(tree03);
  112.  
  113.         BinTree tree04 = new BinTree(new BinNode(50, n25, n75));
  114.         tree04.recreate(1);
  115.         System.out.println("tree04: 1");
  116.         System.out.println(tree04);
  117.  
  118.         BinTree tree05 = new BinTree(new BinNode(50, n25, n75));
  119.         tree05.recreate(97);
  120.         System.out.println("tree05: 97");
  121.         System.out.println(tree05);
  122.  
  123.         BinTree tree06 = new BinTree(new BinNode(50, n25, n75));
  124.         tree06.recreate(9);
  125.         System.out.println("tree06: 9");
  126.         System.out.println(tree06);
  127.  
  128.         System.out.println();
  129.  
  130.         BinTree tree07 = new BinTree(new BinNode(2, null, null));
  131.         System.out.println("tree07");
  132.         System.out.println(tree07);
  133.  
  134.         BinTree tree08 = new BinTree(new BinNode(2, null, null));
  135.         tree08.recreate(3);
  136.         System.out.println("tree08: 3");
  137.         System.out.println(tree08);
  138.  
  139.         BinTree tree09 = new BinTree(new BinNode(2, null, null));
  140.         tree09.recreate(1);
  141.         System.out.println("tree09: 1");
  142.         System.out.println(tree09);
  143.  
  144.         System.out.println();
  145.  
  146.         BinTree tree10 = new BinTree(null);
  147.         System.out.println("tree10");
  148.         System.out.println(tree10);
  149.  
  150.         BinTree tree11 = new BinTree(null);
  151.         tree11.recreate(99);
  152.         System.out.println("tree11: 99");
  153.         System.out.println(tree11);
  154.     }
  155. }
Not running #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/0Tdgo1
language:
Java (HotSpot 12)
created:
11 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!