package com.java912.data;
public class MyTree {
private TNode root;
public void add(Object value){
TNode node = new TNode(value);
if (root == null){
root = node;
}else{
ParrentLR pl = search(value);
if (pl.isLeft){
pl.parrent.left = node;
}else{
pl.parrent.right = node;
}
node.parrent = pl.parrent;
}
}
public boolean delete(Object value){
boolean result = false;
TNode node = find(value);
while (node != null){
if (node.parrent == null){
if (node.left == null && node.right == null){
root = null;
}else if (node.left != null && node.right == null){
root = root.left;
}else if (node.left == null && node.right != null){
root = root.right;
}else{
root = fenLie(node);
}
if (root != null)
root.parrent = null;
}else{
TNode parrent = node.parrent;
boolean isLeft = false;
if (compare(parrent.data,node.data)){
isLeft = true;
}//end if
if (node.left == null && node.right == null){
if (isLeft){
parrent.left = null;
}else{
parrent.right = null;
}
}else if (node.left != null && node.right == null){
if (isLeft){
parrent.left = node.left;
}else{
parrent.right = node.left;
}
node.parrent = parrent;
}else if (node.left == null && node.right != null){
if (isLeft){
parrent.left = node.right;
}else{
parrent.right = node.right;
}
node.parrent = parrent;
}else{
TNode tempnode = fenLie(node);
if (isLeft){
parrent.left = tempnode;
}else{
parrent.right = tempnode;
}
tempnode.parrent = parrent;
}
}//end if (node.parrent == null){
node = find(value);
}//end while (node != null){
return result;
}
private TNode fenLie(TNode node){
TNode result = node.left;
TNode temp = result;
TNode parrent = temp;
while (temp != null){
parrent = temp;
temp = temp.right;
}
parrent.right = node.right;
return result;
}
private TNode find(Object value){
TNode temp = root;
while (temp != null){
if (temp.data.equals(value)){
break;
}else if (compare(temp.data,value)){
temp = temp.left;
}else{
temp = temp.right;
}
}
return temp;
}
private ParrentLR search(Object value){
ParrentLR pl = new ParrentLR();
TNode temp = root;
TNode parrent = root;
boolean isLeft = false;
while (temp != null){
parrent = temp;
if (compare(temp.data,value)){
temp = temp.left;
isLeft = true;
}else{
temp = temp.right;
isLeft = false;
}
}
pl.parrent = parrent;
pl.isLeft = isLeft;
return pl;
}
private boolean compare(Object o1,Object o2){
boolean result = false;
if (o1 instanceof Comparable){
Comparable c1 = (Comparable)o1;
Comparable c2 = (Comparable)o2;
int r = c1.compareTo(c2);
if (r > 0){
result = true;
}
}else{
int r = o1.toString().compareTo(o2.toString());
if (r > 0){
result = true;
}
}
return result;
}
private class ParrentLR{
public TNode parrent;
public boolean isLeft;
public ParrentLR(){
}
public ParrentLR(TNode parrent,boolean isLeft){
this.parrent = parrent;
this.isLeft = isLeft;
}
}
public void print(){
diGui(root);
}
private void diGui(TNode node){
if (node == null){
return;
}else{
diGui(node.left);
System.out.print(node.data + ",");
diGui(node.right);
}
}
}
