Мой метод удаления состоит из 4 операторов if, которые касаются 4 различных типов удаления в двоичном дереве. Не уверен, где ошиблись, но он не удалил ни одного узла, когда я проверил его с помощью своей функции размера.
Кроме того, есть ли способ сделать generi c только ""? Я пытаюсь отформатировать функцию печати двоичного дерева.
Мой код прилагается ниже
public class BinaryTree<T extends Comparable<T>> {
private class Node{
private T data;
private Node left;
private Node right;
public Node ( T data) {
this.data = data;
this.left = null;
this.right = null;
}}
private Node root;
private int count = 0;
public void add( T data) {
if ( isEmpty()) {
root = new Node(data);
count++;
}
else {
insert(data, root);
count++;
}
}
public boolean isEmpty() {
return root == null;
}
public T getRoot() {
if ( root.data == null) {
System.out.println("Root is empty");
return null;
}
else {
return root.data;
}}
public Node getRootNode() {
return root;
}
private void insert( T data, Node node) {
int compare = data.compareTo(node.data);
if ( compare < 1 ){
if (node.left == null ) {
node.left = new Node(data);
}
else {
insert(data, node.left);
}
}
else {
if ( node.right == null) {
node.right = new Node(data);
}
else {
insert( data, node.right);
}
}
}
public int getSize() {
return count;
}
public boolean search ( T data) {
return searchInner( data, root);
}
public boolean searchInner( T data, Node node) {
int compare = data.compareTo(node.data);
if ( getRoot() == data ) {
return true;
}
if ( compare > 1) {
searchInner( data, node.right);
}
if ( compare < 1 ) {
searchInner(data , node.left);
}
if ( compare == 0 ) {
return true;
}
else {
System.out.println("Not found");
return false;
}
}
public void remove( T data) {
Node parent = root;
Node node = root;
Node temp;
boolean isLeft = true;
while ( node.data != data) {
parent = node;
if ( isEmpty()) {
System.out.println("Unable to remove, root is empty");
break;
}
if ( compare(data, node.data) < 0) {
node = node.left;
isLeft = true;
}
// does node becomes node.right?
if ( compare(data, node.data) > 0) {
node = node.right;
isLeft = false;
}
else {
if ( node.left == null && node.right != null) {
temp = node.right;
node.right = null;
node = temp;
count --;
break;
}
if ( node.right == null && node.left != null) {
temp = node.left;
node.left = null;
node = temp;
count --;
break;
}
if ( node.left != null && node.right != null ) {
if (isLeft) {
parent.left = node;
count --;
break;
}
else {
parent.right = node;
count --;
break;
}
}
if ( node.left == null && node.right == null) {
node = null;
count --;
break;
}
}
}
}
private int compare( T data, T data1) {
return data.compareTo(data1);
}
public void printBST(T data) {
printTree( root, data);
}
private void printTree( Node node, T data)
{
if(node == null) return;
System.out.println(data + " + " + node.data);
printTree(node.left , data);
printTree(node.right , data);
}
public int getHeight() {
return getHeight1(root);
}
public int getHeight1( Node node) {
if ( isEmpty()) {
return -1;
}
return Math.max(getHeight1(node.left),getHeight1(node.right)) + 1;
}
}