private boolean Delete(int data, Node node, Node grand, boolean isLeft) {
if (node == null) {
return false;
}
if (data < node.data) {
return Delete(data, node.leftChild, node, true);
} else if (data > node.data) {
return Delete(data, node.rightChild, node, false);
} else {
if (node.leftChild != null && node.rightChild != null) {
if (isLeft == true) {
Node temp = grand.leftChild;
grand.leftChild = findReplacement(node.rightChild);
node = grand.leftChild;
node.leftChild = temp.leftChild;
node.rightChild = temp.rightChild;
} else {
Node temp = grand.rightChild;
grand.rightChild = findReplacement(node.rightChild);
node = grand.leftChild;
node.leftChild = temp.leftChild;
node.rightChild = temp.rightChild;
}
} else {
if (node.leftChild == null && node.rightChild == null) {
if (isLeft == true) {
grand.leftChild = null;
} else {
grand.rightChild = null;
}
} else if (node.rightChild == null) {
if (isLeft == true) {
grand.leftChild = node.leftChild;
} else {
grand.rightChild = node.leftChild;
}
} else if (node.leftChild == null) {
if (isLeft == true) {
grand.leftChild = node.rightChild;
} else {
grand.rightChild = node.rightChild;
}
}
}
return true;
}
}
Node findReplacement(Node node) {
Node parent = null;
Node result = null;
while (node.leftChild != null) {
parent = node;
node = node.leftChild;
result = node;
}
if (node.rightChild != null) {
parent.leftChild = node.rightChild;
} else {
if (parent != null) {
parent.leftChild = null;
} else {
result = node;
}
}
return result;
}
if (node == null) {
return false;
}
if (data < node.data) {
return Delete(data, node.leftChild, node, true);
} else if (data > node.data) {
return Delete(data, node.rightChild, node, false);
} else {
if (node.leftChild != null && node.rightChild != null) {
if (isLeft == true) {
Node temp = grand.leftChild;
grand.leftChild = findReplacement(node.rightChild);
node = grand.leftChild;
node.leftChild = temp.leftChild;
node.rightChild = temp.rightChild;
} else {
Node temp = grand.rightChild;
grand.rightChild = findReplacement(node.rightChild);
node = grand.leftChild;
node.leftChild = temp.leftChild;
node.rightChild = temp.rightChild;
}
} else {
if (node.leftChild == null && node.rightChild == null) {
if (isLeft == true) {
grand.leftChild = null;
} else {
grand.rightChild = null;
}
} else if (node.rightChild == null) {
if (isLeft == true) {
grand.leftChild = node.leftChild;
} else {
grand.rightChild = node.leftChild;
}
} else if (node.leftChild == null) {
if (isLeft == true) {
grand.leftChild = node.rightChild;
} else {
grand.rightChild = node.rightChild;
}
}
}
return true;
}
}
Node findReplacement(Node node) {
Node parent = null;
Node result = null;
while (node.leftChild != null) {
parent = node;
node = node.leftChild;
result = node;
}
if (node.rightChild != null) {
parent.leftChild = node.rightChild;
} else {
if (parent != null) {
parent.leftChild = null;
} else {
result = node;
}
}
return result;
}
No comments:
Post a Comment