fork download
copy 
  1. import java.util.Scanner;
  2.  
  3. class BinaryTree<T extends Comparable<? super T>> {
  4.   class Node<T> {
  5.     public Node<T> left;
  6.     public Node<T> right;
  7.     public T key;
  8.     Node(T newKey) {
  9.       this.left = this.right = null;
  10.       this.key = newKey;
  11.     }
  12.   }
  13.   private Node<T> root;
  14.   public BinaryTree() { root = null; }
  15.  
  16.   private void insertSub(Node<T> parentNode, Node<T> workNode, T newKey) {
  17.     // not use while-loop
  18.     //System.out.println(parentNode + ":" +  workNode + ":(" + newKey + ")");
  19.     if (parentNode == null && workNode == null) {
  20.       this.root = new Node<T>(newKey);
  21.       return;
  22.     }
  23.     if (workNode == null) {
  24.       if (newKey.compareTo(parentNode.key) < 0)
  25.         parentNode.left = new Node<T>(newKey);
  26.       else
  27.         parentNode.right = new Node<T>(newKey);
  28.     } else {
  29.       if (newKey.compareTo(workNode.key) < 0)
  30.         insertSub(workNode, workNode.left, newKey);
  31.       else
  32.         insertSub(workNode, workNode.right, newKey);
  33.     }
  34.   }
  35.   public void insert(T newKey) { insertSub(null, root, newKey); }
  36.  
  37.  
  38.   private boolean deleteSub(Node<T> parentNode, Node<T> workNode, T newKey) {
  39.     // not use while-loop
  40.     // System.out.println(parentNode + ":" +  workNode + ":(" + newKey + ")");
  41.     if (workNode == null)
  42.       return false;
  43.     if (parentNode == null) {
  44.       assert workNode == this.root;
  45.       assert workNode != null;
  46.       if (newKey.compareTo(workNode.key) == 0) {
  47.         /* delete root */
  48.         if (workNode.left == null) {
  49.           this.root = workNode.right;
  50.           return true;
  51.         }
  52.         if (workNode.right == null) {
  53.           this.root = workNode.left;
  54.           return true;
  55.         }
  56.         /* the top node has 2 child nodes */
  57.         this.root = workNode.left; /* == this.root */
  58.         Node<T> p;
  59.         for (p = workNode.left; p.right != null; p = p.right)
  60.         ;
  61.         p.right = workNode.right;
  62.         return true;
  63.       } else {
  64.         if (newKey.compareTo(workNode.key) < 0)
  65.           return deleteSub(workNode, workNode.left, newKey);
  66.         else
  67.           return deleteSub(workNode, workNode.right, newKey);
  68.       }
  69.     }
  70.  
  71.     assert workNode != this.root;
  72.  
  73.     if (newKey.compareTo(workNode.key) != 0) {
  74.       if (newKey.compareTo(workNode.key) < 0)
  75.         return deleteSub(workNode, workNode.left, newKey);
  76.       else
  77.         return deleteSub(workNode, workNode.right, newKey);
  78.     }
  79. //------------------------------------------------------------
  80.     assert newKey.compareTo(workNode.key) == 0;
  81.  
  82.     if (workNode.right == null) {
  83.       if (parentNode.left == workNode) {
  84.         parentNode.left = workNode.left;
  85.       } else {
  86.         assert parentNode.right == workNode;
  87.         parentNode.right = workNode.left;
  88.       }
  89.     } else if (workNode.left == null) {
  90.       assert workNode.right != null;
  91.       if (parentNode.left == workNode) {
  92.         parentNode.left = workNode.right;
  93.       } else {
  94.         assert parentNode.right == workNode;
  95.         parentNode.right = workNode.right;
  96.       }
  97.     } else {
  98.       /* the parent node has 2 child nodes */
  99.       if (parentNode.left == workNode)
  100.         parentNode.left = workNode.left;
  101.       else
  102.         parentNode.right = workNode.left;
  103.       Node<T> p;
  104.       for (p = workNode.left; p.right != null; p = p.right)
  105.         ;
  106.       p.right = workNode.right;
  107.     }
  108.     return true;
  109.   }
  110.   public boolean delete(T newKey) { return deleteSub(null, root, newKey); }
  111.  
  112.   private static int N = 3;
  113.   private void vomitTree(Node<T> parent, int c) {
  114.     if (parent == null)
  115.       return;
  116.     vomitTree(parent.left, c + N);
  117.     for (int i = 0; i < c; i++) System.out.print(' ');
  118.     System.out.println(parent.key);
  119.     vomitTree(parent.right, c + N);    
  120.   }
  121.   public void vomitTree() { vomitTree(root, 0);  }
  122. }
  123.  
  124. class Main {
  125.   public static void main(String[] args) {
  126.     BinaryTree<Integer> tree = new BinaryTree<>();
  127.     Scanner sc = new Scanner(System.in);
  128.  
  129.     for (;;) {
  130.       System.out.print(">");
  131.       int input = 0;
  132.       input = sc.nextInt();
  133.       if (input < 0) break;
  134.  
  135.       tree.insert(input);
  136.       System.out.println("");
  137.       tree.vomitTree();
  138.     }
  139.  
  140.     System.out.println("deleteing");
  141.  
  142.     for (;;) {
  143.       System.out.print(">");
  144.       int input = 0;
  145.       input = sc.nextInt();
  146.       if (input < 0) break;
  147.  
  148.       if (tree.delete(input) == false) System.out.println("not found.");
  149.  
  150.       System.out.println("");
  151.       tree.vomitTree();
  152.     }
  153.   }
  154. }
  155. /* end */
  156.  
Success #stdin #stdout 0.11s 380736KB
comments (?)
stdin
copy 
10
5
15
1
8
12
20
-1
5
10
15
100
8
12
20
100
1
1
-1
stdout
copy 
>
10
>
   5
10
>
   5
10
   15
>
      1
   5
10
   15
>
      1
   5
      8
10
   15
>
      1
   5
      8
10
      12
   15
>
      1
   5
      8
10
      12
   15
      20
>deleteing
>
   1
      8
10
      12
   15
      20
>
1
   8
         12
      15
         20
>
1
   8
      12
         20
>not found.

1
   8
      12
         20
>
1
   12
      20
>
1
   20
>
1
>not found.

1
>
>not found.

>
https://ideone.com/2j9r6p
language:
Java (HotSpot 12)
created:
9 years ago
visibility:
public

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!