public class Node {
private int data;
private Node leftChild;
private Node rightChild;
public Node(int newData) {
data = newData;
}
//методы узла
}
public class Node {
private int key;
private Data myData;
private Node leftChild;
private Node rightChild;
public Node(int newData) {
data = newData;
}
public Node getLeftChild() {
return leftChild;
}
public Node getRightChild() {
return rightChild;
}
//методы узла
}
class Data {
private String s;
public Data(String s) {
this.s = s;
}
public String getString() {
return s;
}
}
public class BinaryTree {
private Node root;
//методы дерева
}
public Node find(int findData) {
Node current = root;
while (current.getData() != findData) {
if (findData < current.getData()) //идем налево
current = current.getLeftChild();
else //идем направо(ситуацию равенства проверяет цикл)
current = current.getRightChild();
if (current == null)//если потомка не существует, значит в дереве нет элемента с ключом findData
return null;
}
return current;
}
public void insert(int insertData) {
Node current = root;
Node parent;//родитель текущего узла
Node newNode = new Node(insertData);
if (root == null)
root = newNode;
else {
while (true) {
parent = current;
if (insertData < current.getData()) {
current = current.getLeftChild();
if (current == null) {
parent.setLeftChild(newNode);
return;
}
}
else {
current = current.getRightChild();
if (current == null) {
parent.setRightChild(newNode);
return;
}
}
}
}
}
public boolean delete(int deleteData) {
Node current = root;
Node parent = current;
boolean isLeftChild = false;//информация о местоположении удаляемого листа по отношению к его родителю
while (current.getData() != deleteData) {
parent = current;
if (deleteData < current.getData()) {
current = current.getLeftChild();
isLeftChild = true;
} else {
isLeftChild = false;
current = current.getRightChild();
}
if (current == null)
return false;
}
if (current.getLeftChild() == null && current.getRightChild() == null) {//если удаляем лист
if (current == root)//если он корень, то достаточно сделать его равным null
current = null;
else if (isLeftChild)//удалем некорневой лист, являющийся
parent.setLeftChild(null);//левым потомком своего родителя
else
parent.setRightChild(null);//правым потомком своего родителя
}
...
//продолжение метода delete
else if (current.getRightChild() == null) {//Если удаляемый узел имеет левого потомка
if (current == root)//удаляемый узел - корень
root = current.getLeftChild();//сделать корнем его (единственный) левый потомок
else if (isLeftChild)//Если удаляемый узел является
parent.setLeftChild(current.getLeftChild());//левым потомком своего родителя
else
current.setRightChild(current.getLeftChild());//правым потомком своего родителя
} else if (current.getLeftChild() == null) {//Если удаляемый узел имеет правого потомка
if (current == root)//удаляемый узел - корень
root = current.getRightChild();//сделать корнем его (единственный) правый потомок
else if (isLeftChild)//если удаляемый узел является
parent.setLeftChild(current.getRightChild());//левым потомком своего родителя
else
parent.setRightChild(current.getRightChild());//правым потомком своего родителя
}
...
public Node getSuccessor(Node deleteNode) {
Node parentSuccessor = deleteNode;//родитель преемника
Node successor = deleteNode;//преемник
Node current = successor.getRightChild();//просто "пробегающий" узел
while (current != null) {
parentSuccessor = successor;
successor = current;
current = current.getLeftChild();
}
//на выходе из цикла имеем преемника и родителя преемника
if (successor != deleteNode.getRightChild()) {//если преемник не совпадает с правым потомком удаляемого узла
parentSuccessor.setLeftChild(successor.getRightChild());//то его родитель забирает себе потомка преемника, чтобы не потерять его
successor.setRightChild(deleteNode.getRightChild());//связываем преемника с правым потомком удаляемого узла
}
return successor;
}
//продолжение метода delete
else {
Node successor = getSuccessor(current);//получить преемника
if (current == root)//если удаляемый элемент - корень дерева
root = successor;//то сделать его преемника корнем
else if (isLeftChild)//если удаляемый элемент является
parent.setLeftChild(successor);//левым потомком своего родителя
else
parent.setRightChild(successor);//правым потомком своего родителя
}
return true;
}
public boolean delete(int deleteData) {
Node current = root;
Node parent = current;
boolean isLeftChild = false;
while (current.getData() != deleteData) {
parent = current;
if (deleteData < current.getData()) {
current = current.getLeftChild();
isLeftChild = true;
} else {
isLeftChild = false;
current = current.getRightChild();
}
if (current == null)//удаляемый элемент не найден
return false;
}
if (current.getLeftChild() == null && current.getRightChild() == null) {
if (current == root)
current = null;
else if (isLeftChild)
parent.setLeftChild(null);
else
parent.setRightChild(null);
}
else if (current.getRightChild() == null) {
if (current == root)
root = current.getLeftChild();
else if (isLeftChild)
parent.setLeftChild(current.getLeftChild());
else
current.setRightChild(current.getLeftChild());
} else if (current.getLeftChild() == null) {
if (current == root)
root = current.getRightChild();
else if (isLeftChild)
parent.setLeftChild(current.getRightChild());
else
parent.setRightChild(current.getRightChild());
}
else {
Node successor = getSuccessor(current);
if (current == root)
root = successor;
else if (isLeftChild)
parent.setLeftChild(successor);
else
parent.setRightChild(successor);
}
return true;
}
public Node getMinimum(Node startPoint) {
Node current = startPoint;
Node parrent = current;
while (current != null) {
parrent = current;
current = current.getLeftChild();
}
return parrent;
}
public Node getMaximum(Node startPoint) {
Node current = startPoint;
Node parrent = current;
while (current != null) {
parrent = current;
current = current.getRightChild();
}
return parrent;
}
public void inOrder(Node current) {
if (current != null) {
inOrder(current.getLeftChild());
System.out.println(current.getData() + " ");//Здесь может быть все, что угодно
inOrder(current.getRightChild());
}
}
public class Node {
private int data;
private Node leftChild;
private Node rightChild;
public Node(int newData) {
data = newData;
}
public void setLeftChild(Node newNode) {
leftChild = newNode;
}
public void setRightChild(Node newNode) {
rightChild = newNode;
}
public Node getLeftChild() {
return leftChild;
}
public Node getRightChild() {
return rightChild;
}
public int getData() {
return data;
}
}
public class BinaryTree {
private Node root;
public Node find(int findData) {
Node current = root;
while (current.getData() != findData) {
if (findData < current.getData())
current = current.getLeftChild();
else
current = current.getRightChild();
if (current == null)
return null;
}
return current;
}
public void insert(int insertData) {
Node current = root;
Node parrent;
Node newNode = new Node(insertData);
if (root == null)
root = newNode;
else {
while (true) {
parrent = current;
if (insertData < current.getData()) {
current = current.getLeftChild();
if (current == null) {
parrent.setLeftChild(newNode);
return;
}
}
else {
current = current.getRightChild();
if (current == null) {
parrent.setRightChild(newNode);
return;
}
}
}
}
}
public Node getMinimum(Node startPoint) {
Node current = startPoint;
Node parrent = current;
while (current != null) {
parrent = current;
current = current.getLeftChild();
}
return parrent;
}
public Node getMaximum(Node startPoint) {
Node current = startPoint;
Node parrent = current;
while (current != null) {
parrent = current;
current = current.getRightChild();
}
return parrent;
}
public Node getRoot() {
return root;
}
public Node getSuccessor(Node deleteNode) {
Node parrentSuccessor = deleteNode;
Node successor = deleteNode;
Node current = successor.getRightChild();
while (current != null) {
parrentSuccessor = successor;
successor = current;
current = current.getLeftChild();
}
if (successor != deleteNode.getRightChild()) {
parrentSuccessor.setLeftChild(successor.getRightChild());
successor.setRightChild(deleteNode.getRightChild());
}
return successor;
}
public boolean delete(int deleteData) {
Node current = root;
Node parent = current;
boolean isLeftChild = false;
while (current.getData() != deleteData) {
parent = current;
if (deleteData < current.getData()) {
current = current.getLeftChild();
isLeftChild = true;
} else {
isLeftChild = false;
current = current.getRightChild();
}
if (current == null)
return false;
}
if (current.getLeftChild() == null && current.getRightChild() == null) {
if (current == root)
current = null;
else if (isLeftChild)
parent.setLeftChild(null);
else
parent.setRightChild(null);
}
else if (current.getRightChild() == null) {
if (current == root)
root = current.getLeftChild();
else if (isLeftChild)
parent.setLeftChild(current.getLeftChild());
else
current.setRightChild(current.getLeftChild());
} else if (current.getLeftChild() == null) {
if (current == root)
root = current.getRightChild();
else if (isLeftChild)
parent.setLeftChild(current.getRightChild());
else
parent.setRightChild(current.getRightChild());
}
else {
Node successor = getSuccessor(current);
if (current == root)
root = successor;
else if (isLeftChild)
parent.setLeftChild(successor);
else
parent.setRightChild(successor);
}
return true;
}
public void inOrder(Node current) {
if (current != null) {
inOrder(current.getLeftChild());
System.out.println(current.getData() + " ");
inOrder(current.getRightChild());
}
}
}
import java.util.Scanner;
public class Main {
public static void main (String[] args) {
Scanner scanner = new Scanner(System.in);
BinaryTree binaryTree = new BinaryTree();
int operationCommand = 0;
int data = 0;
while (true) {
System.out.println("Input 1 to add element, 2 to delete, 3 to search, 4 to get max, 5 to get min, 0 to exit");
operationCommand = scanner.nextInt();
switch (operationCommand) {
case 0:
scanner.close();
return;
case 1:
System.out.println("Input element");
data = scanner.nextInt();
binaryTree.insert(data);
break;
case 2:
System.out.println("Input element");
data = scanner.nextInt();
binaryTree.delete(data);
break;
case 3:
System.out.println("Input element");
data = scanner.nextInt();
if (binaryTree.find(data) != null)
System.out.println("OK");
else
System.out.println("Not found");
break;
case 4:
System.out.println(binaryTree.getMaximum(binaryTree.getRoot()));
break;
case 5:
System.out.println(binaryTree.getMinimum(binaryTree.getRoot()));
break;
default:
System.out.println("Another key to continue");
break;
}
}
}
}
К сожалению, не доступен сервер mySQL