Alguém poderia me mostrar uma implementação de uma função em Java que mova um elemento hierarquicamente em uma Árvore Binária?
1
2
3
Para
1
\
3
\
2
Código parcial da árvore Binária
@Override
public void add(final E element) {
this.root = this.add(this.root, element);
}
private Node<E> add(final Node<E> node, final E element) {
if (node == null) {
return new Node<>(element);
}
final int compareTo = this.compareTo(node, element);
Node<E> son = null;
if (compareTo < 0) {
son = this.add(node.getLeft(), element);
son.setFather(node);
node.setLeft(son);
} else {
if (compareTo > 0) {
son = this.add(node.getRight(), element);
son.setFather(node);
node.setRight(son);
}
}
return node;
}
@Override
public void remove(final E element) {
this.root = this.remove(this.root, element);
}
private Node<E> remove(final Node<E> node, final E element) {
if (node == null) {
return null;
}
final int compareTo = this.compareTo(node, element);
if (compareTo == 0) {
if (!node.hasSons()) {
return null;
}
if (!node.hasRightSon()) {
return node.getLeft();
}
if (!node.hasLeftSon()) {
return node.getRight();
}
final E smallestElement = this.getSmallestElement(node.getRight());
node.setElement(smallestElement);
node.setRight(this.remove(node.getRight(), element));
}
if (compareTo < 0) {
node.setLeft(this.remove(node.getLeft(), element));
}
if (compareTo > 0) {
node.setRight(this.remove(node.getRight(), element));
}
return node;
}
@Override
public void replace(final E oldElement, final E newElement) {
final Node<E> node = this.getNode(this.root, oldElement);
if (node != null) {
node.setElement(newElement);
if (node.hasFather()) {
final Node<E> father = node.getFather();
if (father.getLeft() == node) {
father.setLeft(node);
}
if (father.getRight() == node) {
father.setRight(node);
}
}
if (node.hasLeftSon()) {
node.getLeft().setFather(node);
}
if (node.hasRightSon()) {
node.getRight().setFather(node);
}
this.root = node;
}
}
@Override
public void reverserSons(final E element) {
final Node<E> father = this.getNode(this.root, element);
if (father != null) {
final Node<E> auxNode = father.getRight();
father.setRight(father.getLeft());
father.setLeft(auxNode);
this.root = father;
}
}
@Override
public int getHeight(final E element) {
final Node<E> node = this.getNode(this.root, element);
return this.getHeight(node);
}
private int getHeight(final Node<E> node) {
if (node == null) {
return 0;
}
final int leftHeight = this.getHeight(node.getLeft());
final int rightHeight = this.getHeight(node.getRight());
return Math.max(leftHeight, rightHeight) + 1;
}
private Node<E> getNode(final Node<E> node, final E element) {
if (node == null) {
return null;
}
final int compareTo = this.compareTo(node, element);
if (compareTo < 0) {
return this.getNode(node.getLeft(), element);
}
if (compareTo > 0) {
return this.getNode(node.getRight(), element);
}
return node;
}
private int compareTo(final Node<E> node, final E element) {
return element.compareTo(node.getElement());
}
Código parcial do Nó
public class Node<E> {
private Node<E> father;
private E element;
private Node<E> left;
private Node<E> right;
public Node(final E element) {
this.element = element;
}
public Node(final Node<E> father, final E element) {
this(element);
this.father = father;
}
public Node(final E element, final Node<E> left, final Node<E> right) {
this(element);
this.left = left;
this.right = right;
}
public Node(final Node<E> father, final E element, final Node<E> left, final Node<E> right) {
this(element, left, right);
this.father = father;
}
public Node<E> getFather() {
return father;
}
public void setFather(final Node<E> father) {
this.father = father;
}
public E getElement() {
return element;
}
public void setElement(final E element) {
this.element = element;
}
public Node<E> getLeft() {
return left;
}
public void setLeft(final Node<E> left) {
this.left = left;
}
public Node<E> getRight() {
return right;
}
public void setRight(final Node<E> right) {
this.right = right;
}
public boolean hasSons() {
return this.hasLeftSon() && this.hasRightSon();
}
public boolean hasFather() {
return this.father != null;
}
public boolean hasLeftSon() {
return this.left != null;
}
public boolean hasRightSon() {
return this.right != null;
}
@Override
public String toString() {
String toString = "Node: {";
toString += "\n\tElement: " + this.element;
if (this.hasFather()) {
toString += ", \n\tFather: " + this.father.getElement();
}
if (this.hasLeftSon()) {
toString += ", \n\tLeft: " + this.left.getElement();
}
if (this.hasRightSon()) {
toString += ", \n\tRight: " + this.right.getElement();
}
toString += "\n}";
return toString;
}
}