fork download
copy 
  1. import java.util.*;
  2.  
  3. class BinaryTree<T extends Comparable<? super T>> {
  4.  
  5.     class Node<T>{
  6.  
  7.         Node<T> left;
  8.         Node<T> right;
  9.         T key;
  10.  
  11.         Node(T newKey) {
  12.             left = null;
  13.             right = null;
  14.             key = newKey;
  15.         }
  16.     }
  17.  
  18.     private Node<T> root;
  19.     public BinaryTree() {
  20.         root = null;
  21.     }
  22.  
  23.     public void insert(T newKey) {
  24.         Node<T> workNode = root;
  25.         Node<T> parentNode = null;
  26.         while (workNode != null) {
  27.             parentNode = workNode;
  28.             if (newKey.compareTo(workNode.key) < 0) {
  29.                 workNode = workNode.left;
  30.             } else {
  31.                 workNode = workNode.right;
  32.             }
  33.         }
  34.         if (parentNode == null) {
  35.             root = new Node<T>(newKey);
  36.         } else if (newKey.compareTo(parentNode.key) < 0) {
  37.             parentNode.left = new Node<T>(newKey);
  38.         } else {
  39.             parentNode.right = new Node<T>(newKey);
  40.         }
  41.     }
  42.  
  43.     public T delete(T key) {
  44.         if (root == null) {
  45.             return null;
  46.         }
  47.  
  48.         Node<T> workNode = root;
  49.         Node<T> parentNode = null;
  50.         while (key.compareTo(workNode.key) != 0) {
  51.             if (key.compareTo(workNode.key) < 0) {
  52.                 if (workNode.left == null) {
  53.                     return null;
  54.                 }
  55.                 parentNode = workNode;
  56.                 workNode = workNode.left;
  57.             } else {
  58.                 if (workNode.right == null) {
  59.                     return null;
  60.                 }
  61.                 parentNode = workNode;
  62.                 workNode = workNode.right;
  63.             }
  64.         }
  65.  
  66.         if (workNode.right == null) {
  67.             setChild(parentNode, workNode.left, workNode.key);
  68.             return workNode.key;
  69.         } else if (workNode.left == null) {
  70.             setChild(parentNode, workNode.right, workNode.key);
  71.             return workNode.key;
  72.  
  73.         } else {
  74.             Node<T> replaceNode = workNode.left;
  75.             Node<T> parentReplaceNode = workNode;
  76.  
  77.             while (replaceNode.right != null) {
  78.                 parentReplaceNode = replaceNode;
  79.                 replaceNode = replaceNode.right;
  80.             }
  81.  
  82.             if (parentReplaceNode == workNode) {
  83.                 setChild(parentNode, replaceNode, workNode.key);
  84.                 parentReplaceNode.left = null;
  85.                 replaceNode.right = workNode.right;
  86.             } else {
  87.                 setChild(parentNode, replaceNode, workNode.key);
  88.                 parentReplaceNode.right = replaceNode.left;
  89.                 replaceNode.left = workNode.left;
  90.                 replaceNode.right = workNode.right;
  91.             }
  92.             return workNode.key;
  93.         }
  94.     }
  95.  
  96.     private Node<T> setChild
  97. 	(Node<T> targetNode, Node<T> newNode, T key) {
  98.         if (targetNode == null) {
  99.             root = newNode;
  100.             return null;
  101.         } else if (key.compareTo(targetNode.key) < 0) {
  102.             targetNode.left = newNode;
  103.             return targetNode;
  104.         } else {
  105.             targetNode.right = newNode;
  106.             return targetNode;
  107.         }
  108.     }
  109.  
  110.     public T printAll() {
  111.         if (root == null) {
  112.             System.out.println("null");
  113.             return null;
  114.         } else {
  115.             traverseInorder(root);
  116.             System.out.println();
  117.             return root.key;
  118.         }
  119.     }
  120.  
  121.     private void traverseInorder(Node<T> tempNode) {
  122.         if (tempNode != null) {
  123.             traverseInorder(tempNode.left);
  124.             System.out.print("(" + tempNode.key + ") ");
  125.             traverseInorder(tempNode.right);
  126.         } else {
  127.             return;
  128.         }
  129.     }
  130.  
  131.     public static void main(String[] args) {
  132.         BinaryTree<Integer> tree = new BinaryTree<>();
  133.         Scanner sc = new Scanner(System.in);
  134.  
  135.         for (;;) {
  136.             int input = 0;
  137.             // System.out.print("挿入する数値を入力して下さい（負数で挿入終了）: ");
  138.             input = sc.nextInt();
  139.             if (input < 0) {
  140.                 break;
  141.             }
  142.             System.out.println("(" + input + ")を挿入");
  143.             tree.insert(input);
  144.             tree.printAll();
  145.         }
  146.  
  147.         for (;;) {
  148.             tree.printAll();
  149.             // System.out.print("削除する数値を入力して下さい（負数で終了）: ");
  150.             int input = sc.nextInt();
  151.             if (input < 0) {
  152.                 break;
  153.             }
  154.             Integer deletedInteger = tree.delete(input);
  155.             if (deletedInteger != null) {
  156.                 System.out.println("(" + deletedInteger + ")を削除");
  157.             } else {
  158.                 System.out.println("(" + input + ")は存在しません");
  159.             }
  160.         }
  161.     }
  162. }
Success #stdin #stdout 0.11s 380736KB
comments (?)
stdin
copy 
10 5 20 15 20 30 -1
20 5 10 35 15 10 20 30 -1
stdout
copy 
(10)を挿入
(10) 
(5)を挿入
(5) (10) 
(20)を挿入
(5) (10) (20) 
(15)を挿入
(5) (10) (15) (20) 
(20)を挿入
(5) (10) (15) (20) (20) 
(30)を挿入
(5) (10) (15) (20) (20) (30) 
(5) (10) (15) (20) (20) (30) 
(20)を削除
(5) (10) (15) (20) (30) 
(5)を削除
(10) (15) (20) (30) 
(10)を削除
(15) (20) (30) 
(35)は存在しません
(15) (20) (30) 
(15)を削除
(20) (30) 
(10)は存在しません
(20) (30) 
(20)を削除
(30) 
(30)を削除
null
https://ideone.com/vDPNFb
language:
Java (HotSpot 12)
created:
10 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!