線分データの数え上げ

```package binaryTree;

/**
*  2分探索木
*
*  @version \$Revision: 1.6 \$, \$Date: 2003/04/28 23:23:14 \$
*/

import java.io.*;

public class BinarySearchTreeRY {
class Node {
Node left, right;  double value;
Node(Node left, Node right, double value) {
this.left = left;  this.right = right;  this.value=value;
}

}

final private Node
zero = new Node(null, null,  -99),  // 各葉の子(番人用)
rootParent = new Node(null, zero,  0);  // {\tt rootParent.right} が根
private Node parent;  private boolean isChildLeft;  // 検索成功時の親

public boolean isEmpty() { return (rootParent.right == zero); }

public Node searchNode(double value) {  // 検索（未登録なら {\tt null} を返す）
zero.value=-99; // {\tt zero} は番人
Node child = rootParent;
//int cmp = 1;  // 最初の子は {\tt rootParent.right}
double cmp = 1;
boolean loop=true;
do {
parent = child;
if (cmp < 0) { child = child.left;  isChildLeft = true; }
else         { child = child.right; isChildLeft = false; }
//System.out.println("value="+value);
//System.out.println("child.value="+child.value);
if(child.value==-99){
loop=false;
}else{
cmp=-value+child.value;
if(cmp==0){
loop=false;
}
}

//} while ((cmp = key.compareTo(child.key)) != 0);
} while (loop);
//System.out.println("childvalue="+child.value);
return (child == zero) ? null : child;
}

public Node insertNode(double value) {  // 挿入（登録）
if (searchNode(value) != null) return null;  // すでに登録されている

Node newChild = new Node(zero, zero, value);
if (isChildLeft) parent.left  = newChild;
else             parent.right = newChild;
return newChild;
}

public boolean deleteNode(double value) {  // 削除できれば {\tt true} を返す
final Node target = searchNode(value);
if (target == null) return false;  // 未登録

Node newChild;  // {\tt target} の代わりに {\tt parent} の子になる
if      (target.left  == zero) newChild = target.right;
else if (target.right == zero) newChild = target.left;
else {
Node s = target.left;  // {\tt s} を {\tt target} の次に小さいものに
if (s.right != zero) {
Node p;  // {\tt s} の親
do {  p = s;  s = s.right;  } while (s.right != zero);
p.right = s.left;  s.left = target.left;
}
s.right = target.right;  newChild = s;
}
if (isChildLeft) parent.left  = newChild;
else             parent.right = newChild;
return true;  // 削除成功, C++ では {\tt delete target;} も必要
}

public void printNode() {
if (!isEmpty()) printNode(rootParent.right);
}

private int depth = 0;
private void printNode(Node p) { // 深さ優先探索,中間順でキーを表示
if (p.left != zero) {
depth++;  printNode(p.left);  depth--;
}
for (int i = 0; i < depth; i++) System.out.print("     ");

System.out.println(p.value);
if (p.right != zero) {
depth++;  printNode(p.right);  depth--;
}
}

public static void main(String[] args) throws IOException {
int n=10;
double[] data=new double[n];
for(int i=0;i<data.length;i++){
data[i]=Math.random();
}
BinarySearchTreeRY tree = new BinarySearchTreeRY();

/*
System.out.print("命令 Iabc:  abcを挿入\n"
+ "     Dabc:  abcを削除\n"
+ "     Sabc:  abcを検索\n");
*/
String message;
for (int i=0;i<data.length;i++) {

double value=data[i];
if (tree.insertNode(value) != null)
message = "登録しました.";
else message = "登録ずみです.";
//break;
System.out.println(message);  tree.printNode();
}
int[] searchID={5,3,8};
for(int i=0;i<searchID.length;i++){
if (tree.searchNode(data[searchID[i]]) != null)
message = "登録されています.";
else message = "登録されていません";
System.out.println(message);
}
double valueex=2;
if (tree.searchNode(valueex) != null)
message = "登録されています.";
else message = "登録されていません";
System.out.println(message);

int[] deleteID={6,3,9};
for(int i=0;i<deleteID.length;i++){
if (tree.deleteNode(data[deleteID[i]]))
message = "削除しました.";
else message = "登録されていません.";
System.out.println(message);
}

tree.printNode();
/*
for (int i=0;i<data.length;i++) {

String message;
double value=data[i];
String insert="'I'";
switch ('I') {
case 'I':
if (tree.insertNode(value) != null)
message = "登録しました.";
else message = "登録ずみです.";
break;
case 'D':
if (tree.deleteNode(value))
message = "削除しました.";
else message = "登録されていません.";
break;
case 'S':
if (tree.searchNode(value) != null)
message = "登録されています.";
else message = "登録されていません";
break;
default:
message = "使えるのは I, D, S です.";
break;
}
System.out.println(message);  tree.printNode();
}
*/
}
}

```