дерево / BinaryTree

import java.util.Objects;


/**
*
* @param <T> type of elements in tree
*/

public class BinaryTree<T extends Comparable<T>> {

class Node {
Node left;
Node right;
T data;

Boolean leftThread;
Boolean rightThread;
}

/**
*
* @param value value to be inserted
* @return new root of binary tree
*/


public Node insert(Node root, T value) {

Node ptr = root;
Node par = null;

while (!Objects.isNull(ptr)) {

if (value.equals(ptr.data)) {
return root;
}
par = ptr;

if (value.compareTo(ptr.data) < 0) {
if (!ptr.leftThread)
ptr = ptr.left;
else
break;
} else {
if (!ptr.rightThread) {
ptr = ptr.right;
}
else {
break;
}
}
}

Node tmp = new Node();
tmp.data = value;
tmp.leftThread = true;
tmp.rightThread = true;

if (par == null) {
root = tmp;
tmp.left = null;
tmp.right = null;
} else if (value.compareTo(par.data) < 0) {
tmp.left = par.left;
tmp.right = par;
par.leftThread = false;
par.left = tmp;
} else {
tmp.left = par;
tmp.right = par.right;
par.rightThread = false;
par.right = tmp;
}
return root;
}

/**
*
* @param pointer pointer to current node
* @return new root of binary tree
*/

private Node inorderSuccessor(Node pointer) {

if (pointer.rightThread){
return pointer.right;
}
pointer = pointer.right;
while (!pointer.leftThread) {
pointer = pointer.left;
}
return pointer;
}

/**
*
* @param pointer pointer to current node
* @return new root of binary tree
*/

private Node inorderPredecessor(Node pointer) {

if (pointer.leftThread) {
return pointer.left;
}

pointer = pointer.left;

while (!pointer.rightThread) {
pointer = pointer.right;
}

return pointer;
}

/**
*
* @param root root of binary tree
* @param value key that will be searched for
* @return found value
*/

public Node search(Node root, T value) {
if (Objects.isNull(root) || root.data.equals(value)) {
return root;
}

if (root.data.compareTo(value) < 0) {
return search(root.right, value);
}
return search(root.left, value);
}

/**
*
* @param root root of binary tree
* @param parent pointer to parent node
* @param pointer pointer to current node
* @return new root of binary tree
*/

private Node removeNoChild(Node root, Node parent, Node pointer) {

if (parent == null) {
root = null;
} else if (pointer == parent.left) {
parent.leftThread = true;
parent.left = pointer.left;
} else {
parent.rightThread = true;
parent.right = pointer.right;
}

return root;
}

/**
*
* @param root root of binary tree
* @param parent pointer to parent node
* @param pointer pointer to current node
* @return new root of binary tree
*/

private Node removeOneChild(Node root, Node parent, Node pointer) {
Node child;

if (!pointer.leftThread) {
child = pointer.left;
} else {
child = pointer.right;
}

if (parent == null) {
root = child;
} else if (pointer == parent.left) {
parent.left = child;
} else {
parent.right = child;
}

Node successor = inorderSuccessor(pointer);
Node predecessor = inorderPredecessor(pointer);

if (!pointer.leftThread) {
predecessor.right = successor;
} else if (!pointer.rightThread) {
successor.left = predecessor;
}

return root;
}

/**
*
* @param root root of binary tree
* @param pointer pointer to current node
* @return new root of binary tree
*/

private Node removeTwoChildren(Node root, Node pointer) {
Node parentSuccessor = pointer;
Node successor = pointer.right;

while (!successor.leftThread) {
parentSuccessor = successor;
successor = successor.left;
}

pointer.data = successor.data;

if (successor.rightThread){
root = removeNoChild(root, parentSuccessor, successor);
} else {
root = removeOneChild(root, parentSuccessor, successor);
}
return root;
}

/**
*
* @param root root of binary tree
* @param value value to be removed
* @return new root of binary tree
*/

Node remove(Node root, T value) {
Node parent = null;
Node pointer = root;

boolean isFound = false;

while (!Objects.isNull(pointer)) {
if (value == pointer.data) {
isFound = true;
break;
}
parent = pointer;
if (value.compareTo(pointer.data) < 0) {
if (!pointer.leftThread) {
pointer = pointer.left;
} else {
break;
}
} else {
if (!pointer.rightThread) {
pointer = pointer.right;
} else {
break;
}
}
}

if (!isFound) {
return root;
} else if (!pointer.leftThread && !pointer.rightThread) {
root = removeTwoChildren(root, pointer);
} else if (!pointer.leftThread || !pointer.rightThread) {
root = removeOneChild(root, parent, pointer);
} else {
root = removeNoChild(root, parent, pointer);
}
return root;
}

/**
*
* @param root root of binary tree
* @return string representation of tree
*/

String asString(Node root) {

StringBuilder stringBuilder = new StringBuilder();

if (root == null){
return "Tree is empty";
}

Node ptr = root;

while (!Objects.isNull(ptr) && !ptr.leftThread) {
ptr = ptr.left;
}

while (!Objects.isNull(ptr)) {
stringBuilder.append(ptr.data).append("\n");
ptr = inorderSuccessor(ptr);
}
return stringBuilder.toString();
}
}