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 Node<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;
  69.         } else if (workNode.left == null) {
  70.             setChild(parentNode, workNode.right, workNode.key);
  71.             return workNode;
  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.                 return workNode;
  87.             } else {
  88.                 setChild(parentNode, replaceNode, workNode.key);
  89.                 parentReplaceNode.right = replaceNode.left;
  90.                 replaceNode.left = workNode.left;
  91.                 replaceNode.right = workNode.right;
  92.                 return workNode;
  93.             }
  94.         }
  95.     }
  96.  
  97.     private Node<T> setChild
  98. 	(Node<T> targetNode, Node<T> newNode, T key) {
  99.         if (targetNode == null) {
  100.             root = newNode;
  101.             return null;
  102.         } else if (key.compareTo(targetNode.key) < 0) {
  103.             targetNode.left = newNode;
  104.             return targetNode;
  105.         } else {
  106.             targetNode.right = newNode;
  107.             return targetNode;
  108.         }
  109.     }
  110.  
  111.     public void printTree() {
  112.         if (root == null) {
  113.             System.out.println("null");
  114.         } else {
  115.             traverseInorder(root);
  116.             System.out.println();
  117.         }
  118.     }
  119.  
  120.     private void traverseInorder(Node<T> tempNode) {
  121.         if (tempNode != null) {
  122.             traverseInorder(tempNode.left);
  123.             System.out.print("(" + tempNode.key + ") ");
  124.             traverseInorder(tempNode.right);
  125.         } else {
  126.             return;
  127.         }
  128.     }
  129.  
  130.     public static void main(String[] args) {
  131.         final int MAXKEY = 100;
  132.         BinaryTree<Integer> tree = new BinaryTree<>();
  133.         Random rand = new Random();
  134.         int numberOfNodes = rand.nextInt(10);
  135.         for (int i = 0; i < numberOfNodes; i++) {
  136.             tree.insert(rand.nextInt(MAXKEY));
  137.         }
  138.         tree.printTree();
  139.  
  140.         for (int i = 0; i < numberOfNodes; ++i) {
  141.             int input = 0;
  142.             do {
  143.                 input = rand.nextInt(MAXKEY);
  144.             } while (tree.delete(input) == null);
  145.             System.out.println("(" + input + ") を削除");
  146.             tree.printTree();
  147.         }
  148.     }
  149. }
Success #stdin #stdout 0.07s 381248KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
(3) (4) (12) (25) (28) (53) (54) (78) 
(25) を削除
(3) (4) (12) (28) (53) (54) (78) 
(54) を削除
(3) (4) (12) (28) (53) (78) 
(28) を削除
(3) (4) (12) (53) (78) 
(53) を削除
(3) (4) (12) (78) 
(12) を削除
(3) (4) (78) 
(3) を削除
(4) (78) 
(4) を削除
(78) 
(78) を削除
null
https://ideone.com/Hh7Zac
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!